On the Bit Size of Sum-of-Squares Proofs for Symmetric Formulations
Preprint
Abstract
The Sum-of-Squares (SoS) 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 SoS automatability. (i) While low-degree SoS 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 SoS 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 SoS hierarchy. It has remained unclear whether symmetry can also lead to large bit sizes in SoS 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 SoS proofs. Focusing on symmetric Archimedean instances, we show that low-degree SoS proofs for such systems admit compact, low bit size representations. Together, these results provide a conceptual separation between two sources of SoS 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.Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Reflection groups and cones of sums of squaresJournal of Symbolic Computation, 2023
- Symmetric Non-Negative Forms and Sums of SquaresDiscrete & Computational Geometry, 2020
- Sum-of-squares hierarchy lower bounds for symmetric formulationsMathematical Programming, 2019
- Convergence rates of moment-sum-of-squares hierarchies for optimal control problemsSystems & Control Letters, 2017
- An unbounded Sum-of-Squares hierarchy integrality gap for a polynomially solvable problemMathematical Programming, 2017
- Sums of Squares, Moment Matrices and Optimization Over Polynomials2008
- Symmetry groups, semidefinite programs, and sums of squaresJournal of Pure and Applied Algebra, 2004
- Semidefinite programming relaxations for semialgebraic problemsMathematical Programming, 2003
- Complexity of Null- and Positivstellensatz proofsAnnals of Pure and Applied Logic, 2001
- Even symmetric sexticsMathematische Zeitschrift, 1987