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
On the thresholds in linear and nonlinear Boolean equations, Reconstruction for the Potts model, Lack of strong completeness for stochastic flows, Reconstruction of random colourings, Random subcubes as a toy model for constraint satisfaction problems, Replica cluster variational method
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
