Sum of Squares SDP Relaxations on Random Tensors

on YouTube ↗45m

" summary

Proves a concrete runtime vs. guarantee tradeoff: a degree-d Sum-of-Squares proof (computed in time n^{O(d)}) certifies strictly better upper bounds on the injective norm of random k‑tensors than the naive spectral bound, interpolating between polynomial time (certify O(n)) and brute force (certify O(√n)) as d grows. Construction uses a symmetrized tensor spectral matrix and the trace method to bound its norm, yields subexponential refutations for random k‑LIN, and matches known SOS lower bounds up to logs.

AI-written summary · about

" chapters (7)

1. 0:00Introduction to CSPs
2. 3:08Planting and hardness
3. 7:17Sum of squares results
4. 12:28Injective tensor norms
5. 17:24Spectral symmetrization
6. 25:18Trace method for bounds
7. 36:15Open problems and closing

" related talks

• 42mTight Semidefinite Programming Relaxations for Polynomial OptimizationJiawang Nie · Hyperbolic Polynomials and Hyperbolic Programming
• 39mFast Spectral Algorithms from Sum-of-Squares AnalysesTselil Schramm · Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017)
• 01h 01mLP/SDP Hierarchies and Sum of Squares Proofs 1Ankur Moitra, Pablo Parrilo · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 01h 06mLP/SDP Hierarchies and Sum of Squares Proofs 4Ankur Moitra, Pablo Parrilo · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 01h 12mPedagogical Talk: Frameworks for Information-Computation TradeoffsTselil Schramm · Computational Phase Transitions (Simons Institute, 2020)
• 29mSum Of Squares Lower Bounds Versus Low-Degree Polynomial Lower BoundsAaron Potechin · Rigorous Evidence for Information-Computation Trade-offs
• 59mLP/SDP Hierarchies and Sum of Squares Proofs 3Ankur 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)