UC Santa Cruz

The interpolation method, originally developed in statistical physics, transforms distributions of random Constraint Satisfaction Problems (CSPs) to distributions of much simpler problems while bounding the change in a number of associated statistical quantities along the transformation path. By now, it is known that, in principle, the method can yield rigorous unsatisfiability results if one ``plugs in an appropriate functional distribution'' to the derived expressions. A drawback of the method is that identifying the appropriate distribution leads to major analytical challenges as the relevant distributions are, in fact, infinite dimensional objects. We develop a variant of the interpolation method for random CSPs on arbitrary sparse degree distributions which trades accuracy for tractability. In particular, our bounds only require the solution of a 1-dimensional optimization problem (which typically turns out to be very easy) and as such can be used to compute explicit rigorous unsatisfiability bounds. We use this new method to analyze the performance of a number of algorithms on random 3-CNF formulas with n variables and m=rn clauses. A long series of papers analyzing so-called ``myopic'' algorithms has provided a sequence of lower bounds for the satisfiability threshold, which is widely believed to be r~4.26. Indeed, for each myopic algorithm A it is known that there exists an algorithm-specific clause-density, r_A, such that if r2.78 and the same is true for generalized unit clause for all r>3.1. Our results imply exponential lower bounds for many other myopic algorithms for densities similarly close to the corresponding r_A.