Class Materials

Scribers: please use this LaTeX template as your starting point.

Lectures

1. 01/22/2019: Intro, Morris algorithm for approx counting (scribe in pdf and tex)
   • Morris: Lecture 1 from here
2. 01/24/2019: Chernoff bound, distinct elements count (scribe in pdf and tex)
   • Lecture 2 from here
3. 01/29/2019: Impossibility results, Tug-of-War sketch for 2nd moment (scribe in pdf and tex)
   • Lectures 2,3 from here
4. 01/31/2019: Heavy hitters, CountMin, linearity (scribe in pdf and tex)
   • Lectures 3,4 from here
5. 02/5/2019: High frequency moments and precision sampling (scribe in pdf and tex)
   • For the full analysis of the Fp sketch see this write-up. Section 4 presents Precision Sampling Lemma.
   • Lectures 4,5 from here
6. 02/7/2019: Dimension reduction, ell_1 (scribe in pdf and tex)
   • Lecture 8 from here
7. 02/12/2019: Numerical Linear Algebra: least square regression, fast dimension reduction (scribe in pdf and tex)
   • Lecture 9, 14 from here
   • Lectures 6,7 from here
8. 02/14/2019: Numerical Linear Algebra: fast dimension reduction, ell_1 regression (scribe in pdf and tex)
   • Lecture 6 from here
9. 02/19/2019: Compressed sensing: Restricted Isometry Property (scribe in pdf and tex)
   • Lecture 13 from here
10. 02/21/2019: Compressed sensing: iterative hard thresholding (scribe in pdf and tex)
    • Lectures 13, 14 from here
    • In particular, for the proof of "RIP implies null-space property", see proof of Lemma 1 from this writeup (from Harvard/MIT class).
11. 02/26/2019: Streaming for graph problems: distance, triangle count (scribe in pdf and tex)
    • Lectures 5,6 from here
12. 02/28/2019: Streaming: dynamic sampling/ell_0 sampler (scribe in pdf and tex)
    • Lectures 6,7 from here
13. 03/05/2019: Streaming for dynamic graph problems: connectivity. (scribe in pdf and tex)
    • Lectures 6,7 from here
14. 03/07/2019: Distribution testing: uniformity (scribe in pdf and tex)
    • Lectures 17,18 from here
15. 03/12/2019: Distribution testing. (scribe in pdf and tex)
    • Lectures 17,18 from here
16. 03/14/2019: Monotonicity testing. Sublinear-time graph algorithms: MST. (scribe in pdf and tex)
    • Monotonicity: Lecture 18 from here
    • MST: Lecture 19 (Nov 12) from here
17. 03/26/2019: Sublinear-time graph algorithms: MST, and Vertex Cover. (scribe in pdf and tex)
    • MST: Lecture 19 (Nov 12) from here
    • VC: Lecture 20 from here
18. 03/28/2019: Sublinear-time graph algorithms: VC. Linearity testing (BLR). (scribe in pdf and tex)
    • VC: Lecture 20 from here
    • Linearity testing: Lecture 21 from here
19. 04/2/2019: Linearity testing (BLR test). (scribe in pdf and tex)
    • Linearity testing: Lecture 21 from here
20. 04/4/2019: Large-scale models: IO model, cache oblivious model. (scribe in pdf and tex)
    • lectures 24, 25 from here
21. 04/9/2019: Cache oblivious model, Parallel models. (scribe: version 1 pdf and tex; version 2 pdf and tex)
    • parallel: Lecture 24 from here
    • parallel: Lecture 25 from here
22. 04/11/2019: MPC model: sorting. (scribe in pdf and tex)
    • lecture 27 from D. Karger and A. Madry's class
23. 04/16/2019: MPC model: graph connectivity. (scribe in pdf and tex)
    • this lecture from G. Yaroslavtsev's class
24. 04/18/2019: Learning-aware/data-dependent algorithms. (scribe in pdf and tex)
    • lecture 7 from this class by P. Indyk and K. Daskalakis
25. 04/23/2019: LSH and fruit flies. (scribe in pdf and tex)
    • slides
26. 04/25/2019: presentations. class recap. (scribe in pdf and tex)

Other resources

• Algorithmic Techniques for Massive Data, Fall'15 (previous iteration of this class)
• Sketching Algorithms for Big Data, Fall'17, Jelani Nelson (Harvard), Piotr Indyk (MIT)
• List of other similar classes