Random instances of Constraint Satisfaction Problems (CSP's) appear to be hard for all known algorithms, when the number of constraints per variable lies in a certain interval. Contributing to the general understanding of the structure of the solution space of a CSP in the satisfiable regime, we formulate a set of natural technical conditions on a large family of (random) CSP's, and prove bounds on three most interesting thresholds for the density of such an ensemble: namely, the satisfiability threshold, the threshold for clustering of the solution space, and the threshold for an appropriate reconstruction problem on the CSP's. The bounds become asymptoticlally tight as the number of degrees of freedom in each clause diverges. The families are general enough to include commonly studied problems such as, random instances of Not-All-Equal-SAT, k-XOR formulae, hypergraph 2-coloring, and graph k-coloring. An important new ingredient is a condition involving the Fourier expansion of clauses, which characterizes the class of problems with a similar threshold structure.
@cite_14: Consider a collection of random variables attached to the vertices of a graph. The reconstruction problem requires to estimate one of them given far away' observations. Several theoretical results (and simple algorithms) are available when their joint probability distribution is Markov with respect to a tree. In this paper we consider the case of sequences of random graphs that converge locally to trees. In particular, we develop a sufficient condition for the tree and graph reconstruction problem to coincide. We apply such condition to colorings of random graphs. Further, we characterize the behavior of Ising models on such graphs, both with attractive and random interactions (respectively, ferromagnetic' and spin glass').
In a recent paper, Gerschenfeld and the first author @cite_14 , considered the reconstruction problem for , which included the case of proper colorings of the vertices of a random graph. This amounts to understanding the correlation (as measured e.g. through mutual information) between the color of a vertex @math , and the colors of vertices at distance @math from @math . In particular, the problem is said to be unsolvable' if such a correlation decays to @math with @math . We refer to for a precise definition of the reconstruction problem. For a class of models, including the so-called Ising spin glass, the antiferromagnetic Potts model, and proper @math -colorings of a graph, @cite_14 derived a general sufficient condition, under which reconstruction for (sparse) random graphs @math with @math edges is possible if and only if it is possible for a Galton-Watson tree with independent @math degrees for each vertex. Moreover, they also verified that the condition holds for the Ising spin glass and the antiferromagnetic Potts at non-zero temperature, leaving open the case of proper colorings of graphs.