Sublinear Time and Space Algorithms (semester 2026A)

[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 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

• TBA

Lectures

1. 2025-10-29: TBA
   Reading: TBA 
   
2. 2025-11-05: TBA
   Reading: TBA
   
3. 2025-11-12: TBA
   Reading: TBA
   
4. 2025-11-19: TBA
   Reading: TBA
   
5. TBA
   

Assignments

• TBA
  

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