Sum of squares lower bounds for refuting any CSP
Pravesh K. Kothari, Ryuhei Mori, Ryan W. O’Donnell, David K Witmer · 2017
Let P:{0,1}k → {0,1} be a nontrivial k-ary predicate. Consider a random instance of the constraint satisfaction problem (P) on n variables with Δ n constraints, each being P applied to k randomly chosen literals. Provided the constraint density satisfies Δ ≫ 1, such an instance is unsatisfiable with high probability. The refutation problem is to efficiently find a proof of unsatisfiability.