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

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

Abstract

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.

Detaljer

Författare
Externa organisationer
  • KTH Royal Institute of Technology
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Datavetenskap (datalogi)

Nyckelord

Originalspråkengelska
Titel på värdpublikation30th Conference on Computational Complexity, CCC 2015
RedaktörerDavid Zuckerman
FörlagSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Sidor448-466
Antal sidor19
ISBN (elektroniskt)9783939897811
StatusPublished - 2015 jun 1
PublikationskategoriForskning
Peer review utfördJa
Externt publiceradJa
Evenemang30th Conference on Computational Complexity, CCC 2015 - Portland, USA
Varaktighet: 2015 jun 172015 jun 19

Publikationsserier

NamnLeibniz International Proceedings in Informatics, LIPIcs
FörlagSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Volym33
ISSN (tryckt)1868-8969

Konferens

Konferens30th Conference on Computational Complexity, CCC 2015
LandUSA
OrtPortland
Period2015/06/172015/06/19