- Instructors: Ronitt Rubinfeld
- Time: TR 11:00-12:30
- Place: 24-115
- 3-0-9 H-Level Grad Credit

** Course Requirements: **
Homework sets (35%). Scribe notes (25%). Project (25%). Class participation
(15%). As part of class participation, students will be asked to help
with grading of assignments and writing solution sets.

** Prerequisites: **
6.045 or 6.046 or equivalent.

- (02/07) Lecture 1: Overview. Diameter of a point set. Approximating the number of connected components. Approximate Minimum Spanning Tree. [scanned notes] [scribe notes] [latex file for scribe notes]
- (02/14) Lecture 2: Approximating the average degree in sub-linear time. [scanned notes] [scribe notes draft] [latex file for scribe notes draft]
- (02/16) Lecture 3: Finish approximating the average degree (see notes from last time). Approximating vertex cover in sub-linear time via local distributed algorithms. [scanned notes] [scribe notes] [latex file for scribe notes]
- (02/23) Lecture 4: Continue approximating vertex cover in sub-linear time via local distributed algorithms. Approximating maximal matching via simulating greedy algorithms. [scanned notes] [scribe notes] (draft) [latex file for scribe notes]
- (02/28) Lecture 5: Property testing. Testing planarity. Partition oracles. [scanned notes] [scribe notes ] [latex file for scribe notes]
- (03/2) Lecture 6: Property testing of distributions. Testing uniformity. [scanned notes] [scribe notes] [latex file for scribe notes]
- (03/7) Lecture 7: Property testing of distributions. More on uniformity. [scanned notes -- same as lecture 6] [scribe notes] [latex file for scribe notes]
- (03/9) Lecture 8: Property testing of distributions. Lower bound techniques: Collisions, Information theory, Poissonization. [scanned notes] [scribe notes ] [latex file for scribe notes]
- (03/16) Lecture 9: Property testing of distributions. Testing closeness of two unknown distributions. Testing and learning monotone distributions. [scanned notes] [scribe notes ] [latex file for scribe notes]
- (03/21) Lecture 10: Testing and learning monotone distributions. [scanned notes] [scribe notes ] [latex file for scribe notes]
- (03/21) Lecture 11: Hypothesis testing. [scanned notes] [scribe notes ] [latex file for scribe notes]
- (04/4) Lecture 12: Learning and and testing PBDs. [scanned notes] [scribe notes ] [latex file for scribe notes]
- (04/6) Lecture 13: Testing Monotonicity. [scanned notes] [scribe notes ] [latex file for scribe notes]
- (04/11) Lecture 14: Testing Monotonicity under L1 distance. Begin testing properties of dense graphs (bipartiteness). [scanned notes] [scribe notes ] [latex file for scribe notes]
- (04/13) Lecture 15: Testing bipartiteness of dense graphs. [scanned notes] [scribe notes ] [latex file for scribe notes]
- (04/20) Lecture 16: Local computation algorithms for maximal independent set (guest lecture by Anak Yodpinyanee!). [notes] [scribe notes ] [latex file for scribe notes]
- (04/25) Lecture 17: The Szemeredi regularity lemma -- begin use in property testing of dense graphs. [scanned notes] [scribe notes ] [latex file for scribe notes]
- (04/25) Lecture 18: Using the Szemeredi regularity lemma for testing triangle-freeness. (see notes from lecture 17)
- (05/2) Lecture 19: Lower bounds from communication complexity. [scanned notes] [scribe notes ] [latex file for scribe notes]
- (05/4) Lecture 20: Lower bounds based on Yao's method. [scanned notes] [scribe notes ] [latex file for scribe notes]
- (05/9) Lecture 21: Lower bounds based arithmetic number theory. [scanned notes] [scribe notes ] [latex file for scribe notes]
- (05/16) Lecture 22: Linearity testing. [scanned notes] [scribe notes ] [latex file for scribe notes]

- If you are not familiar with Markov, Chebyshev and Hoeffding/Chernoff bounds, please read about them (e.g., in a description given below in "useful pointers").
- Problem set 0 (Don't turn in -- just for review.) Last modified Feb 3, 2017.
- Problem set 1 Due Feb 23, 2017 (note new deadline!). Last modified Feb 20, 2017.
- Problem set 2 Due March 2, 2017. Last modified Feb 23, 2017.
- Problem set 3 Due March 9, 2017. Last modified March 4, 2017.
- Problem set 4 Due March 21, 2017. (This overrides the due date written in the file). Last modified March 9, 2017.
- Problem set 5 Due April 6, 2017. Last modified March 22, 2017.
- Problem set 6 Due April 13, 2017. Last modified April 6, 2017.
- Problem set 7 Due April 20, 2017. Last modified April 6, 2017.
- Problem set 8 NOW DUE May 2, 2017. Last modified April 25, 2017.
- Problem set 9 Due May 9, 2017. Last modified May 2, 2017.

- References on Markov, Chebyshev and tail inequalities:
- Avrim Blum's Handout on Tail inequalities.
- Avrim Blum's Handout on probabilistic inequalities.
- Fall 2007 6.042 notes -- Lecture 25 and Recitation 23

- For future scribes, here is a sample file and the preamble.tex file that it uses. Here are some tips for scribes.
- Scribe schedule
- Grading schedule
- Instructions for graders.
- Project ideas
- Solutions (password required).