Unique Games and Expansion

on YouTube ↗45m

" summary

Gives concrete algorithms: when low-degree sum-of-squares proofs certify small-set expansion, a degree-2 SoS relaxation plus a conditioning-and-sample rounding produces a labeling that turns a 90%‑satisfiable affine Unique Games instance on an expander into ≈50% satisfied constraints. Extends to certified global hypercontractivity using higher-degree SoS and a preprocessing that preserves pairwise independence after conditioning. Targets Johnson/Grassmann-style graphs, explains why certain Johnson-graph regimes remain plausible hard instances (49% vs 1% hardness) and what structural witnesses make them easy or hard.

AI-written summary · about

" chapters (15)

1. 0:00Intro
2. 0:49Propagation
3. 2:41History of Unique Games
4. 5:41Johnson graphs
5. 8:09UG on Expanders: Uniqueness
6. 12:57Sum-of-Squares: Distribution view
7. 14:21Expander Algorithm from Uniqueness
8. 15:23Analysis of Expander Algorithm
9. 21:30Small Set Expanders
10. 25:15Analysis of SSE Algorithm
11. 31:26Algorithm on Globally Hypercontractive Graphs
12. 38:12Algorithms for UG on Non-Globally Hypercontractive (Johnson) Graphs?
13. 40:37Summary
14. 40:47Hard instances for UG?
15. 41:52New Tools for Rounding SoS