3 papers
cs.CC2025
On the Bit Size of Sum-of-Squares Proofs for Symmetric Formulations
Alex Bortolotti, Monaldo Mastrolilli, Marilena Palomba +1
The Sum-of-Squares (SoS) hierarchy is a powerful framework for polynomial optimization and proof complexity, offering tight semidefinite relaxations that capture many classical alg…
cs.CC2025
On the Degree Automatability of Sum-of-Squares Proofs
Alex Bortolotti, Monaldo Mastrolilli, Luis Felipe Vargas
The Sum-of-Squares (SoS) hierarchy, also known as Lasserre hierarchy, has emerged as a promising tool in optimization. However, it remains unclear whether fixed-degree SoS proofs c…
math.OC2025
Computational complexity of sum-of-squares bounds for copositive programs
Marilena Palomba, Lucas Slot, Luis Felipe Vargas +1
In recent years, copositive programming has received significant attention for its ability to model hard problems in both discrete and continuous optimization. Several relaxations…