Exponential lower bounds on spectrahedral representations of hyperbolicity cones

2017/11/30 by Raghavendra, Prasad, Ryder, Nick, Srivastava, Nikhil +1
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1711.11497

Abstract

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 (n/d)^Ω(d) pairwise distant cones in a certain metric, and therefore that any semidefinite representation of such cones must have dimension at least (n/d)^Ω(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.

Related

• Spectrahedrality of hyperbolicity cones of multivariate matching\n polynomials
• Spectrahedral relaxations of hyperbolicity cones
• Hyperbolic Polynomials and Generalized Clifford Algebras
• Hyperbolicity cones of elementary symmetric polynomials are spectrahedral
• Smooth Hyperbolicity Cones are Spectrahedral Shadows