Spring 2019

Exponential Lower Bounds on Spectrahedral Representations of Hyperbolicity Cones

Friday, May 3, 2019 10:00 am10:45 am PDT

Add to Calendar


Nick Ryder (UC Berkeley)

The Generalized Lax Conjecture asks whether every hyperbolicity cone is a section of a semidefinite cone of sufficiently high dimension. We prove that the space of hyperbolicity cones of hyperbolic polynomials of degree d in n variables contains exponentially pairwise distant cones in a certain metric, and therefore that any semidefinite representation of such cones must have dimension at least exponential in n/d (even if a small approximation is allowed). The proof contains several ingredients of independent interest, including the identification of a large subspace in which the elementary symmetric polynomials lie in the relative interior of the set of hyperbolic polynomials, and quantitative versions of several basic facts about real rooted polynomials.