Class: Mondays and Wednesdays 9-10:30am, Annenberg 213.
Recitation: TBA.
| January 3rd | Streaming algorithms and basic probabilistic inequalities. | Notes |
| January 8th | The Chernoff bound and amplification via median-of-means. | Notes |
| January 10th | Applications of the Chernoff bound: the Johnson-Lindenstrauss lemma; sketching for matrix products; approximate nearest neighbors. | Notes |
| Friday 12th | Recitation: count-min sketch. | |
| January 15th | Online learning and the Multiplicative Weights algorithm. | |
| January 17th | Applications of the Multiplicative Weights algorithm. |