Lower Bounds on the Size of Semidefinite Programming Relaxations.

James R. Lee Prasad Raghavendra David Steurer

Published in: STOC (2015)

Keyphrases

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