Class Materials

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

Lectures

1. 9/6/2023: Intro, course topics. Streaming for graph problems: connectivity, distance (scribe)
   • Lecture 11 from here
   • Lectures 5,6 from here
2. 9/11/2023: Streaming for graph problems: distance, triangle count(scribe)
   • Lecture 11,12 from here
3. 9/13/2023: Probability review. Streaming for graph problems: triangle count, dynamic streaming(scribe)
   • Lecture 12 from here
   • Lecture 18 from this Indyk/Nelson class.
4. 9/18/2023: Dynamic streaming for graphs: connectivity(scribe)
   • Lecture 13 from here
   • Lecture 18 from this Indyk/Nelson class.
5. 9/20/2023: Dynamic connectivity. Dimension reduction.(scribe)
   • Lecture 21 from here
   • Lecture 3 from this Indyk/Nelson class.
6. 9/25/2023: Numerical Linear Algebra: LSR.(scribe)
   • Lecture 7,8 from here
   • Lecture 9,10 from this Indyk/Nelson class.
7. 9/27/2023: Fast dimension reduction.(scribe)
   • Lecture 7,8 from here
   • Lecture 9,10 from this Indyk/Nelson class.
8. 10/2/2023: Compressed sensing.(scribe)
   • Lecture 13 from here
9. 10/4/2023: Compressed sensing.(scribe)
   • Lectures 13, 14 from here
10. 10/9/2023: Iterative Hard Thresholding.(scribe)
    • Lecture 14 from here
    • Lecture 10 from here
11. 10/11/2023: Sparse Fourier Transform.(scribe)
    • Lecture 16 from here
12. 10/16/2023: Sparse Fourier Transform.(scribe)
    • Lectures 16, 17 from here
13. 10/18/2023: Sparse Fourier Transform. Distribution Testing.(scribe)
    • lecture 7 from Paul Beame's class at UW.
    • Lectures 14,15 from here
14. 10/21/2023: Distribution Testing: uniformity(scribe)
15. 10/25/2023: Closeness Testing. Monotonicity Testing.(scribe)
    • Lecture 15 from Paul Beame's class at UW.
    • Lectures 15 (distribution testing), 16 (monotonicity testing) from here
16. 10/30/2023: Monotonicity Testing. Sublinear algos for graphs.(scribe)
    • Lecture 15 from Paul Beame's class at UW.
    • Lectures 16, 17 from here
17. 11/1/2023: Sublinear algos for graphs: MST.
    • Lecture 15 from Paul Beame's class at UW.
    • Lecture 17 from here
18. 11/8/2023: Sublinear algos for graphs: vertex cover. (scribe)
    • Lecture 20 from here
19. 11/13/2023: Learning-aware/data-dependent algorithms.
    • lecture 7 from this class by P. Indyk and K. Daskalakis
20. 11/15/2023: Massively Parallel Computing model.
    • See Section 1 from this lecture notes compilation by M. Gaffari.
21. 11/20/2023: MPC: graph connectivity.(scribe)
    • this lecture from G. Yaroslavtsev's class
    • Section 3 from this lecture notes compilation by M. Gaffari.
22. 11/27/2023: MPC algorithms for geometric graphs: MST of a pointset on a plane
    • See Section 3.4 from this lecture notes compilation by M. Gaffari.
    • Lecture 24 from here
23. 11/29/2023: MPC algorithms for geometric graphs: MST (cont).(scribe)
24. 12/4/2023: CONGEST and CONGESTED CLIQUE models.
    • See Sections 2,3 from this lecture notes compilation by M. Gaffari.

Other resources

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