Planted Clique, Sum-of-Squares and Pseudo-Calibration
summary
Shows that level-D Sum-of-Squares cannot rule out planted cliques much below √n: the integrality gap is ≥ n^{1/2 - O(√D / log n)} for D = o(log n), so any SOS run in n^{O(D)} time still fails near the √n barrier. The construction builds a pseudo-calibration recipe that fixes low-degree discrepancies by prescribing Fourier-truncated pseudoexpectation coefficients (truncate at τ ≈ log n), then proves positivity by an approximate PSD factorization via separators of the SOS moment matrix.
AI-written summary · about
chapters (10)
- 0:00Introduction to the problem
- 0:35Planted clique background
- 7:35Sum of squares hierarchy
- 14:29Hierarchy comparisons
- 16:27Lower bounds against SOS
- 18:16Pseudo-calibration technique
- 26:54Mechanics of pseudo-calibration
- 33:33Proof skeleton and truncation
- 34:15Verification and challenges
- 40:44Q&A session
related talks
29mSum Of Squares Lower Bounds Versus Low-Degree Polynomial Lower Bounds
01h 06mLP/SDP Hierarchies and Sum of Squares Proofs 4
31mA Positivity-First Approach to Sum-of-Squares Over the Hypercube
59mLP/SDP Hierarchies and Sum of Squares Proofs 3
01h 01mLP/SDP Hierarchies and Sum of Squares Proofs 1
27mWeak Decoupling, Polynomial Folds, and Approximate Optimization over the Sphere
01h 04mExplicit SoS Lower Bounds from (Small-Set) High Dimensional Expanders
39mFast Spectral Algorithms from Sum-of-Squares Analyses