Theory Lunch

Sum of squares lower bounds for refuting any CSP

David Witmer

November 30, 2016

Let P be a k-ary predicate. Consider a random instance of the constraint satisfaction problem CSP(P) on n variables with $\Delta n$ constraints, each being P applied to k randomly chosen literals. When $\Delta >>1$, such an instance is unsatisfiable with high probability. The refutation problem is to efficiently find a proof of unsatisfiability. The sum of squares (SOS) hierarchy is a powerful algorithmic tool in the study of CSPs. It is a sequence of semidefinite programming relaxations parameterized by the degree d. The relaxation becomes tighter as d increases, but it takes $n^{O\left(d\right)}$ time to solve. In this talk, we will discuss a lower bound on the SOS degree required to refute a random instance of CSP(P): If P supports a t-wise-uniform probability distribution on its satisfying assignments, the SOS algorithm of degree $d=\Theta (n/{\Delta }^{2/(t-1)})$ cannot refute. By recent algorithmic results, this bound is essentially tight. This is joint work with Pravesh K. Kothari, Ryuhei Mori, and Ryan O.Donnell.