Exponential Lower Bounds on Spectrahedral Representations of Hyperbolicity Cones
summary
Proves that a family of hyperbolic polynomials requires spectrahedral representations of size exponential in the input parameters, and that even approximate representations need exponential size. Builds a hypercube of hyperbolic polynomials by small, translation‑invariant perturbations of elementary symmetric polynomials using matching‑based polynomials that vanish on high‑multiplicity restrictions, compares cones via a symmetrized Hausdorff/metric on linear restrictions, analyzes root shifts using Jacobi polynomials, and finishes with a packing argument to force exponentially large matrix size.
AI-written summary · about
chapters (19)
- 0:00Introduction
- 1:21Preliminary Definitions
- 2:08Relation to SDP
- 2:51Lax Conjectures
- 5:05Complexity of Spectrahedral Representations
- 6:16Main Theorem
- 9:13Three Spaces
- 10:49Packing Arguments
- 12:23Gameplan
- 14:18Elementary Symmetric Polynomial
- 17:17Valid Perturbations
- 17:57Constant restrictions
- 24:07Analytic Notions for Multiple Roots
- 27:20From Perturbations to Restrictions
- 28:25Finding Restrictions
- 32:28Far Cones
- 33:22From Cones to Spectrahedral Representations
- 35:31Full Picture
- 36:16Future Directions
related talks
01h 04mHigher-dimensional Expansion of Random Geometric Complexes
31mA Positivity-First Approach to Sum-of-Squares Over the Hypercube
27mWeak Decoupling, Polynomial Folds, and Approximate Optimization over the Sphere
01h 11m(Hidden) Symmetries of Computational Problems (continued)
33mSymmetry Adapted Gram Spectrahedra
01h 00mAverage-case Complexity for Polynomials, and All That
11mGeometric Methods for Machine Learning and Optimization
57mHigh Dimensional Geometry and Concentration I