Approximate schedule:
| Week | Lecture | Recitation and Problem Solving Practice |
|---|---|---|
| 1 | Introduction | Variation distance |
| 1-2 | Linearity of expectation | Sum-Free subsets |
| 2-3 | Alterations | Derandomization using the method of conditional expectations |
| 3-4 | The isolating lemma | Derandomization using the method of limited independence |
| 5 | The second moment method | Applications of the second moment method |
| 6 | Large deviation inequalities | Large deviations in "rare" variables, multiplicative Chernoff bounds |
| 6-7 | Martingales | Additional martingale examples, the Poisson paradigm |
| 8-9 | The Lovász local lemma | A constructive proof of the local lemma |
| 10 | Correlation inequalities | Additional correlation inequalities, lower bound in Janson's inequality |
| 11-12 | Entropy | Shearer's inequality, applications |
| 13 | Introduction to random walks | Complementary material |
Approximate homework schedule (subject to change):
| Assignment | Release date | Due date |
|---|---|---|
| HW1 | 30.10 | 24.11 |
| HW2 | 27.11 | 29.12 |
| HW3 | 1.1 | 26.1 |
| HW4 | 29.1 | 2.3 |