Resources on Sublinear Algorithms

(Please add links only to class websites that provide lecture notes and/or slides.)

Communication complexity (sublinear communication)

Classes

• P. Harsha, M. Mahajan, and J. Radhakrishnan. Communication Complexity. TIFR & IMSc, Monsoon Semester 2011-12.

Compressed sensing (sublinear measurement)

Classes

• P. Indyk. Sketching, streaming, and sub-linear space algorithms. MIT, Fall 2007.
• P. Indyk and R. Rubinfeld. Sublinear Algorithms. MIT, Fall 2010.

Property testing and sublinear-time algorithms

Classes

• R. Rubinfeld and E. Ben-Sasson. Sublinear Time Algorithms. MIT, Fall 2004.
• R. Rubinfeld. Sublinear Time Algorithms. MIT, Spring 2007.
• P. Indyk and R. Rubinfeld. Sublinear Algorithms. MIT, Fall 2010.
• S. Raskhodnikova. Sublinear Algorithms. Penn State, Spring 2012.
• T. Sauerwald. Sublinear Algorithms. Max Planck Institut, Winter Semester 2012.

Surveys

• E. Fischer. The art of uninformed decisions: a primer to property testing. 2001.
• D. Ron. Property Testing. Handbook of Randomized Computing, Vol. II, 2001.
• R. Rubinfield. Sublinear time algorithms. Proceedings of the International Congress of Mathematicians, 2006.
• D. Ron. Property testing: a learning theory perspective. 2008.
• A. Czumaj and C. Sohler. Sublinear-time algorithms. In Property Testing. Current Research and Surveys. 2010.
• O. Goldreich. Introduction to testing graph properties. 2010.
• R. Rubinfeld and A. Shapira. Sublinear time algorithms. SIAM Journal on Discrete Mathematics 25, 2011.

Streaming algorithms

Classes

• A. Chakrabarti. Data Stream Algorithms. Dartmouth, Fall 2011.
• P. Indyk. Sketching, streaming, and sub-linear space algorithms. MIT, Fall 2007.
• P. Indyk and R. Rubinfeld. Sublinear Algorithms. MIT, Fall 2010.
• A. McGregor. Data streams and massive data. University of Massachusetts in Amherst, Spring 2012.

Surveys

• S. Muthukrishnan. Data streams: algorithms and applications. Now Publishers Inc, 2005.