Spring 2017

Sum of Squares Lower Bounds for Refuting Any CSP

Monday, April 10th, 2017 10:00 am10:30 am

Add to Calendar

We consider random (or sufficiently pseudorandom) instances of a constraint satisfaction problem with n variables, m = m(n) constraints, and constraint predicate F.  Given a certain running time n^r for the "SOS algorithm", how strong an upper-bound 1-delta can be placed on the maximum fraction of simultaneously satisfiable constraints?
We establish the optimal 3-way tradeoff between m, r, and delta, in terms of F, generalizing all previously known lower bounds in the area.  
Perhaps the most interesting contribution is a new and improved definition for the "closure" of a set of constraints in a CSP, a graph-theoretic concept heavily used in previous work on proof complexity.
joint work with Pravesh Kothari, Ryuhei Mori, and David Witmer