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

Gibbs states and the set of solutions of random constraint satisfaction problems / F., Krzakala; A., Montanari; RICCI TERSENGHI, Federico; G., Semerjian; L., Zdeborova. - In: PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA. - ISSN 0027-8424. - STAMPA. - 104:25(2007), pp. 10318-10323. [10.1073/pnas.0703685104]

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

RICCI TERSENGHI, Federico;
2007

Abstract

An instance of a random constraint satisfaction problem defines a random subset S (the set of solutions) of a large product space chi(N) (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.
2007
message passing algorithms; phase transitions; random graphs
01 Pubblicazione su rivista::01a Articolo in rivista
Gibbs states and the set of solutions of random constraint satisfaction problems / F., Krzakala; A., Montanari; RICCI TERSENGHI, Federico; G., Semerjian; L., Zdeborova. - In: PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA. - ISSN 0027-8424. - STAMPA. - 104:25(2007), pp. 10318-10323. [10.1073/pnas.0703685104]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/131313
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? 12
  • Scopus 367
  • ???jsp.display-item.citation.isi??? 326
social impact