Instability of one-step replica-symmetry-broken phase in satisfiability problems

DOI10.1088/0305-4470/37/6/008zbMath1116.82308arXivcond-mat/0308147OpenAlexW4297799124MaRDI QIDQ4466289

Federico Ricci-Tersenghi, Giorgio Parisi, Andrea Montanari

Publication date: 9 June 2004

Published in: Journal of Physics A: Mathematical and General (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cond-mat/0308147

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial probability (60C05) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30)

Related Items

On the number of circuits in random graphs, Tutorial series on brain-inspired computing. V: Statistical mechanics of communication and computation, On the thresholds in linear and nonlinear Boolean equations, Analysis of local search landscapes for \(k\)-SAT instances, Phase transitions in theq-coloring of random hypergraphs, Leveraging cluster backbones for improving MAP inference in statistical relational models, Next nearest neighbour Ising models on random graphs, Diluted mean-field spin-glass models at criticality, On the freezing of variables in random constraint satisfaction problems, Pairs of SAT-assignments in random Boolean formulæ, On the survey-propagation equations in random constraint satisfiability problems, The network source location problem: ground state energy, entropy and effects of freezing, The theoretical capacity of the Parity Source Coder, A hard-sphere model on generalized Bethe lattices: statics, Statistical and algebraic analysis of a family of random Boolean equations, Approximate survey propagation for statistical inference, Minimal contagious sets in random regular graphs