LP/SDP Hierarchies and Sum of Squares Proofs 4

on YouTube ↗01h 06m

" summary

Presents a concrete SOS-based algorithm: a quasi-polynomial time N^{O(log N / ε^2)} method that approximates the max of a degree‑4 polynomial (M defined as N^2×N^2 PSD) by producing a unit vector x with value within ε of the pseudoexpectation. Key tools are pseudoexpectation operators and moment‑based rounding (never sampling). Analysis shows conditioning cuts entropy by Ω(ε^2) per round, so after O(log N / ε^2) conditionings one finds a feasible x; relates to separable quantum states and de Finetti symmetry.

AI-written summary · about

" chapters (8)

1. 0:00Introduction
2. 0:58Pseudo expectation
3. 9:17Polynomial optimization
4. 16:43Separable states
5. 26:18Unit vectors
6. 32:23Too small
7. 37:33Quadratic form
8. 53:40Discussion

" related talks

• 31mA Positivity-First Approach to Sum-of-Squares Over the HypercubeTim Kunisky · Computational Phase Transitions (Simons Institute, 2020)
• 39mFast Spectral Algorithms from Sum-of-Squares AnalysesTselil Schramm · Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017)
• 29mSum Of Squares Lower Bounds Versus Low-Degree Polynomial Lower BoundsAaron Potechin · Rigorous Evidence for Information-Computation Trade-offs
• 47mPlanted Clique, Sum-of-Squares and Pseudo-CalibrationAnkur Moitra · Random Instances and Phase Transitions (Simons Institute, 2016)
• 44mMixture Models, Robustness, and Sum of Squares ProofsJerry Li · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 27mWeak Decoupling, Polynomial Folds, and Approximate Optimization over the SphereVijay Bhattiprolu · Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017)
• 59mOptimizing Noncommutative Polynomials: The SYK ModelRyan O'Donnell · Rigorous Evidence for Information-Computation Trade-offs
• 45mSum of Squares SDP Relaxations on Random TensorsPrasad Raghavendra · Random Instances and Phase Transitions (Simons Institute, 2016)