Weak Decoupling, Polynomial Folds, and Approximate Optimization over the Sphere
Talkat Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017) · 2017-11-06..11-09·
summary
Claims a concrete tradeoff: powering a degree-D polynomial to degree Q and using SOS yields an n^{Q} time algorithm that achieves roughly an n / Q^{Q/2} approximation for degree-Q homogeneous polynomials. Proof uses explicit matrix representation / SOS spectral norm bounds, decomposes polynomials into multilinear blocks, spreads coefficients across symmetric representations, and proves a decoupling-type lower bound on the sphere so the spectral upper bound tracks the actual value.
AI-written summary · about
chapters (16)
- 0:00Intro
- 0:24Problem
- 2:10Complexity
- 2:42Approximability d = 0(1)
- 5:33First Step
- 6:31Tuples and Monomials
- 7:01Multi-Indices and Monomials
- 8:23Matrix Representations
- 12:03Strategy
- 14:52When g is multilinear
- 17:40Non-multilinear g
- 20:28Multilinear Decomposition Inequality
- 21:43Finding a good Matrix Representation
- 22:44Finding good B
- 24:17Saving 1 in Exponent
- 24:51Conclusion
related talks
01h 06mLP/SDP Hierarchies and Sum of Squares Proofs 4
59mOptimizing Noncommutative Polynomials: The SYK Model
31mA Positivity-First Approach to Sum-of-Squares Over the Hypercube
47mPlanted Clique, Sum-of-Squares and Pseudo-Calibration
01h 12mPedagogical Talk: Frameworks for Information-Computation Tradeoffs
01h 11mPedagogical Talk: Failure of Low-Degree Polynomials
59mLP/SDP Hierarchies and Sum of Squares Proofs 3
01h 00mAverage-case Complexity for Polynomials, and All That