Approximate schedule (subject to change):
Week | Lecture | Recitation and Problem Solving Practice |
---|---|---|
1 | Introduction | Variation distance |
1-2 | Linearity of expectation | Sum-Free subsets |
2-3 | Alterations | Two methods for derandomization |
4 | The second moment method | Applications of the second moment method |
5 | Large deviation inequalities | Large deviations in "rare" variables, multiplicative Chernoff bounds |
5-6 | Martingales | Additional martingale examples |
7-8 | The Lovász local lemma | A constructive proof of the local lemma |
9 | Correlation inequalities | Additional correlation inequalities |
10-11 | Entropy | Shearer's inequality, applications |
12 | Complementary material | Complementary material |
Approximate homework schedule is TBA (due to the last-minute semester delay).