Games and Grothendieck's Tensor Norms
summary
A concrete dictionary maps game values to tensor norms: classical correlations = epsilon norm, quantum correlations = min norm, and quantum XOR values equal a gamma2 SDP; Grothendieck then gives a bounded ratio (Grothendieck constant ≈ 1.7, equals √2 for two‑dim Hilbert case). Operator‑space/Banach techniques and SDPs produce unbounded three‑party violations* and explicit rank‑one/OH games that show naive parallel repetition can fail; a rank‑one square‑root construction matches the norm exactly.
AI-written summary · about
chapters (17)
- 0:00Intro
- 1:22Plan
- 2:51Basic Banach Spaces
- 12:11Largest and smallest tensor norm
- 19:36Tsirelson's interpretation
- 20:40Joint Probabilities
- 22:23Optimal value
- 25:59Joint Correlations
- 29:46Joint quantum probabilities and correlations
- 32:08Separation of convex sets
- 33:10Grothendieck's Theorem for correllations
- 37:43Grothendieck's Theorem for correlations
- 45:03Tool: Operator Space Theory
- 48:45Dictionary for values of games'
- 52:14Quantum games
- 54:05Operator space interpretation
- 56:39Application of square root
related talks
20mWith a Few Square Roots, Quantum Computing is as Easy as Pi
32mOptimal Quantum Programs
01h 31mTutorial 1: The GCT Chasm I
01h 04mExplicit SoS Lower Bounds from (Small-Set) High Dimensional Expanders
01h 28mTutorial 4: GCT and Matrix Multiplication
01h 01mTrue Complexity of Multilinear Systems
39mStructure of the Fourier Spectrum of Boolean Functions and Complexity
23mKarchmer-Wigderson Games for Hazard-free Computation