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 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 \emph{satisfiability} threshold, the threshold for \emph{clustering} of the solution space, and the threshold for an appropriate \emph{reconstruction} problem on the CSP's. The bounds become asymptotically 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. This is joint work with Andrea Montanari (Stanford University) and Ricardo Restrepo (Georgia Tech.)
Copyright. All Rights Reserved.