7. Property testing, PCPPs, and CSPs🔗

Function and string property testing, probabilistically checkable proofs of proximity, finite constraint-satisfaction problems, their exact complexity boundaries, and the finite Fourier analysis underlying Håstad's tests.

1. 7.1. Dictator testing
2. 7.2. Probabilistically Checkable Proofs of Proximity
3. 7.3. CSPs and computational complexity
4. 7.4. Håstad’s hardness theorems
5. 7.5. Exercises and notes