PreprintarXiv licencearXiv
Bounds on the Semidefinite Programming Complexity of the Euclidean Ball
Abstract
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 ⌈ 2 √(n−1)⌉. 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, and indeed extend to any convex set whose extreme points form a semialgebraic set.
Related
- Multiplicative Semidefinite Programming Upper Bounds on Quantum No-Signalling-Assisted Zero-Error Capacity
- Low-Rank and Lifted Semidefinite Programming for Mixed-Integer Polynomial Power Grid Optimization
- Inexact PDHG for Large-Scale Semidefinite Programming
- Spectral Deflation for Factorization-Free Matrix Filtering in Muon and Semidefinite Programming
- A Triangular Log-Det PDHG for Semidefinite Programming: Complementarity Selection and Global Linear Convergence
BibTeX
@misc{li2026bounds,
title = {{Bounds on the Semidefinite Programming Complexity of the Euclidean Ball}},
author = {Guanxi Li and Kevin Shu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.21089},
eprint = {2609.21089},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.21089},
}
RIS
TY - UNPB
TI - Bounds on the Semidefinite Programming Complexity of the Euclidean Ball
AU - Guanxi Li
AU - Kevin Shu
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2609.21089
UR - https://arxiv.org/abs/2609.21089
AB - 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 ⌈ 2 √(n−1)⌉. 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, and indeed extend to any convex set whose extreme points form a semialgebraic set.
ER -