  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.
