Sum Of Squares Lower Bounds Versus Low-Degree Polynomial Lower Bounds

on YouTube ↗29m

" summary

Compares low-degree polynomials and Sum-of-Squares via pseudo-calibration and gives a concrete inequality: a low-degree polynomial with mean C on the planted model and variance ≤1 forces the variance of the pseudo-expectation ≥ C^2, so SoS lower bounds subsume checking the entry for one but require PSD control of the whole moment matrix. Highlights gaps: planted clique using independent inclusion K/N vs exact-K planted model, Tensor PCA issues with dense ±1 vectors, and specific bounds like M ≤ N^{3/2} SoS lower bound versus low-degree M ≤ N^2; tweaks to pseudo-calibration yield SoS certification lower bounds for sparse independent set.

AI-written summary · about

" chapters (17)

1. 0:00Intro
2. 0:24Outline
3. 0:55Distinguishing Problems
4. 1:32Planted Clique Example
5. 2:30Low-Degree Polynomial Framework
6. 3:00Sum of Squares (SoS) Framework
7. 6:31Background: Fourier Analysis and Low-Degree Projections
8. 7:40Goal: Assigning Pseudo-expectation Values
9. 9:46Pseudo-Calibration
10. 13:36Canonical Example: Planted Clique
11. 18:38Summary
12. 20:53Evidence for the Low-Degree Conjecture
13. 21:26Delicateness of Current Sos Lower Bounds
14. 23:20Example: Parallel Pancakes
15. 25:52Special Case: A = {-1,1}
16. 26:46Example: Independent Set on Sparse Graphs
17. 28:22Open Problem: Quiet Planting

" related talks

• 47mPlanted Clique, Sum-of-Squares and Pseudo-CalibrationAnkur Moitra · Random Instances and Phase Transitions (Simons Institute, 2016)
• 01h 06mLP/SDP Hierarchies and Sum of Squares Proofs 4Ankur Moitra, Pablo Parrilo · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 11mUnderstanding Statistical-to-Computational Gaps via Low-Degree PolynomialsAlex Wein · Meet the Fellows Welcome Event
• 01h 12mPedagogical Talk: Frameworks for Information-Computation TradeoffsTselil Schramm · Computational Phase Transitions (Simons Institute, 2020)
• 01h 11mPedagogical Talk: Failure of Low-Degree PolynomialsAlex Wein · Computational Phase Transitions (Simons Institute, 2020)
• 01h 01mLP/SDP Hierarchies and Sum of Squares Proofs 1Ankur Moitra, Pablo Parrilo · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 31mA Positivity-First Approach to Sum-of-Squares Over the HypercubeTim Kunisky · Computational Phase Transitions (Simons Institute, 2020)
• 01h 04mFrom Proofs to Algorithms for Machine Learning ProblemsDavid Steurer · Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017)