CS294: Property Testing (F2016)


Instructor(s): Alessandro Chiesa, Igor Shinkar
Teaching Assistant(s): none
Time: W 13.00-16.00 (with food at half-time!)
Location: 380 Soda Hall
Office Hours: fix appointment via email (to Alessandro or Igor)

Course Description

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:

  • testing properties of boolean functions (linearity, dictators, juntas),
  • testing properties of real functions (monotonicity, submodularity),
  • testing algebraic properties of functions (low-degreeness in various settings),
  • lower bounds (via communication complexity, via yes/no instances),
  • testing graph properties (in the dense graph model, regularity, bipartiteness, k-colorability, triangle-freeness)

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.

Reading and Resources

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:




# Date Topic Reading
1 2016.08.24




2 2016.08.31

Boolean Functions 1



3 2016.09.07

Boolean Functions 2


Additional on testing dictators and their applications:

Additional on juntas:

Additional on PCP applications of Fourier analys:

4 2016.09.14

Boolean Functions 3

  • testing linear transformations
  • regime of large agreement / small distance
    • black-box use of BLR with union bound
    • directly via majority decoding
  • regime of small agreement / large distance



5 2016.09.21

Real Functions


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



Initial uses of low-degree testing for probabilistic checking:

7 2016.10.05

Low-Degree Polynomials 2

  • connection from total degree to individual degree
  • bivariate polynomials (tighter analysis via Bézout)



8 2016.10.12

Low-Degree Polynomials 3



9 2016.10.19

Tensor Product Codes


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



X 2016.11.02

No class.

No class.

11 2016.11.09

Graph Properties 1


More on upper and lower bounds for bipartiteness:

12 2016.11.16

Graph Properties 2



X 2016.11.23

No class.

No class.

13 2016.11.30

Research project presentations


  • 1310-1330: HKN Evaluations
  • 1330-1350: Peter Manohar, m-variate low degree testing
  • 1350-1410: Yuting Wei, testing shape restriction of discrete distribution
  • 1410-1430: Aaron Schild, local computation algorithms

10-min break

  • 1440-1500: Pratyush Mishra, PCP proof composition
  • 1500-1520: Pasin Manurangsi, (2-eps) vertex cover hardness
  • 1520-1540: Xingyou Song, submodular testing and optimization
  • 1540-1600: Daniel Shaw, a combinatorial characterization of testable graph properties and regularity

later on

  • Benjamin Weitz, another proof of the BLR test: generalizing to different domains
X 2016.12.07

No class.

No class.