## 6.896 Sublinear Time Algorithms

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

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