On the freezing of variables in random constraint satisfaction problems
From MaRDI portal
Publication:2473356
DOI10.1007/s10955-007-9417-7zbMath1139.82041arXiv0705.2147OpenAlexW2042243015MaRDI 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
Random graphs (graph-theoretic aspects) (05C80) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30) Phase transitions (general) in equilibrium statistical mechanics (82B26) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items (16)
On the sufficiency of pairwise interactions in maximum entropy models of networks ⋮ Reconstruction of random colourings ⋮ The asymptotics of the clustering transition for random constraint satisfaction problems ⋮ On the thresholds in linear and nonlinear Boolean equations ⋮ Curvature-driven pathways interpolating between stationary points: the case of the pure spherical 3-spin model ⋮ Random subcubes as a toy model for constraint satisfaction problems ⋮ The large deviations of the whitening process in random constraint satisfaction problems ⋮ The tightness of the Kesten-Stigum reconstruction bound of symmetric model with multiple mutations ⋮ Replica cluster variational method ⋮ Reconstruction for the Potts model ⋮ Lack of strong completeness for stochastic flows ⋮ Jamming transition in kinetically constrained models with reflection symmetry ⋮ Rigid Colorings of Hypergraphs and Contiguity ⋮ Function simulation, graph grammars and colourings ⋮ Biased landscapes for random constraint satisfaction problems ⋮ Generating hard satisfiable instances by planting into random constraint satisfaction problem model with growing constraint scope length
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
This page was built for publication: On the freezing of variables in random constraint satisfaction problems
