A Positivity-First Approach to Sum-of-Squares Over the Hypercube
summary
New method builds pseudoexpectations as actual random symmetric tensors conditioned to satisfy SOS linear constraints, forcing positive semidefiniteness by construction rather than proving it afterward. Applied to the SK/GOE hypercube problem, the technique reproduces earlier spectral barrier hardness (largest eigenvalue ≈ 2 versus true optimum ≈ 1.5) and extends prior work from degree‑4 to a degree‑six lower bound, using forest/möbius combinatorics to enforce ideal constraints.
AI-written summary · about
chapters (11)
- 0:00Intro
- 6:30Spectral Bound
- 11:49Pseudo Expectations
- 14:30Lower Bounds
- 16:07Pseudo Calibration
- 17:34Why is this so hard
- 19:30PositivityFirst Approach
- 22:21Diagrammatic Interpretation
- 23:33Coefficients
- 25:04Results
- 27:08Questions
related talks
01h 06mLP/SDP Hierarchies and Sum of Squares Proofs 4
39mFast Spectral Algorithms from Sum-of-Squares Analyses
01h 01mLP/SDP Hierarchies and Sum of Squares Proofs 1
59mOptimizing Noncommutative Polynomials: The SYK Model
59mLP/SDP Hierarchies and Sum of Squares Proofs 3
47mPlanted Clique, Sum-of-Squares and Pseudo-Calibration
29mSum Of Squares Lower Bounds Versus Low-Degree Polynomial Lower Bounds
39mOptimization over the Hypercube via Sums of Nonnegative Circuit Polynomials