Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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

Lauria, Massimo and Nordström, Jakob LU (2015) 30th Conference on Computational Complexity, CCC 2015 In Leibniz International Proceedings in Informatics, LIPIcs 33. p.448-466
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]... (More)

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.

(Less)
Please use this url to cite or link to this publication:
author
and
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Clique, Degree, Lasserre, Lower bound, Positivstellensatz, Proof complexity, Rank, Resolution, Semidefinite programming, Size, SOS, Sums-ofsquares
host publication
30th Conference on Computational Complexity, CCC 2015
series title
Leibniz International Proceedings in Informatics, LIPIcs
editor
Zuckerman, David
volume
33
pages
19 pages
publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
conference name
30th Conference on Computational Complexity, CCC 2015
conference location
Portland, United States
conference dates
2015-06-17 - 2015-06-19
external identifiers
  • scopus:84958245402
ISSN
1868-8969
ISBN
9783939897811
DOI
10.4230/LIPIcs.CCC.2015.448
language
English
LU publication?
no
id
5fcafda2-73a9-4019-9c6c-66f2b076b61c
date added to LUP
2020-12-18 22:23:21
date last changed
2022-04-19 03:06:48
@inproceedings{5fcafda2-73a9-4019-9c6c-66f2b076b61c,
  abstract     = {{<p>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<sup>Ω(d)</sup> for values of d = d(n) from constant all the way up to n<sup>δ</sup> for some universal constant δ. This shows that the n<sup>O(d)</sup> 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.</p>}},
  author       = {{Lauria, Massimo and Nordström, Jakob}},
  booktitle    = {{30th Conference on Computational Complexity, CCC 2015}},
  editor       = {{Zuckerman, David}},
  isbn         = {{9783939897811}},
  issn         = {{1868-8969}},
  keywords     = {{Clique; Degree; Lasserre; Lower bound; Positivstellensatz; Proof complexity; Rank; Resolution; Semidefinite programming; Size; SOS; Sums-ofsquares}},
  language     = {{eng}},
  month        = {{06}},
  pages        = {{448--466}},
  publisher    = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}},
  series       = {{Leibniz International Proceedings in Informatics, LIPIcs}},
  title        = {{Tight size-degree bounds for sums-of-squares proofs}},
  url          = {{http://dx.doi.org/10.4230/LIPIcs.CCC.2015.448}},
  doi          = {{10.4230/LIPIcs.CCC.2015.448}},
  volume       = {{33}},
  year         = {{2015}},
}