Exponential Lower Bounds on Spectrahedral Representations of Hyperbolicity Cones

DOI10.1137/1.9781611975482.141zbMath1432.90103arXiv1711.11497OpenAlexW2774729553MaRDI QIDQ5236328

Prasad Raghavendra, Benjamin Weitz, Nick Ryder, Nikhil Srivastava

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1711.11497

Mathematics Subject Classification ID

Semidefinite programming (90C22) Abstract computational complexity for mathematical programming problems (90C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Spectral linear matrix inequalities

This page was built for publication: Exponential Lower Bounds on Spectrahedral Representations of Hyperbolicity Cones