Tight size-degree bounds for sums-of-squares proofs

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

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Ω(d) for values of d = d(n) from constant all the way up to nδ for some universal constant δ. This shows that the nO(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 [Krajícek'04] and [Dantchev and Riis'03], and then applying a restriction argument as in [Atserias, Müller, and Oliva'13] and [Atserias, Lauria, and Nordström'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.

Original languageEnglish
Title of host publication30th Conference on Computational Complexity, CCC 2015
EditorsDavid Zuckerman
Number of pages19
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication date1 Jun 2015
Pages448-466
ISBN (Electronic)9783939897811
DOIs
Publication statusPublished - 1 Jun 2015
Externally publishedYes
Event30th Conference on Computational Complexity, CCC 2015 - Portland, United States
Duration: 17 Jun 201519 Jun 2015

Conference

Conference30th Conference on Computational Complexity, CCC 2015
LandUnited States
ByPortland
Periode17/06/201519/06/2015
SponsorMicrosoft Research
SeriesLeibniz International Proceedings in Informatics, LIPIcs
Volume33
ISSN1868-8969

    Research areas

  • Clique, Degree, Lasserre, Lower bound, Positivstellensatz, Proof complexity, Rank, Resolution, Semidefinite programming, Size, SOS, Sums-ofsquares

ID: 251869202