Lower bounds on the size of semidefinite programming relaxations.

James R. Lee Prasad Raghavendra David Steurer

Published in: CoRR (2014)

Keyphrases

semidefinite programming
lower bound
semidefinite
linear programming
upper bound
np hard
objective function
interior point methods
optimal solution
kernel matrix
primal dual
maximum margin
quadratically constrained quadratic
worst case
computational complexity