6.896 Sublinear Time Algorithms

Instructors: Ronitt Rubinfeld
Time: TR 2:30-4:00
Place: 36-155
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.

Announcements

Handouts

Lecture Notes

  1. Tuesday, 2/6: Introduction. Testing closeness of distributions. latex source
  2. Thursday, 2/8: More testing closeness of distributions. latex source
  3. Tuesday, 2/13: Finish testing closeness of distributions in L1 distance. Testing monotone distributions. latex source
  4. Thursday 2/15: Testing properties of monotone distributions. latex source
  5. Tuesday 2/20: No class. MIT "Monday".
  6. Thursday 2/22: Testing properties of monotone distributions. latex source
  7. Tuesday 2/27: Finish last details of testing properties of monotone distributions. Estimating the entropy. latex source
  8. Thursday 3/1: Estimating the number of distinct values. latex source
  9. Tuesday 3/6: Lempel Ziv latex source
  10. Thursday 3/8: More Lempel Ziv. Testing whether a graph is connected. latex source
  11. Tuesday 3/13: Estimating the number of connected components. Approximating the minimum spanning tree weight. latex source
  12. Thursday 3/15: Formal definition of property testers. Begin testing bipartiteness of a dense graph. latex source
  13. Tuesday 3/20: Testing bipartiteness of a dense graph. latex source
  14. Thursday 3/22: Regular partitions. Counting triangles. Regularity Lemma. latex source
  15. Tuesday 4/3: Proof of Regularity Lemma. latex source
  16. Thursday 4/5: Testing triangle-freeness. latex source See below for pointers on more recent work.
  17. Tuesday 4/10: Lower bound on epsilon for testing triangle-freeness. latex source
  18. Thursday 4/12: Lower bound on epsilon for testing triangle-freeness. Graph Isomorphism. latex source
  19. Tuesday 4/17: MIT holiday. No class. Day after Patriot's day.
  20. Thursday 4/19: Graph Isomorphism. latex source
  21. Tuesday 4/24: Clustering latex source
  22. Thursday 4/26: More clustering. latex source
  23. Tuesday 5/1: Testing functions: Monotonicity testing. latex source
  24. Thursday 5/3: More monotonicity testing. Begin linearity testing. latex source
  25. Tuesday 5/8: Linearity testing. latex source
  26. Thursday 5/11: Estimating sums of powers of degree 1 Fourier Coefficients. Weak estimations of the largest degree 1 Fourier Coefficient. latex source
  27. Tuesday 5/14: Linear threshold function testing. latex source
  28. Tuesday 5/8: Class project presentations.

Homeworks

  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 below in "useful pointers".
  2. Problem set 0 (don't turn in -- just for review)
  3. Problem set 1 (due February 27) last modified 2/20 10:00 pm.
  4. Problem set 2 (due March 15) last modified 3/14 6:00 am. Hint for problem 2 . Hint for problem 3 .
  5. Problem set 3 (due April 5)
  6. Problem set 4 (due April 24) last modified 4/10 noon.
  7. Problem set 5 (due May 10, but optional) last modified 5/1 2:15pm.

Some useful pointers: