Computer Science
Tel-Aviv University

0368.4612
Seminar on Sublinear Time Algorithms

Instructor: Ronitt Rubinfeld
Fall 2008

Course Description

With the growing importance of massive data sets, there has been increased interest in algorithms that consider only a very small portion of the data, in particular, algorithms which run in sublinear time. The study of sublinear time algorithms has been applied to problems from a wide range of areas, and many beautiful techniques have been applied to analyzing such algorithms, including the Szemeredi Regularity Lemma, low rank approximations of matrices, Fourier analysis, and other tools from number theory, combinatorics, linear algebra, optimization theory and probability theory. We will look at both classical and cutting edge papers in this area. Students are expected to read and present a paper or a small set of papers on a topic, and to construct a homework problem. Optional homework exercises will also be distributed.

Grading

will be based on the student presentation of the papers, creation of homework exercises and class participation.

Prerequisites

Some knowledge of algorithms and basics of probability.

Time and location

The seminar will take place on Tuesdays, 11:00-13:00, in room 114 Shenker.

Announcements

Lecture notes

  1. Tuesday, November 4: Introduction to sublinear time algorithms.
  2. Tuesday, November 11: Quick probability review. More introduction to sublinear time algorithms. (See part II of notes from lecture 1.)
  3. Tuesday, November 18: Some models/results from "Property Testing in Bounded Degree Graphs" (Goldreich, Ron)
  4. Tuesday, November 25: Weakly approximating the edit distance.
  5. Tuesday, December 2: Constant time approximations via local improvements
  6. Tuesday, December 9: Coresets for clustering
  7. Tuesday, December 16: Testing graph isomorphism.
  8. Tuesday, December 23: More testing of bounded degree graphs
  9. Tuesday, December 30: Testing of Clustering
  10. Tuesday, January 6: Testing Random Variables for Independence and Identity
  11. Tuesday, January 13: Testing Basic Boolean Formula
  12. Tuesday, January 13 and 20: Homomorphism Testing
  13. Tuesday, January 20 and 27: Testing Juntas
  14. Tuesday, January 27: Testing Concise Representations

Useful Pointers

List of Possible Topics

click here.

(Tentative) Schedule

Date Topic Speaker
Nov 4 Introduction to course; Introduction to sublinear time Algorithms. Ronitt
Nov 11 Finish introduction. A quick review of probability. Ronitt
Nov 18 Intro to property testing of graphs Yaron Orenstein
Nov 25 Weakly approximating edit distance Yoav Artzi
Dec 2 Constant time approximation algorithms via local improvements Arie Zilberstein
Dec 9 Coresets for clustering Sagi Hed
Dec 16 Graph isomorphism Dima Sotnikov
Dec 23 More testing of bounded degree graphs Roy Kasher
Dec 30 Testing of clustering Asaf Porat
Jan 6 Testing Random Variables for Independence and Identity Avi Kama
Jan 13 Homomorphism Testing + Testing Basic Boolean Formulae Daniel Shahaf + Elya Dolev
Jan 20 Homomorphism Testing + Testing Juntas Daniel Shahaf + Reut Levi
Jan 27 Testing Juntas + Testing Concise Properties Regut Levi + Gilad Tsur