Certificates of Polynomial Non-Negativity via Hyperbolic Optimization
summary
Proposes certifying global non-negativity by encoding a hyperbolic polynomial and a direction into a family of polynomial Hankel/Bezoutian matrices whose positive semidefiniteness characterizes membership in the hyperbolicity cone, so certificates become linear projections of the hyperbolicity cone and are searchable by solving hyperbolic programs. Connects this to sums of squares: low-degree/low-variable cases coincide but constructs explicit non-SOS examples (a quartic from a Vámos-type matroid and a cubic with 43 variables from the icosahedral graph), proves NP-hardness of testing cubic hyperbolicity, and exhibits a polynomial with no power admitting a definite determinantal representation.
AI-written summary · about
chapters (7)
- 0:00Introduction to Hyperbolicity
- 21:24Hyperbolic Certificates
- 23:29Relationship with SOS
- 35:23Hyperbolic Cubics
- 37:23Non-SOS Example
- 43:14Conclusion
- 43:35Q&A Session
related talks
27mNonnegative Polynomials, Nonconvex Polynomial Optimization, and Applications to Learning
01h 01mLP/SDP Hierarchies and Sum of Squares Proofs 1
01h 04mLP/SDP Hierarchies and Sum of Squares Proofs 2
31mA Positivity-First Approach to Sum-of-Squares Over the Hypercube
01h 11mPedagogical Talk: Failure of Low-Degree Polynomials
59mOptimizing Noncommutative Polynomials: The SYK Model
01h 11m(Hidden) Symmetries of Computational Problems (continued)
57mStructure Of Boolean Almost Low Degree Functions On The Biased Cube