Sublinear Time and Space Algorithms (semester 2024A)

[Course description] [Announcements] [Lectures] [Assignments] [Reading material]

Course description

Instructor: Robert Krauthgamer

Grader: Shay Sapir

When and where: Wed. 14:15-16:00, Ziskind Lecture Room 155

First class: December 13, 2023 (new and adjusted schedule)

FGS code: 20244101 

Syllabus: The course will cover algorithms whose running time and/or space requirement is sublinear in the input size. Such algorithms can view only a small portion of the entire input, but they are particularly suitable for analyzing massive data sets. In recent years, this approach has been successfully used in several areas, including graph theory, linear algebra, combinatorial optimization, geometry, and string matching.

Prerequisites: Basic knowledge of algorithms, probability and linear algebra at an undergraduate level.

Final: There will be a take-home exam, distributed morning of March 19 (via email), and due within 72 hours. Its format will be similar to previous years.
Here is the final assignment itself.

Webpage: http://www.wisdom.weizmann.ac.il/~robi/teaching/2024a-SublinearAlgorithms

Previous offerings:

Announcements

• [posted 2024-02-07]: The final (take-home exam) schedule: Distributed morning of March 19 (via email), and due within 72 hours. Its format will be similar to previous years. For exceptions, please email me directly.
  
• [posted 2024-01-25]: Problem set 3 was corrected (the first question was deleted because it was already given in the problem set 2)
  
• The first class has been postponed to 2023-12-13 and the schedule below was adjusted accordingly
  

Lectures

1. 2023-12-13: Data-Stream Algorithms, Probabilistic Counting.
   Reading: lecture notes #1. See also Andoni, lecture #1; Nelson, lecture #1; Chekuri, lecture #1; and paper by Nelson and Yu.
   
2. 2023-12-20: Frequency Vectors, Distinct Elements, Frequency Moments, the AMS algorithm.
   Reading: lecture notes #2. See also Andoni, lectures #2+3; Nelson, lectures #2+3; Chekuri, lectures #2+4.
   Homework: problem set #1 below.
3. 2023-12-27: l_1 and l_2 Point Queries, Amplifying success probability.  
   Reading: lecture notes #3. See also Andoni, lectures #3+4; Nelson, lecture #7; Chekuri, lecture #6.
4. 2024-01-03: Dynamic Geometric Streams and Euclidean MST.
   Reading: lecture notes #4. See also Nelson, lecture #21; and paper by Indyk.
   Homework: problem set #2 below.
5. 2024-01-10: Adversarially Robust Streaming, Flip-Number and Sketch Switching. 
   Reading: lecture notes #5. See also two papers by Ben-Eliezer, Jayaram, Woodruff, and Yogev, and by Ben-Eliezer, Eden, and Onak.
6. 2024-01-17: Reservoir Sampling and l_0-sampling
   Reading: lecture notes #6. See also Nelson, lecture #18; Chekuri, lectures #1+9.
7. 2024-01-24: Streaming of Graphs and Connectivity in Dynamic Graphs.
   Reading: lecture notes #7. See also Andoni, lecture #5+6; Nelson, lecture #18.
   Homework: problem set #3 below.
8. 2024-01-31: Hash Functions with Limited Randomness and Triangle Counting.
   Reading: lecture notes #8. See also Andoni, lecture #6.
9. 2024-02-07: Sublinear-time algorithms for sparse graphs.
   Reading: lecture notes #9. See also survey by Czumaj and Sohler.
10. 2024-02-14: Sublinear-Time Algorithms for Vertex Cover in Planar Graphs
    Reading: lecture notes #10. See also paper by Hassidim, Kelner, Nguyen and Onak.
    Homework: problem set #4 below.
11. 2024-02-21: Planar Vertex Cover (cont'd) and Sampling an Edge Uniformly 
    Reading: lecture notes #11. See also paper by Eden and Rosenbaum.
12. 2024-02-28: Communication Complexity and Streaming Lower Bounds 
    Reading: lecture notes #12. See also Nelson, lecture #20; Beame, lectures #11+12.

Assignments

• problem set #1 (posted December 21)
• problem set #2 (posted January 3)
• problem set #3 (posted January 24)
• problem set #4 (posted February 15)

Reading material

Books, surveys and lecture notes:

• Algorithms for Big Data by Moran Feldman (2020) -- eBook available inside Weizmann
• Small Summaries for Big Data by Cormode and Yi (2020)
  
• Data Stream Algorithms, lecture notes by Amit Chakrabarti (2020)
• Data Streams: Algorithms and Applications by S. Muthukrishnan (2005)
• Graph Stream Algorithms: a Survey by Andrew McGregor (2014)
• Sublinear-time algorithms by Artur Czumaj and Christian Sohler (2010)
• Sublinear Time Algorithms by Ronitt Rubinfeld (2006)
• Sketch Techniques for Approximate Query Processing by Graham Cormode (2011)
• The Continuous Distributed Monitoring Model by Graham Cormode (2013)
• Sketching as a Tool for Numerical Linear Algebra by David Woodruff (2014)
  

Similar/related courses (many with lecture notes):

• Sublinear Algorithms by Sepehr Assadi (2021)
  
• Sublinear Algorithms by Sofya Raskhodnikova (2020)
  
• Data Stream Algorithms by Amit Chakrabarti at Dartmouth (2020)
• Sketching Algorithms for Big Data by Jelani Nelson at Harvard (2017)
• Algorithmic Techniques for Massive Data by Alexandr Andoni at Columbia (2015)
• Algorithms for Big Data by Chandra Chekuri at UIUC (2014)
• Sublinear Algorithms by Piotr Indyk and Ronitt Rubinfeld at MIT (2013)
• Sublinear and Streaming Algorithms by Paul Beame at U. of Washington (2014)
• Data Streams Algorithms by Andrew McGregor at UMass (2018)
• Introduction to Property Testing by Oded Goldreich at Weizmann (2015)
• Seminar on Sublinear Time Algorithms by Ronitt Rubinfeld at Tel Aviv U. (2016)
  

Useful references:

• Concentration of Measure for the Analysis of Randomized Algorithms by Dubhashi and Panconesi (errata)
• Concentration by Colin McDiarmid. Probabilistic Methods for Algorithmic Discrete Mathematics, 1998, 1-46

Other:

• Open Problems in Sublinear Algorithms