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 n 3/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 n t/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 n t/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. Constraint satisfaction problems (CSPs) play a major role in computer science. There is a vast theory [23] of how algebraic properties of a CSP predicate affect its worst-case satisfiability complexity; there is a similarly vast theory [68] of worst-case approximability of CSPs. Finally, there is a rich range of research -from the fields of computer science, mathematics, and physics -on the average-case complexity of random CSPs; see [2] for a survey just of random k-SAT. This paper is concerned with random CSPs, and in particular the problem of efficiently refuting satisfiability for random instances. This is a well-studied algorithmic task with connections to, e.g., proof complexity [20] Historically, random CSPs are probably best studied in the case of k-SAT, k ≥ 3. The model here involves choosing a CNF formula I over n variables by drawing m clauses (ORs of k literals) independently and uniformly at random. This is one of the best known efficient ways of generating hard-seeming instances of NP-complete and coNP-complete problems. The computational hardness depends crucially on the density, α = m/n. For each k there is (conjecturally) a constant critical density α k such that I is satisfiable with high probability when α < α k , and I is unsatisfiable with high probability when α > α k . (Here and throughout, "with high probability (whp)" means with probability 1 − o(1) as n → ∞.) This phenomenon occurs for all nontrivial random CSPs; in the case of k-SAT it's been rigorously proven [35] for sufficiently large k. There is a natural algorithmic task associated with each of the two regimes. When α < α k one wants to find a satisfying assignment for I. When α > α k one wants to refute I; i.e., find a certificate of unsatisfiability. Most heuristic SAT-solvers use DPLL-based algorithms; on unsatisfiable instances, they produce certificates that can be viewed as refutations within the Resolution proof system. More generally, a refutation algorithm for density α is any algorithm that: a) outputs "unsatisfiable" or "fail"; b) never incorrectly outputs "unsatisfiable"; c) outputs "fail" with low probability (i.e., probability o(1)). 1 Empirical work suggests that as α increases towards α k , finding satisfying assignments becomes more difficult; and conversely, as α increases beyond α k , finding certificates of unsatisfiability gradually becomes easier. A seminal paper of Chvátal and Szemerédi [25] showed that for any sufficiently large integer c (depending on k), a random k-SAT instance with m = cn requires Resolution refutations of size 2 Ω(n) (whp). On the other hand, Fu [46] showed that polynomial-size Resolution refutations exist (whp) once m ≥ O(n k−1 ); Beame et al. [18] 1 We caution the reader that in this paper we do not consider the related, but distinct, scenario of distinguishing planted random instances from truly random ones.
We brie y survey the prior work on refuting random CSPs-we refer the reader to REF for a thorough survey on the topic.
How to Refute a Random CSP
2015 IEEE 56th Annual Symposium on Foundations of Computer Science
2015 IEEE 56th Annual Symposium on Foundations of Computer Science
Mathematics Computer Science