Class: Mondays and Wednesdays 9-10:30am, Annenberg 213.
|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.|