Lower Bounds on the Size of Semidefinite Programming Relaxations
From MaRDI portal
Publication:2941550
DOI10.1145/2746539.2746599zbMath1321.90099arXiv1411.6317MaRDI QIDQ2941550
James R. Lee, Prasad Raghavendra, David Steurer
Publication date: 21 August 2015
Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1411.6317
semidefinite programming; polynomial optimization; quantum learning; approximation complexity; lower bounds on positive-semidefinite rank; sum-of-squares method
90C22: Semidefinite programming
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Uses Software