2008/02/29 by Andrea Montanari, Federico Ricci-Tersenghi, Federico Ricci‐Tersenghi +1 · 2 citations
Computer Science · Mathematics · Physics and Astronomy · #Bayesian Modeling and Causal Inference #Combinatorics #Constraint Satisfaction and Optimization #Discrete mathematics #Entropy (arrow of time) #Exponential function #Formalism (music) #Markov Chains and Monte Carlo Methods #Mathematical analysis #Mathematics #Phase transition #Physics #Quantum mechanics #Replica #Replica trick #Satisfiability #Statistical physics #Symmetry breaking #cond-mat.dis-nn #cond-mat.stat-mech #cs.CC
paper · pdf · doi:10.1088/1742-5468/2008/04/p04004
published as J. Stat. Mech. P04004 (2008) · 30 pages, 14 figures, typos corrected, discussion of appendix C expanded with a new figure
arxiv created 2008/02/29 · openalex publication_date 2008/04/01 · arxiv updated 2009/12/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
We study the set of solutions of random k -satisfiability formulas through the cavity method. It is known that, for an interval of the clause-to-variables ratio, this decomposes into an exponential number of pure states (clusters). We refine substantially this picture by: (i) determining the precise location of the clustering transition; (ii) uncovering a second ‘condensation’ phase transition in the structure of the solution set for k ≥4. These results both follow from computing the large deviation rate of the internal entropy of pure states. From a technical point of view our main contributions are a simplified version of the cavity formalism for special values of the Parisi replica symmetry breaking parameter m (in particular for m = 1 via a correspondence with the tree reconstruction problem) and new large- k expansions.