On the freezing of variables in random constraint satisfaction problems
From MaRDI portal
Publication:2473356
DOI10.1007/s10955-007-9417-7zbMath1139.82041arXiv0705.2147MaRDI QIDQ2473356
Publication date: 27 February 2008
Published in: Journal of Statistical Physics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0705.2147
05C80: Random graphs (graph-theoretic aspects)
82D30: Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses)
82B26: Phase transitions (general) in equilibrium statistical mechanics
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Related Items
Reconstruction of random colourings, Random subcubes as a toy model for constraint satisfaction problems, Replica cluster variational method
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A survey of max-type recursive distributional equations
- A threshold for unsatisfiability
- Reconstruction on trees and spin glass transition
- Gibbs measures and phase transitions
- Bounds for diluted mean-fields spin glass models
- Two solutions to diluted \(p\)-spin models and XORSAT problems
- Replica bounds for optimization problems and diluted spin systems
- Broken replica symmetry bounds in the mean field spin glass model
- On the dynamics of the glass transition on Bethe lattices
- The Parisi formula
- Singularity Analysis of Generating Functions
- Sharp thresholds of graph properties, and the $k$-sat problem
- Instability of one-step replica-symmetry-broken phase in satisfiability problems
- Entropy of theK-Satisfiability Problem
- Factor graphs and the sum-product algorithm
- Gibbs states and the set of solutions of random constraint satisfaction problems
- Threshold values of random K‐SAT from the cavity method
- Bicolouring random hypergraphs
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
- Results related to threshold phenomena research in satisfiability: Lower bounds
- Upper bounds on the satisfiability threshold
