Bounds on the Semidefinite Programming Complexity of the Euclidean Ball
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. Specifically, we show that any linear matrix inequality representing the Euclidean ball must involve matrices of size at least $n$, and any spectrahedral extension of the Euclidean ball must involve matrices of size at least $\lceil 2 \sqrt{n-1}\rceil$. These match the upper bounds given by existing explicit constructions exactly. Our proofs rely on elementary facts about the dimension of the set of faces of spectrahedra,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.21089
curl -X POST /api/v1/records/arxiv/2609.21089/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.21089/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'