Sublinear Time and Space Algorithms (semester 2026A)

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

Course description

Instructor: Robert Krauthgamer

Grader:Yotam Kenneth

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

First class: October 29, 2025

FGS code: 20264031

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.

Previous offerings:

Announcements

• n/a
  

Lectures

1. 2025-10-29: Data-stream algorithms, probabilistic counting.
   Reading: lecture notes #1.
2. 2025-11-05: Frequency Vectors, Distinct Elements, Frequency Moments, and the AMS algorithm.
   Reading: lecture notes #2.
3. 2025-11-12: l_1 and l_2 Point Queries, Amplifying success probability.
   Reading: lecture notes #3. 
4. 2025-11-19: Precision Sampling and High Frequency Moments.
   Reading: lecture notes #4.
5. 2025-11-26: Dynamic Geometric Streams and Euclidean MST.
   Reading: lecture notes #5.
6. 2025-12-03: Reservoir Sampling and l_0-sampling.
   Reading: lecture notes #6.
7. 2025-12-10: Streaming of Graphs and Connectivity in Dynamic Graphs.
   Reading: lecture notes #7.
8. 2025-12-17 (Yotam): Cut-Query Algorithms and Streaming Data Structures.
   Reading: slides and notes.
   
9. 2025-12-24: Hash Functions with Limited Randomness and Triangle Counting.
   Reading: lecture notes #9.
10. 2025-12-31: Approximating Average Degree in Sublinear Time.
    Reading: lecture notes #10.
11. 2026-01-07: Maximum Matching and Sampling an Edge Uniformly.
    Reading: lecture notes #11.
12. 2026-01-21: Sublinear-Time Algorithms for Vertex Cover in Planar Graphs.
    Reading: lecture notes #12.

Assignments

• problem set #1 (posted November 6)
• problem set #2 (posted November 21)
• problem set #3 (posted December 4)
• problem set #4 (posted December 26)
  
• problem set #5 (posted January 7)
  

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