PCPs and Global Hyper-contractivity 1
summary
Explains that the PCP theorem is recast as a small-alphabet label cover hardness (constant k, gap 1 vs 1−ε), develops the Unique Games Conjecture as the ultimate structured gap, and reports the recent 2-to-1 games NP-hardness result that achieves small-soundness (yes-case near 1 vs no-case ≈ε) and yields concrete gaps (e.g., proving hardness for clique down to ~0.29 vs ε). Uses Boolean-analysis tools (hypercontractivity, invariance principle), long-code/local-testers, and the Grassmann graph to escape small-set-expansion barriers; constructions produce the intended hardness gaps.
AI-written summary · about
chapters (9)
- 0:00Introduction to PCP
- 1:40The basic PCP theorem
- 9:45Label cover and reformulations
- 17:02Strengthening the PCP theorem
- 21:10Unique games conjecture
- 30:13Analytical consequences
- 37:30Two-to-one games
- 44:07Locally testable codes
- 53:28Small cell expansion
related talks
41mSpotlight Talks
22mQuantum space, ground space traversal, and how to embed multi-prover...
46mInteractive Proofs for Verifying Machine Learning
30mUnfamiliar Terrain
25mQuantum NP and Beyond
52mKernelized Multiplicative Weights for 0/1-Polyhedral Games:...
34mWhen Is Offline Two-Player Zero-Sum Markov Game Solvable?
45mAGT and Machine Learning