On the freezing of variables in random constraint satisfaction problems
From MaRDI portal
Publication:2473356
Random graphs (graph-theoretic aspects) (05C80) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Phase transitions (general) in equilibrium statistical mechanics (82B26) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30)
Abstract: The set of solutions of random constraint satisfaction problems (zero energy groundstates of mean-field diluted spin glasses) undergoes several structural phase transitions as the amount of constraints is increased. This set first breaks down into a large number of well separated clusters. At the freezing transition, which is in general distinct from the clustering one, some variables (spins) take the same value in all solutions of a given cluster. In this paper we study the critical behavior around the freezing transition, which appears in the unfrozen phase as the divergence of the sizes of the rearrangements induced in response to the modification of a variable. The formalism is developed on generic constraint satisfaction problems and applied in particular to the random satisfiability of boolean formulas and to the coloring of random graphs. The computation is first performed in random tree ensembles, for which we underline a connection with percolation models and with the reconstruction problem of information theory. The validity of these results for the original random ensembles is then discussed in the framework of the cavity method.
Recommendations
- Frozen variables in random Boolean constraint satisfaction problems
- scientific article; zbMATH DE number 1002207
- Randomized approximation of the constraint satisfaction problem
- Recognizing frozen variables in constraint satisfaction problems
- The Resolution Complexity of Random Constraint Satisfaction Problems
- Random constraint satisfaction: Flaws and structure
- Models for Random Constraint Satisfaction Problems
- A general model and thresholds for random constraint satisfaction problems
- The satisfiability threshold for a seemingly intractable random constraint satisfaction problem
- Phase transitions of random constraint satisfaction problems
Cites work
- A survey of max-type recursive distributional equations
- A threshold for unsatisfiability
- Bicolouring random hypergraphs
- Bounds for diluted mean-fields spin glass models
- Broken replica symmetry bounds in the mean field spin glass model
- Entropy of theK-Satisfiability Problem
- Factor graphs and the sum-product algorithm
- Gibbs measures and phase transitions
- Gibbs states and the set of solutions of random constraint satisfaction problems
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1273988 (Why is no real title available?)
- scientific article; zbMATH DE number 1952026 (Why is no real title available?)
- scientific article; zbMATH DE number 1834589 (Why is no real title available?)
- Instability of one-step replica-symmetry-broken phase in satisfiability problems
- On the dynamics of the glass transition on Bethe lattices
- Reconstruction on trees and spin glass transition
- Replica bounds for optimization problems and diluted spin systems
- Results related to threshold phenomena research in satisfiability: Lower bounds
- Sharp thresholds of graph properties, and the k-sat problem
- Singularity Analysis of Generating Functions
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
- The Parisi formula
- Threshold values of random K‐SAT from the cavity method
- Two solutions to diluted p-spin models and XORSAT problems
- Upper bounds on the satisfiability threshold
Cited in
(21)- The tightness of the Kesten-Stigum reconstruction bound of symmetric model with multiple mutations
- Generating hard satisfiable instances by planting into random constraint satisfaction problem model with growing constraint scope length
- Jamming transition in kinetically constrained models with reflection symmetry
- The asymptotics of the clustering transition for random constraint satisfaction problems
- Function simulation, graph grammars and colourings
- On the sufficiency of pairwise interactions in maximum entropy models of networks
- Boolean constraint satisfaction problems for reaction networks
- The large deviations of the whitening process in random constraint satisfaction problems
- Biased landscapes for random constraint satisfaction problems
- Random formulas have frozen variables
- Rigid colorings of hypergraphs and contiguity
- Frozen variables in random Boolean constraint satisfaction problems
- A continuous constraint satisfaction problem for the rigidity transition in confluent tissues
- Curvature-driven pathways interpolating between stationary points: the case of the pure spherical 3-spin model
- On the thresholds in linear and nonlinear Boolean equations
- Counting and hardness-of-finding fixed points in cellular automata on random graphs
- 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
This page was built for publication: On the freezing of variables in random constraint satisfaction problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2473356)
