  An instance of a random constraint satisfaction problem defines a random
subset S (the set of solutions) of a large product space (the set of
assignments). We consider two prototypical problem ensembles (random
k-satisfiability and q-coloring of random regular graphs), and study the
uniform measure with support on S. As the number of constraints per variable
increases, this measure first decomposes into an exponential number of pure
states ("clusters"), and subsequently condensates over the largest such states.
Above the condensation point, the mass carried by the n largest states follows
a Poisson-Dirichlet process.
  For typical large instances, the two transitions are sharp. We determine for
the first time their precise location. Further, we provide a formal definition
of each phase transition in terms of different notions of correlation between
distinct variables in the problem.
  The degree of correlation naturally affects the performances of many
search/sampling algorithms. Empirical evidence suggests that local Monte Carlo
Markov Chain strategies are effective up to the clustering phase transition,
and belief propagation up to the condensation point. Finally, refined message
passing techniques (such as survey propagation) may beat also this threshold.
