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.Prerequisites: Basic knowledge of algorithms, probability and linear algebra at an undergraduate level.
Announcements (with post-date):
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 k-colorability
(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. Low-rank 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 sample-scribe.tex
together with definitions file defs.tex;
see the resulting sample-scribe.pdf
Relevant Resources:
Surveys and expository articles:
Suggested papers for presentations (in crude categorization):
Geometry, clustering etc.: