3 papers
cs.CC2026
Ideal Membership in Polynomial Calculus: Complexity and Reductions
Alex Bortolotti, Monaldo Mastrolilli
The Ideal Membership Problem (IMP) asks whether a polynomial f belongs to an ideal <p_1, ..., p_m> of Q[x_1, ..., x_n]. Polynomial Calculus (PC) certifies membership by deriving f…
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…