How to Refute a Random CSP

Let P be a k-ary predicate and let H be a uniformly random constraint satisfaction problem with n variables and m = m(n) constraints, each of type P applied to k literals. For example, if P is the 3-ary OR predicate, then H is a classic random instance of 3SAT.

For each P there is a critical constant alpha such that H will be satisfiable (with high probability) if m < alpha n and will be unsatisfiable (whp) if m > alpha n. In the former case, the natural algorithmic task is to find a satisfying assignment to the variables.

In the latter case, the natural algorithmic task is to find a refutation; i.e., a proof of unsatisfiability. This task becomes algorithmically easier the larger m is. As an example, in the case of 3SAT, it is known that efficient refutation algorithms exist provided m >> n^{3/2}. We will discuss the refutation problem in general, focusing on how the predicate, P, affects the number of constraints, m, required for efficient refutation. We will also describe the applications to hardness of learning.