  Random constraint satisfaction problems play an important role in computer
science and combinatorics. For example, they provide challenging benchmark
instances for algorithms and they have been harnessed in probabilistic
constructions of combinatorial structures with peculiar features. In an
important contribution [Krzakala et al., PNAS 2007] physicists made several
predictions on the precise location and nature of phase transitions in random
constraint satisfaction problems. Specifically, they predicted that their
satisfiability thresholds are quite generally preceded by several other
thresholds that have a substantial impact both combinatorially and
computationally. These include the condensation phase transition, where
long-range correlations between variables emerge, and the reconstruction
threshold. In this paper we prove these physics predictions for a broad class
of random constraint satisfaction problems. Additionally, we obtain contiguity
results that have implications on Bayesian inference tasks, a subject that has
received a great deal of interest recently (e.g., [Banks et al., COLT 2016]).
