Computer Science/Discrete Mathematics Seminar II

Let $P:\{0,1\}^k \to \{0,1\}$ be a $k$-ary predicate. A random instance of a constraint satisfaction problem (CSP(P)) where each of the $\Delta n$ constraints is $P$ applied to $k$ literals on $n$ variables chosen at random is unsatisfiable with high probability whenever the density of constraints, $\Delta \gg 1.$ The refutation problem asks for an efficient proof of unsatisfiability of such an instance that works correctly with high probability. We show that whenever the predicate $P$ fails to support a $t$-wise-uniform probability distribution over its satisfying assignments, the Sum-of-Squares (SoS) algorithm of degree $d = \Theta(\frac{n}{\Delta^{2/(t-2)} \log \Delta})$ (that runs in time $n^{O(d)}$) cannot refute a random instance of CSP(P). In particular, polynomial time SoS algorithm requires $\sim n^{t/2}$ constraints to refute CSPs with predicates that support $t$-wise-uniform distribution on their satisying assignments. This matches the bounds known for special cases such as 3XOR and 3SAT [Grigoriev 2001, Schonebeck 08]. Together with the recent work [Lee, Raghavendra, Steurer 2015], it also yields that any polynomial-size semidefinite programming relaxation for refutation requires at least $\sim n^{t/2}$ constraints. More generally, for every constraint predicate~$P$, we get a three-way hardness tradeoff between the density of constraints, the SOS degree (hence running time), and the strength of the refutation. By recent known algorithmic results of [Allen, O'Donnell, Witmer 2015] and [Raghavendra, Rao, Schramm 2016], our full three-way tradeoff is tight, up to lower-order factors. Our results carry over to the more general $\delta$-refutation problem: we show that if $P$ is $\delta$-close to supporting a $t$-wise uniform distribution on satisfying assignments, then the degree-$\Theta(\frac{n}{\Delta^{2/(t-1)} \log \Delta})$ SoS algorithm cannot $(\delta+o(1))$-refute a random instance of CSP$(P)$. Our results also extend with no change to CSPs over larger alphabets and subsume all previously known lower bounds for semialgebraic refutations of random CSPs. They are also the first to show a distinction between the degree SOS needs to weakly refute random CSPs, versus $\delta$-refute them.