On the Bit Size of Sum-of-Squares Proofs for Symmetric Formulations
SIAM Journal on Discrete Mathematics · 30.09.2026 · 40 (3) · 1010-1033
DOI: 10.1137/25m1796576 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 10.07.2026. Verfasst von Alex Bortolotti und 3 weiteren Autor:innen. Die Arbeit nennt 38 Literaturangaben. Gefördert von: Swiss National Science Foundation.
Abstract (Originalsprache)
The Sum-of-Squares ([Formula: see text]) hierarchy is a powerful framework for polynomial optimization and proof complexity, offering tight semidefinite relaxations that capture many classical algorithms. Despite its broad applicability, several works have revealed fundamental limitations to [Formula: see text] automatability. (i) While low-degree [Formula: see text] proofs are often desirable for tractability, recent works have revealed they may require coefficients of prohibitively large bit size, rendering them computationally infeasible. (ii) Prior works have shown that [Formula: see text] proofs for seemingly easy problems require high degree. In particular, this phenomenon also arises in highly symmetric problems. Instances of symmetric problems—particularly those with a small number of constraints—have repeatedly served as benchmarks for establishing high-degree lower bounds in the [Formula: see text] hierarchy. It has remained unclear whether symmetry can also lead to large bit sizes in [Formula: see text] proofs, potentially making low-degree proofs computationally infeasible even in symmetric settings. In this work, we resolve this question by proving that symmetry alone does not lead to large bit size [Formula: see text] proofs. Focusing on symmetric Archimedean instances, we show that low-degree [Formula: see text] proofs for such systems admit compact, low bit size representations. Together, these results provide a conceptual separation between two sources of [Formula: see text] hardness—degree and bit size—by showing they do not necessarily align, even in highly symmetric instances. This insight guides future work on automatability and lower bounds: symmetry may necessitate high-degree proofs, but it does not by itself force large coefficients.
Förderung
- Swiss National Science Foundation
Zitieren
APA
Bortolotti, A., Mastrolilli, M., Palomba, M., & Vargas, L. F. (2026). On the Bit Size of Sum-of-Squares Proofs for Symmetric Formulations. SIAM Journal on Discrete Mathematics, 40(3), 1010-1033. https://doi.org/10.1137/25m1796576
Vancouver
Bortolotti A, Mastrolilli M, Palomba M, Vargas LF. On the Bit Size of Sum-of-Squares Proofs for Symmetric Formulations. SIAM Journal on Discrete Mathematics. 2026;40(3):1010-1033. doi:10.1137/25m1796576
BibTeX
@article{Bortolotti2026,
author = {Bortolotti, Alex and Mastrolilli, Monaldo and Palomba, Marilena and Vargas, Luis Felipe},
title = {On the Bit Size of Sum-of-Squares Proofs for Symmetric Formulations},
journal = {SIAM Journal on Discrete Mathematics},
year = {2026},
volume = {40},
number = {3},
pages = {1010--1033},
doi = {10.1137/25m1796576}
}
EUVIMED