2006/12/31 by Florent Krząkała, Florent Krzakala, Andrea Montanari +5 · 4 citations
Computer Science · Physics and Astronomy · #Bayesian Modeling and Causal Inference #Constraint Satisfaction and Optimization #Data Management and Algorithms #cond-mat.dis-nn #cond-mat.stat-mech #cs.CC
paper · pdf · doi:10.1073/pnas.0703685104
published as Proc. Natl. Acad. Sci. 104, 10318 (2007) · 6 pages, 6 figures, slightly revised version
arxiv created 2007/02/26 · openalex publication_date 2007/06/14 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An instance of a random constraint satisfaction problem defines a random subset (the set of solutions) of a large product space chiN (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 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.