Lower Bounds on the Size of Semidefinite Programming Relaxations
type: Item
instance of: scholarly article
title: Lower Bounds on the Size of Semidefinite Programming Relaxations
zbMATH Open document ID: 1321.90099
DOI: 10.1145/2746539.2746599
author: James R. Lee
author: Prasad Raghavendra
author: David Steurer
published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing
publication date: 2015-08-21T00:00:00Z
full work available at URL: https://arxiv.org/abs/1411.6317
Mathematics Subject Classification ID: 90C22
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6474760
zbMATH Keywords: approximation complexity
zbMATH Keywords: lower bounds on positive-semidefinite rank
zbMATH Keywords: polynomial optimization
zbMATH Keywords: quantum learning
zbMATH Keywords: semidefinite programming
zbMATH Keywords: sum-of-squares method
describes a project that uses: Graphs
MaRDI profile type: Publication
OpenAlex ID: W2031923588
arXiv ID: 1411.6317
cites work: On Approximate Distance Labels and Routing Schemes with Affine Stretch
cites work: On sparse spanners of weighted graphs
cites work: Near-Linear Time Construction of Sparse Neighborhood Covers
cites work: Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
cites work: Approximate distance oracles with constant query time
cites work: Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
cites work: Ramsey partitions and proximity data structures
cites work: Q5414573
cites work: Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
cites work: Automata, Languages and Programming
cites work: Shortest-path queries in static networks
cites work: Approximate distance oracles
description: scientific article