Sum of squares lower bounds for refuting any CSP

Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell +1

Let $P:\{0,1{\}}^k\to \{0,1\}$ be a nontrivial $k$-ary predicate. Consider a random instance of the constraint satisfaction problem $\mathrm{CSP}(P)$ on $n$ variables with $\Delta n$ cons…