Change search
ReferencesLink to record
Permanent link

Direct link
Tight size-degree bounds for sums-of-squares proofs
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0003-4003-3168
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0002-2700-4285
2015 (English)In: Leibniz International Proceedings in Informatics, LIPIcs, Dagstuhl Publishing , 2015, Vol. 33, 448-466 p.Conference paper (Refereed)Text
Abstract [en]

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.

Place, publisher, year, edition, pages
Dagstuhl Publishing , 2015. Vol. 33, 448-466 p.
Keyword [en]
Clique, Degree, Lasserre, Lower bound, Positivstellensatz, Proof complexity, Rank, Resolution, Semidefinite programming, Size, SOS, Sums-ofsquares
National Category
Mathematical Analysis
URN: urn:nbn:se:kth:diva-187388DOI: 10.4230/LIPIcs.CCC.2015.448ScopusID: 2-s2.0-84958245402ISBN: 978-393989781-1OAI: diva2:931253
30th Conference on Computational Complexity, CCC 2015; Portland; United States

QC 20160527

Available from: 2016-05-27 Created: 2016-05-23 Last updated: 2016-05-27Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Lauria, MassimoNordström, Jakob
By organisation
Theoretical Computer Science, TCS
Mathematical Analysis

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

ReferencesLink to record
Permanent link

Direct link