PCPs and Global Hyper-Contractivity 2
summary
Starts by showing a long-code with a simple noise tester (one coordinate kept with probability 1−ε) that is complete but far too large to be useful, contrasts it with the Hadamard code which needs three queries, then constructs the Grassman graph encoding subspace-restricted linear functions and a 2-query test checking agreement on (l−1)-dimensional intersections. The graph fails small-set expansion via “zoom-in” (subspaces containing a point) and “zoom-out” (subspaces inside a hyperplane) examples, so soundness is salvaged only by proving a pseudorandom/global expansion theorem and extracting local linear structure via random linear-function sampling.
AI-written summary · about
chapters (16)
- 0:00Introduction to part two
- 1:52Conventional wisdom for 2-to-1 games
- 8:00Limitations of long-code
- 9:29Hadamard code and tester
- 12:26Introducing Grassmann code
- 16:29Testing Grassmann code
- 22:08Soundness challenges in Grassmann test
- 29:14Non-expanding sets in Grassmann graph
- 33:44Refuting optimistic soundness
- 36:58Relaxing soundness for use
- 38:00Global pseudorandomness in Grassmann graph
- 44:29Simplifying expansion theorem
- 48:51Connecting pseudorandomness to expansion
- 53:06Proof sketch of main theorem
- 59:41Summary and future work
- 1:00:02Question and answer session
related talks
22mQuantum space, ground space traversal, and how to embed multi-prover...
52mGeneralization in the representations and computations of frontier language models.
41mSpotlight Talks
46mInteractive Proofs for Verifying Machine Learning
30mUnfamiliar Terrain
48mLearning by Local Entropy Maximization
01h 02mOut-of-Distribution Generalization as Reasoning: Are LLMs Competitive?
57mA Simple Quantum Sketch With Applications to Graph Algorithms