PCPs and Global Hyper-contractivity 3
summary
States the Grassmann expansion theorem: any r‑ε global subset of the Grassmann graph has edge expansion tending to 1. Proof framework builds the degree (junta) decomposition as eigenspaces of the adjacency operator, reduces expansion to a level‑d mass bound, then analyzes the d=1 case: either a Poisson‑type few heavy points (yielding a hyperplane with much higher density) or nontrivial four‑wise correlations, whose fourth‑moment/Fourier analysis forces a dense hyperplane. Method extends to the p‑biased cube and yields p‑biased hypercontractivity tools with PCP, sharp‑threshold, extremal and coding applications.
AI-written summary · about
chapters (12)
- 0:00PCPs and global hyper-contractivity
- 0:44Grassmann graph expansion theorem
- 4:27Boolean functions on Grassmann graph
- 15:20Small sets expansion via eigenvalues
- 23:29Expansion theorem level inequalities
- 26:30Degree-1 functions and Boolean behavior
- 35:53Degree-1 expansion theorem proof
- 41:11Expansion theorems beyond Grassmann
- 47:02Hypercontractivity in p-biased cube
- 53:57Global hypercontractivity applications
- 57:36Future directions and open questions
- 58:02Q&A
related talks
41mSpotlight Talks
22mQuantum space, ground space traversal, and how to embed multi-prover...
52mKernelized Multiplicative Weights for 0/1-Polyhedral Games:...
46mSpectral Partitioning for Metrics (And NNs Too)
59mAspects of Coulomb Gases
48mLearning by Local Entropy Maximization
17mData-Parallel Differentiation by Optic Composition
30mUnfamiliar Terrain