Crash Course on Probabilistically Checkable Proofs (PCP): Parallel Repetition
Talkat Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020) · 2020-08-19..08-28
summary
Parallel repetition takes a projection game and tensorizes it so questions are d-tuples; the basic PCP route uses this to amplify a 1 versus 1−ε gap to 1 versus ≈0. Raz proves exponential decay of value but also shows strong parallel repetition is false: the odd-cycle counterexample has single-game value 1−1/m yet repeated value ≈(1−1/m^2)^d, not (1−1/m)^d. SDP relaxations explain the gap, and the Raz-based constructions produce tilings of R^d with surface area ~√d, so the counterexamples and geometric foams work.
AI-written summary · about
chapters (17)
- 0:00Introduction to PCPs
- 1:04Basic PCP theorem
- 3:05Tightness and 3-SAT
- 6:00From Label Cover to Strong PCP
- 7:55Label cover definition
- 12:12Hardness of label cover
- 15:12Two-player game view
- 18:48Parallel repetition
- 23:32Parallel repetition theorem
- 27:35Tightness in repetition
- 30:27Unique games and max-cut
- 34:16Unique games conjecture
- 37:28Strong parallel repetition
- 42:39Odd cycle game
- 45:55Geometric interpretation
- 58:42Necessity of the two
- 1:02:28Questions and discussion