On the survey-propagation equations in random constraint satisfiability problems

DOI10.1063/1.3030862zbMath1159.81335OpenAlexW2040951960WikidataQ57338428 ScholiaQ57338428MaRDI QIDQ3624676

Giorgio Parisi

Publication date: 30 April 2009

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

Full work available at URL: https://doi.org/10.1063/1.3030862

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Special processes (60K99) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Classical dynamic and nonequilibrium statistical mechanics (general) (82C05) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

The solution space structure of planted constraint satisfaction problems with growing domains, Clustering phase of a general constraint satisfaction problem model \(d\)-\(k\)-CSP, Generating hard satisfiable instances by planting into random constraint satisfaction problem model with growing constraint scope length

Cites Work

• Two solutions to diluted \(p\)-spin models and XORSAT problems
• Replica bounds for optimization problems and diluted spin systems
• The cavity method at zero temperature
• The ?(2) limit in the random assignment problem
• Coloring Random Graphs
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Survey propagation as local equilibrium equations
• A new look at survey propagation and its generalizations
• On the formal equivalence of the TAP and thermodynamic methods in the SK model
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• Entropy of theK-Satisfiability Problem
• Factor graphs and the sum-product algorithm
• Survey propagation: An algorithm for satisfiability