This course offers a graduate introduction to property testing, which studies how to detect structural properties of huge objects by only examining 'local views' of these objects. Property testing has its roots in the program checking and PCP literature, but has evolved into a thriving area of its own standing between algorithms and complexity theory; results are often characterized by relatively simple algorithms that are supported by a fairly complex analysis. (Sometimes invoking powerful results from additive combinatorics, extremal graph theory, and algebraic geometry.)
Topics covered include:
Emphasis is on getting students up to speed for research in the area; lectures will often contain open problems or suggestions for future research.
The Piazza website is here.
The official prerequisite is CS 170 (or equivalent). All students with "mathematical maturity" (ease with proofs, algorithms, elementary number theory, and discrete probability) and curiosity about property testing are welcome. Reviewing standard probability inequalities is helpful.
Completing the course requires regular attendance/participation and a research project. Grading will be based 30% on attendance/participation, and 70% on the research project.
This course has no required textbook, but much of the material covered in class can be found online; we give specific references for each lecture. In addition, the following online resources could be helpful:
None.
# | Date | Topic | Reading |
---|---|---|---|
1 | 2016.08.24 | Introduction
|
Main:
Additional: |
2 | 2016.08.31 | Boolean Functions 1
|
Main
Additional:
|
3 | 2016.09.07 | Boolean Functions 2
|
Main: Additional on testing dictators and their applications:
Additional on juntas:
Additional on PCP applications of Fourier analys: |
4 | 2016.09.14 | Boolean Functions 3
|
Main: Additional:
|
5 | 2016.09.21 | Real Functions
|
Main:
More on testing monotonicity:
Testing real functions for Lp distances: Other cool topics about boolean functions that we do not have time to cover:
|
6 | 2016.09.28 | Low-Degree Polynomials 1
|
Main:
Additional:
Initial uses of low-degree testing for probabilistic checking: |
7 | 2016.10.05 | Low-Degree Polynomials 2
|
Main:
Additional: |
8 | 2016.10.12 | Low-Degree Polynomials 3
|
Main:
Additional: |
9 | 2016.10.19 | Tensor Product Codes
|
Main:
Positive results for robust testability 2-wise tensor products:
Negative results for robust testability 2-wise tensor products:
Other cool topics that we do not have time to cover:
|
10 | 2016.10.26 | Lower Bounds
|
Main:
Additional: |
X | 2016.11.02 | No class. |
No class. |
11 | 2016.11.09 | Graph Properties 1
|
Main:
More on upper and lower bounds for bipartiteness: |
12 | 2016.11.16 | Graph Properties 2
|
Main:
Additional:
|
X | 2016.11.23 | No class. |
No class. |
13 | 2016.11.30 | Research project presentations |
Schedule:
10-min break
later on
|
X | 2016.12.07 | No class. |
No class. |