Tight size-degree bounds for sums-of-squares proofs
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Standard
Tight size-degree bounds for sums-of-squares proofs. / Lauria, Massimo; Nordström, Jakob.
30th Conference on Computational Complexity, CCC 2015. red. / David Zuckerman. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2015. s. 448-466 (Leibniz International Proceedings in Informatics, LIPIcs, Bind 33).Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Tight size-degree bounds for sums-of-squares proofs
AU - Lauria, Massimo
AU - Nordström, Jakob
PY - 2015/6/1
Y1 - 2015/6/1
N2 - 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.
AB - 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.
KW - Clique
KW - Degree
KW - Lasserre
KW - Lower bound
KW - Positivstellensatz
KW - Proof complexity
KW - Rank
KW - Resolution
KW - Semidefinite programming
KW - Size
KW - SOS
KW - Sums-ofsquares
UR - http://www.scopus.com/inward/record.url?scp=84958245402&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.CCC.2015.448
DO - 10.4230/LIPIcs.CCC.2015.448
M3 - Article in proceedings
AN - SCOPUS:84958245402
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 448
EP - 466
BT - 30th Conference on Computational Complexity, CCC 2015
A2 - Zuckerman, David
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 30th Conference on Computational Complexity, CCC 2015
Y2 - 17 June 2015 through 19 June 2015
ER -
ID: 251869202