How to refute a random CSP
September 30, 2015

Let P be a nontrivial k-ary predicate over a finite alphabet. Consider a random CSP(P) instance I over n variables with m constraints, where each constraint is P applied to k random literals. When m >> n the instance I will be unsatisfiable with high probability, and the natural associated algorithmic task is to find a refutation of I — i.e., a certificate of unsatisfiability. When P is the 3-ary Boolean OR predicate, this is the well studied problem of refuting random 3-SAT formulas; in this case, an efficient algorithm is known only when m >> n^{3/2}. Understanding the density required for average-case refutation of other predicates is of importance for various areas of complexity, including cryptography, proof complexity, and learning theory. The main previously-known result is that for a general Boolean k-ary predicate P, having m >> n^{ceil(k/2)} random constraints suffices for efficient refutation.

We give a general criterion for arbitrary k-ary predicates, one that often yields efficient refutation algorithms at much lower densities. Specifically, if P fails to support a t-wise independent (uniform) probability distribution, then there is an efficient algorithm that refutes random CSP(P) instances I with high probability, provided m >> n^{t/2} . Indeed, our algorithm will “somewhat strongly” refute I, certifying Opt(I) <=1 − Omega(1); if t = k then we furthermore 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. As an application of our result, we falsify the “SRCSP assumptions” used to show various hardness-of-learning results in the recent (STOC 2014) work of Daniely, Linial, and Shalev–Shwartz.

This is joint work with Ryan O’Donnell and David Witmer.