Exponential lower bounds on fixed-size psd rank and semidefinite extension complexity.

Hamza Fawzi Pablo A. Parrilo

Published in: CoRR (2013)

Keyphrases

fixed size
semidefinite
lower bound
average case complexity
sliding window
worst case
semidefinite programming
upper bound
sufficient conditions
objective function
window size
computational complexity
np hard
convex relaxation
data streams
multiresolution
higher dimensional
model selection