The Edge of Tractability: Unique Games vs Sum of Squares

on YouTube ↗01h 03m

" summary

Argues that the sum-of-squares meta-algorithm formally captures the strongest known approximation methods, gives certificates (low-degree SOS proofs) that rule out sparse nonexpanding sets, and reproduces all known hard instances where simpler meta-algorithms fail. Shows an efficient SDP procedure that finds these certificates or outputs a pseudo-distribution witness, yields algorithms up to 2^{n^ε} time for small-set expansion, connects the needed junta size to counts of small eigenvalues, and leaves Unique Games unresolved but tightly constrained.

AI-written summary · about

" chapters (13)

1. 0:00Optimization and complexity
2. 1:50Meta-algorithms in research
3. 5:30UGC and sum-of-squares
4. 8:50Unique games conjecture
5. 13:24Predictions and implications
6. 17:36Meta-algorithm exceptions
7. 20:31Functions on the hypercube
8. 25:36Sum-of-squares meta-algorithm
9. 34:34Improving the algorithm
10. 40:53Complexity transitions
11. 44:24Eigenvalues and expansion
12. 49:29The SOS proof system
13. 58:41Duality and conclusions