Advanced Algorithms
CS/CMS 139
Winter 2018



Class: Mondays and Wednesdays 9-10:30am, Annenberg 213.
Recitation: TBA.


Schedule


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.