[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

*REMINDER*

Combinatorics & Theoretical Computer Science Seminar

Tuesday, June 9, 2015
Ryerson 251@ 3:45 pm
 
Massimo Lauria
KTH Royal Inst. of Tech.
 
Title: “Tight Size-Degree Bounds for Sums-of-Squares Proofs”
 
Abstract: 
Sums-of-Squares (SOS) is a technique to prove that a real polynomial is positive by showing that it is representable as a sums of squared polynomials. This has application to inapproximability theory or propositional theorem proving. In particular it is possible to prove that a CNF is unsatisfiable with a sums-of-squares proof. If the CNF has n variables and some SOS proof which does only involve polynomials of degree d, then it is possible to find such proof in time n^{O(d)} using Lasserre semidefinite relaxations.
We exhibit families of 4-CNF formulas over n variables that have sums-of-squares 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.

This is joint work with Jakob Nordstrom.

Host by Prof. Razborov

(Refreshments will be served before the talk in Ry. 255@ 2:30pm)
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20150609/b49f68b0/attachment.htm