Seminar on Sublinear Time Algorithms (2010)
Instructor: Robi Krauthgamer
When and where: Wednesdays 24pm, 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.Prerequisites: Basic knowledge of algorithms, probability and linear algebra at an undergraduate level.
Announcements (with postdate):
Date 
Topic 
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 kcolorability
(presenting: Igor) 2. Proximity oblivious testing (presenting: Aviv) 
paper by Alon and Krivelevich
(2002) paper by Goldreich and Ron (2009) 
presentation2 presentation3 
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) 
presentation4 presentation5 
Jun. 2 
no class
(IMU meeting) 

Jun. 9 
no class
(cancelled) 

Jun. 16 
1. Lowrank matrix
approximations (presenting: Boris) 2. Testing Monotonicity (presenting: Shlomo) 
presentation6 presentation7 

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) 
presentation8

Note: Scribes are in
somewhat draft form, and may skip details, have typos etc.
Scribes template: Use
the example latex file samplescribe.tex
together with definitions file defs.tex;
see the resulting samplescribe.pdf
Relevant Resources:
Surveys and expository articles:
Suggested papers for presentations (in crude categorization):
Geometry, clustering etc.: