On the Existence of Optimal Algorithms

on YouTube ↗50m

" summary

Proposes sum of squares as a candidate “universal” algorithmic template: optimize over degree-d pseudo-distributions (convex, solvable in n^d time) that enforce low‑degree moment/PSD constraints and recover LP/SDP. Claims the hierarchy becomes exact at degree ≈ n, and that for planted clique the known barrier sits at sqrt(n) (no polynomial improvement known for constant d); prior purported lower‑bound proofs fail but degree‑4 analyses still match the sqrt(n) threshold.

AI-written summary · about

" chapters (17)

1. 0:00Introduction to the topic
2. 1:05Historical context
3. 5:46Making algorithms boring
4. 7:50Characterizing easy problems
5. 10:02Goal of the talk
6. 12:02Domain of optimization
7. 14:56The role of convexity
8. 18:00Relaxation methods
9. 20:00Sum of squares algorithm
10. 22:13Bayesian vs frequentist
11. 25:01Computational perspectives
12. 27:50Computational Bayesianism
13. 30:20Understanding pseudo-distributions
14. 34:08Generalizing pseudo-distributions
15. 36:46Planted clique problem
16. 39:04Limitations of SOS
17. 42:31Lessons and future work