Teaching

Introduction to Property Testing

Lecture 1 (8/11) : Introduction and the toy problem of Majority (pages 6-8 from the book).

Lecture 2 (15/11): Continued Majority, symmetric properties and the SORTED problem (pages 8-12 ).

Lecture 3 (22/11): Formal definition of property testing, POTs (pages 13-21).

Lecture 4 (29/11): Testing Group Homomorphism (pages 40-45).

Lecture 5 (6/12): Testing Monotonicity (pages 69-75, 77-80).

Lecture 6 (13/12): Oded's talk (Dictatorship testing, a taste of Junta testing and learning implies testing).

Lecture 7 (20/12): The Dense Graph Model - testing Bipartiteness (pages 167-168, 180-183).

Lecture 8 (27/12): The Dense Graph Model - testing triangle freeness.

Lecture 9 (03/01): The Bounded Degree Model - testing Connectivity.

Lecture 10 (10/01): The Bounded Degree Model - testing Bipartiteness (the rapidly mixing case).

Lecture 11 (17/01): Continued testing Bipartiteness.

Lecture 12 (24/01): Testing Minor-closed properties with two-sided error (partition oracles).

Assignment #1: Exercise 1.1 and Exercise 1.3. Due date: 6/12/18

Assignment #2: Exercise 4.2 and Exercise 4.3. Due date: 20/12/18

Assignment #3: Exercise 8.5 and Exercise 8.7. Due date: 03/01/19

Assignment #4: Exercise 9.2 and Exercise 9.10. Due date: 07/02/19