Bounds on the Semidefinite Programming Complexity of the Euclidean Ball

Guanxi Li, Kevin Shu

We present tight lower bounds for the size of any linear matrix inequality representation of the Euclidean ball, and on the semidefinite extension complexity of the ball. Specifica…