How to refute a random CSP

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 gg n the instance I will be unsatisfiable with high probability, and we want to find a refutation - i.e., 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 gg 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 gg nlceil k/2 rceil 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 I whp when m gg nt/2. Indeed, our algorithm will "somewhat strongly" refute I, certifying Opt(I) ≤ 1-Omegak(1), if t = k then we get the strongest possible refutation, certifying Opt(I) ≤ E[P] + o(1). This last result is new even in the context of random k-SAT. Regarding the optimality of our m gg nt/2 requirement, prior work on SDP hierarchies has given some evidence that efficient refutation of random CSP(P) may be impossible when m ll nt/2. Thus there is an indication our algorithm's dependence on m is optimal for every P, at least in the context of SDP hierarchies. Along these lines, we show that our refutation algorithm can be carried out by the O(1)-round SOS SDP hierarchy. Finally, as an application of our result, we falsify assumptions used to show hardness-of-learning results in recent work of Daniely, Linial, and Shalev-Shwartz.