Gibbs states and the set of solutions of random constraint satisfaction problems

By Florent Krzakala, Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian, Lenka Zdeborov'a. Proceedings of the National Academy of Sciences of the United States of America, 2006

488 citations recorded by the source corpus.

An instance of a random constraint satisfaction problem defines a random subset 𝒮 (the set of solutions) of a large product space XN (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.

Subfields: Artificial Intelligence, Computer Networks and Communications, Signal Processing

View Paper: https://www.semanticscholar.org/paper/f4f866c8fab8a72a37e3c3e6508499a9f95931af

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Signal Processing

Citations in the corpus

Ising models on locally tree-like graphs (2008, background): “(1.1) These distributions are parametrized by the ‘magnetic field’ B and ‘inverse temperature’ β ≥ 0, where the partition function Z(β,B) is fixed by the normalization condition ∑ x µ(x) = 1.”
Theoretical perspective on the glass transition and amorphous materials (2010, methodology): “We simply illustrate it pointing out that a central problem in optimization, random k-satisfiability, has been shown to undergo a glass transition when α increases that is reminiscent of the one of structural glasses and can be treated analytically using similar tools (Krzakala et al., 2007).”
Universality of the SAT-UNSAT (jamming) threshold in non-convex continuous constraint satisfaction problems (2017, background): “We do not discuss in details the properties of this transition, for which we refer to [ 4, 30, 32 ] .”
On the solution-space geometry of random constraint satisfaction problems (2006, unknown): “, [15]).”
Challenges and opportunities in quantum optimization (2023, unknown): “Its significance in optimization, particularly in classical Markov-chain Monte Carlo algorithms, extends to solving problems such as constraint satisfaction 243 .”
Comparing dynamics: deep neural networks versus glassy systems (2018, background): “…similarities with the one found in several combinatorial optimization problems in which easy, hard and impossible algorithmic phases have been found, see e.g. (Monasson et al., 1999; M´ezard et al., 2002; Krzakała et al., 2007; Zdeborov´a & Krzakala, 2016; Achlioptas & Coja-Oghlan, 2008).”
Statistical physics of inference: thresholds and algorithms (2015, methodology): “[171] Florent Krzakala, Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian, and Lenka Zdeborová.”