Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs

Albert Atserias, Tuomas Hakoniemi

We show that if a system of degree-$k$ polynomial constraints on~$n$ Boolean variables has a Sums-of-Squares (SOS) proof of unsatisfiability with at most~$s$ many monomials, then i…