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, other applications of LSH.(scribe)
    • tbd
11. 10/8/2025: HNSW.(scribe)
    • tbd

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)