2026-07-23T03:19:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5073 2024-03-06T10:35:48Z ddc:004 open_access

Tight Size-Degree Bounds for Sums-of-Squares Proofs Lauria, Massimo Nordström, Jakob Proof complexity resolution Lasserre Positivstellensatz sums-of-squares SOS semidefinite programming size degree rank clique lower bound We exhibit families of 4-CNF formulas over n variables that have sums-of-squares (SOS) proofs of unsatisfiability of degree (a.k.a. rank) d but require SOS proofs of size n^Omega(d) for values of d = d(n) from constant all the way up to n^delta for some universal constant delta. This shows that the n^O(d) running time obtained by using the Lasserre semidefinite programming relaxations to find degree-d SOS proofs is optimal up to constant factors in the exponent. We establish this result by combining NP-reductions expressible as low-degree SOS derivations with the idea of relativizing CNF formulas in [Krajicek '04] and [Dantchev and Riis '03], and then applying a restriction argument as in [Atserias, Müller, and Oliva '13] and [Atserias, Lauria, and Nordstrom '14]. This yields a generic method of amplifying SOS degree lower bounds to size lower bounds, and also generalizes the approach in [ALN14] to obtain size lower bounds for the proof systems resolution, polynomial calculus, and Sherali-Adams from lower bounds on width, degree, and rank, respectively. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Massimo Lauria and Jakob Nordström 2015 Is Part Of LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2015.448 urn:nbn:de:0030-drops-50736 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.448 eng https://creativecommons.org/licenses/by/3.0/legalcode