How to Refute a Random CSP
Sarah R. Allen, Ryan W. O’Donnell, David K Witmer · 2015
Let P be a k-ary predicate over a finite alphabet. Consider a random CSP(P) instance I over n variables with m constraints. When m ≫ n the instance will be unsatisfiable with high probability and we want to find a certificate of unsatisfiability. When P is the 3-ary OR predicate, this is the well-studied problem of refuting random 3-SAT formulas and an efficient algorithm is known only when m ≫ n3/2. Understanding the density required for refutation of other predicates is important in cryptography, proof complexity, and learning theory. Previously, it was known that for a k-ary predicate, having m ≫≫n[k/2]constraints suffices for refutation. We give a criterion for predicates that often yields efficient refutation algorithms at much lower densities. Specifically, if P fails to support a t-wise uniform distribution, then there is an efficient algorithm that refutes random CSP(P) instances whp when m ≫ nt/2. Indeed, our algorithm will “somewhat strongly” refute the instance I, certifying Opt(I) ≤ 1 - Ωk(1). If t = k then we get the strongest possible refutation, certifying Opt(I) ≤ E[P] + o(1). This last result is new even for random k-SAT. Prior work on SDP hierarchies has given some evidence that efficient refutation of random CSP(P) may be impossible when m ≫ nt/2; thus there is an indication that our algorithm's dependence on m is optimal for every P, at least in the context of SDP hierarchies. As an application of our result, we falsify assumptions used to show hardness-of-learning in recent work of Daniely, Linial, and Shalev-Shwartz.