- Instructors: Ronitt Rubinfeld
- Time: TR 2:30-4:00
- Place: 36-155
- 3-0-9 H-Level Grad Credit

**Office hours:** By appointment.

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

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

- References on Markov, Chebyshev and tail inequalities:
- Avrim Blum's Handout on Tail inequalities.
- Avrim Blum's Handout on probabilistic inequalities.
- Jin Yi Cai's book containing derivations of useful probabilistic inequalities (see pages 63-67).
- Fall 2007 6.042 notes -- Lecture 25 and Recitation 23

- Pointers to more recent work on characterizing the properties testable in constant time in the adjacency matrix model: (1) Alon and Shapira A Characterization of the (natural) Graph Properties Testable with One-Sided Error and (2) Alon, Fischer, Newman and Shapira A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
- For future scribes, here is a sample file and the preamble.tex file that it uses.
- Scribe schedule
- Instructions for graders.