2026-07-23T01:41:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10846 2024-03-06T10:46:51Z ddc:004 open_access

Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs Atserias, Albert Hakoniemi, Tuomas Proof complexity semialgebraic proof systems Sums-of-Squares Positivstellensatz trade-offs lower bounds monomial size degree 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 it also has one whose degree is of the order of the square root of n log s plus k. A similar statement holds for the more general Positivstellensatz (PS) proofs. This establishes size-degree trade-offs for SOS and PS that match their analogues for weaker proof systems such as Resolution, Polynomial Calculus, and the proof systems for the LP and SDP hierarchies of Lovász and Schrijver. As a corollary to this, and to the known degree lower bounds, we get optimal integrality gaps for exponential size SOS proofs for sparse random instances of the standard NP-hard constraint optimization problems. We also get exponential size SOS lower bounds for Tseitin and Knapsack formulas. The proof of our main result relies on a zero-gap duality theorem for pre-ordered vector spaces that admit an order unit, whose specialization to PS and SOS may be of independent interest. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Albert Atserias and Tuomas Hakoniemi 2019 Is Part Of LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2019.24 urn:nbn:de:0030-drops-108464 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.24 eng https://creativecommons.org/licenses/by/3.0/legalcode