Class Materials

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

Lectures

1. 9/3/2025: Class info. Start on Least Square Regression.(scribe)
   • Lecture 7 from here
2. 9/8/2025: Dimension Reduction.(scribe)
   • Lecture 6-7 from here
   • Lecture 3 from this Indyk/Nelson class.
3. 9/10/2025: LSR via Fast dimension reduction. Probability Tools.(scribe)
   • Lecture 7,8 from here
   • Lecture 9,11,12 from this Indyk/Nelson class.
4. 9/15/2025: Fast dimension reduction (FJL) construction and proof.(scribe)
   • Lecture 7,8 from here
   • Lecture 9 from this Indyk/Nelson class.
5. 9/17/2025: Compressed Sensing.(scribe)
   • Lecture 9,10 from here
   • Lecture 13 from this Indyk/Nelson class.
6. 9/22/2025: Proof that L1 minimization solves CS.(scribe)
   • Lecture 9,10 from here
   • Lecture 13 from this Indyk/Nelson class.
   • Proofs of core lemmas also appears in from this writeup (from Harvard/MIT class).
7. 9/24/2025: Iterative Hard Thresholding.(scribe)
   • Lecture 10 from here
   • Lecture 14 from this Indyk/Nelson class.
8. 9/29/2025: Extension of CS. Start on NNS.(scribe)
   • Lecture 14 from this Indyk/Nelson class.
   • GAN+CS: Ankur Moitra (MIT) lecture
   • NNS: lecture 8 from here
9. 10/1/2025: NNS: Locality Sensitive Hashing.(scribe)
   • NNS: lectures 9,10 from here
10. 10/6/2025: LSH functions.(scribe)
    • NNS: lectures 9,10 from here
11. 10/8/2025: LSH extensions/connections.(scribe)
12. 10/13/2025: More: Attention, HNSW.(scribe)
13. 10/15/2025: Large-scale models.(scribe)
    • See Section 1 from this lecture notes compilation by M. Gaffari.
    • Lecture 20 from here.
14. 10/20/2025: MPC models: sorting, graphs(scribe)
    • this lecture from G. Yaroslavtsev's class
    • Section 3 from this lecture notes compilation by M. Gaffari.
    • Lecture 20, 21 from here.
15. 10/22/2025: MPC models: sparse regime connectivity.(scribe)
    • this lecture from G. Yaroslavtsev's class
    • Section 3 from this lecture notes compilation by M. Gaffari.
    • Lecture 21 from here.
16. 10/27/2025: MPC models: doubling algorithms, other connections.
    • this lecture from G. Yaroslavtsev's class
    • Section 3 from this lecture notes compilation by M. Gaffari.
17. 10/29/2025: MPC models: geometric graph problems. Start on Sublinear time algorithms.
    • See Section 3.4 from this lecture notes compilation by M. Gaffari.
    • Lecture 24 from here
18. 11/5/2025: Sublinear time algorithms.
    • Lecture 15 from Paul Beame's class at UW.
    • Lecture 17 from here
19. 11/10/2025: Estimating MST.(scribe)
    • Lecture 15 from Paul Beame's class at UW.
20. 11/12/2025: Local algorithm for Independent Set. Start on Testing.(scribe)
    • Lecture 20 from here
    • Lecture 17 from here
21. 11/17/2025: Distribution testing: uniformity.(scribe)
    • lecture 7 from Paul Beame's class at UW.
    • Lectures 14,15 from here
22. 11/19/2025: Distribution testing: uniformity and beyond.(scribe (v1), scribe (v2))
23. 11/24/2025: Learning-augmented algorithms.
    • See this class by P. Indyk and K. Daskalakis (and lecture 7 specifically for what we've covered)

Other resources

• Sketching Algorithms for Big Data, Fall'17, Jelani Nelson (Harvard), Piotr Indyk (MIT)
• List of other related classes
• Algorithms for Massive Data, Spring'19 (2019 iteration of this class)
• Algorithms for Massive Data, Fall'23 (2023 iteration of this class)
• Algorithmic Techniques for Massive Data, Fall'15 (2015 iteration of this class)