Seminar on Sublinear Time Algorithms (2010)

Instructor: Robi Krauthgamer

When and where: Wednesdays 2-4pm, Ziskind 1

Syllabus: This seminar will cover algorithms whose running time 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.
The planned format is a combination of instructor lectures and student presentations, based on recent papers and surveys.

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

Announcements (with post-date):

(weekly handouts typically include announcements, overview of topics covered, and problem sets)



Reading (found below)

Handouts and scribes

Mar. 17

Motivation and basic examples: diameter of point set, finding element in list, average degree in graph

Survey by Czuamj and Sohler

handout1, scribe1
Mar. 24
Minimum spanning trees and maximum matching in sparse graphs
Survey by Czuamj and Sohler handout2, scribe2
Mar. 31
no class (holiday)

Apr. 7
Property testing framework, Testing monotonicity of a list
Survey by Rubinfeld
handout3, scribe3
Apr. 14
Testing homomorphism of a function, testing bipartiteness of a dense graph
Survey by Rubinfeld, Introduction by Goldreich
handout4, scribe4
Apr. 21
Query complexity lower bounds: for element distinctness, and for testing juntas
paper by Chockler and Gutfreund
handout5, scribe5
Apr. 28
Testing of clustering (presenting: Nir)
paper by Alon, Dar, Parnas, and Ron (2003) presentation1
May 5
no class (department trip)

May 12
1. Testing k-colorability (presenting: Igor)
2. Proximity oblivious testing (presenting: Aviv)
paper by Alon and Krivelevich (2002)
paper by Goldreich and Ron (2009)
May 19
no class (holiday)

May 26
1. Weakly approximating edit distance (presenting: Itai)
2. Testing distributions (presenting: Anat)
paper by Batu, et a. Ergün, Kilian, Magen, Raskhodnikova, Rubinfeld and Sami (2003)
paper by Batu, Fortnow, Rubinfeld, Smith and White (2000)

Jun. 2
no class (IMU meeting)

Jun. 9
no class (cancelled)

Jun. 16
1. Low-rank matrix approximations (presenting: Boris)
2. Testing Monotonicity (presenting: Shlomo)


Jun. 23
Local partitioning of planar graphs, and additive approximation of vertex cover
paper by Hassidim, Kelner, Nguyen, and Onak (2009)
handout6, scribe6
Jun. 30
Testing distributions (presenting: Tamar and Omer)


Note: Scribes are in somewhat draft form, and may skip details, have typos etc.
Scribes template: Use the example latex file sample-scribe.tex together with definitions file defs.tex; see the resulting sample-scribe.pdf

Relevant Resources:

Surveys and expository articles:

Concentration inequalities: How to read research papers:
Classes in other institutions:

Suggested papers for presentations (in crude categorization):

Geometry, clustering etc.: Ranking and string problems: Matrix problems: Testing graph properties: Testing distributions and functions: