CS294: Property Testing (F2016)

Basics


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.

Prerequisites


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.

Requirements


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:

Assignments


None.

Schedule


# 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

  • 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

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

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

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:

  • 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.