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

[Jakob Nordstrom]

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

**********

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^{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)
http://www.csc.kth.se/~jakobn/