An instance of a random constraint satisfaction problem defines a random subset 𝒮 (the set of solutions) of a large product spaceX^N(the set of assignments). We consider two prototypical problem ensembles (randomk-satisfiability andq-coloring of random regular graphs) and study the uniform measure with support onS. 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 thenlargest states follows a Poisson-Dirichlet process. For typical large instances, the two transitions are sharp. We determine 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 also beat this threshold.

Significance: Modern data analysis requires solving hard optimization problems with a large number of parameters and a large number of constraints. A successful approach is to replace these hard problems by surrogate problems that are convex and hence tractable. Semidefinite programming relaxations offer a powerful method to construct such relaxations. In many instances it was observed that a semidefinite relaxation becomes very accurate when the noise level in the data decreases below a certain threshold. We develop a new method to compute these noise thresholds (or phase transitions) using ideas from statistical physics.

We report a high-precision finite-size scaling study of the critical behavior of the three-dimensional Ising Edwards-Anderson model (the Ising spin glass). We have thermalized lattices up to $L=40$ using the Janus dedicated computer. Our analysis takes into account leading-order corrections to scaling. We obtain ${T}_{\mathrm{c}}=1.1019(29)$ for the critical temperature, $$\nu${}=2.562(42)$ for the thermal exponent, $$\eta${}=$-${}0.3900(36)$ for the anomalous dimension, and $$\omega${}=1.12(10)$ for the exponent of the leading corrections to scaling. Standard (hyper)scaling relations yield $$\alpha${}=$-${}5.69(13)$, $$\beta${}=0.782(10)$, and $$\gamma${}=6.13(11)$. We also compute several universal quantities at ${T}_{\mathrm{c}}$.