[Proof Complexity] Paper announcement: Tight Size-Degree Bounds for Sums-of-Squares Proofs

Jakob Nordstrom jakobn at kth.se
Sat Apr 11 21:39:02 CEST 2015

Dear colleagues,

This is just to announce that we have posted a full-length version at
http://eccc.hpi-web.de/report/2015/053/ of the paper "Tight Size-Degree Bounds
for Sums-of-Squares Proofs" by Massimo Lauria and myself, to be presented at
CCC this summer.

The abstract follows below. Any questions or comments would be much appreciated.

Best regards,
Jakob Nordstrom



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^{Omega(d)} for values of d = d(n) from constant
all the way up to n^{delta} for some universal constant delta. This shows that
the n^{O(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 [Krajicek '04] and [Dantchev and Riis '03], and then applying a
restriction argument as in [Atserias, Müller, and Oliva '13] and [Atserias,
Lauria, and Nordstrom '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.

Jakob Nordström, Assistant Professor
KTH Royal Institute of Technology
Osquars backe 2, SE-100 44 Stockholm, Sweden
Phone: +46 8 790 69 19 (office), +46 70 742 21 98 (cell)

More information about the Proof-Complexity mailing list