6.896 Sublinear Time Algorithms

Instructors: Ronitt Rubinfeld and Eli Ben- Sasson
Time: TR 1:00-2:30
Place: 36-156
3-0-9 H-Level Grad Credit
Brief Course description: This course will focus on the design of algorithms that are restricted to run in sublinear time, and thus can view only a very small portion of the data. The study of sublinear time algorithms has been applied to problems from a wide range of areas, including algebra, graph theory, geometry, string and set operations, optimization and probability theory. This course will introduce many of the various techniques that have been applied to analyzing such algorithms. (Slightly more detailed course announcement.)

Office hours: By appointment.


Homework 3 has been posted below.


Lecture Notes

  1. 09/9: Introduction. Examples of deterministic sublinear time algorithms. Example of a property tester.
  2. 09/14: Definition of property tester, bounded degree graph testing model, testing connectivity.
  3. 09/21: Finishing off testing connectivity, estimating the number of connected components.
  4. 09/23: Estimating the minimum spanning tree weight.
  5. 09/28: Bipartiteness testing.
  6. 09/30: Finish proof of bipartiteness tester. Discussion of tester for first order graph properties.
  7. 10/5: Tester for triangle-free property: Szemeredi's Regularity Lemma, and finding triangles in regular tri-partite graphs.
  8. 10/7: Finish tester for triangle-free property. Start lower bound in terms of epsilon.
  9. 10/12: Finish lower bound for triangle-free property.
  10. 10/14: Max-cut.
  11. 10/19: Finish max-cut. Start weak approximations of edit distance.
  12. 10/21: Weak approximations of edit distance (no scribe notes). (Guest lecturer: Rahul Sami)
  13. 10/26: Finish weak approximations of edit distance (no scribe notes). (Guest lecturer: Rahul Sami)
  14. 10/28: Clustering. (Guest lecturer: Rahul Sami)
  15. 11/2: Matrix multiplication.
  16. 11/4: Lower bounds for testing low density parity check codes and 3CNF formulas.
  17. 11/9: finish lower bound.
  18. 11/16: linearity testing.
  19. 11/18: preliminary draft.
  20. 11/23: Locally decodable error-correcting codes. (Guest lecturer: Iordanis Kerenidis)
  21. 11/30: Monotonicity testing.
  22. 12/2: Proximity of distributions.
  23. 12/7: Proximity of distributions. (no scribe notes)
  24. 12/9: Testing uniformity of monotone distributions. (no scribe notes)


  1. If you are not familiar with Markov, Chebyshev and Hoeffding/Chernoff bounds, please read about them in one or more of the descriptions given in useful pointers.
  2. Homework 1 (Due October 7). hint Solution to problem 6. Solution to problem 7.
  3. Homework 2 (Due November 16). (11/9) Note update to due date and to homework set. Solution to problem 1. Solution to problem 3.
  4. Homework 3 (Due November 30). Solutions .

Some useful pointers: