Metraipolis › archive › dc_bfb567c98e19

Bounds on the Semidefinite Programming Complexity of the Euclidean Ball — arXiv:2609.21089

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.21089
License (as archived)
CC0-1.0
Archived
2026-10-10T02:04:41.876Z
SHA-256 of the archived text
c9700ce7f772845620aa98ae375811af3afd1b7f867b9a6b0093c1af4a70cf96
Stable URL of this page
https://metraipolis.com/documento/dc_bfb567c98e19

How to cite

Bounds on the Semidefinite Programming Complexity of the Euclidean Ball — arXiv:2609.21089 — arXiv (en), https://arxiv.org/abs/2609.21089 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bfb567c98e19 (Metraipolis archive dc_bfb567c98e19, sha256 c9700ce7f772845620aa98ae375811af3afd1b7f867b9a6b0093c1af4a70cf96)
BibTeX
@misc{dcbfb567c98e19,
  title = {Bounds on the Semidefinite Programming Complexity of the Euclidean Ball — arXiv:2609.21089},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.21089},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bfb567c98e19; sha256 c9700ce7f772845620aa98ae375811af3afd1b7f867b9a6b0093c1af4a70cf96},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.21089. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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, and indeed extend to any convex set whose extreme points form a semialgebraic set.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-21 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.21089 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-10T01:45:31.230Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-21?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).