On the freezing of variables in random constraint satisfaction problems

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.

32 pages, 7 figures

References in corpus (22)

• The Bethe lattice spin glass revisited
• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• A survey of max-type recursive distributional equations
• Clustering of solutions in the random satisfiability problem
• The Entropy of the K-Satisfiability Problem
• On the nature of the low-temperature phase in discontinuous mean-field spin glasses
• Reconstruction on trees and spin glass transition
• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• A variational description of the ground state structure in random satisfiability problems
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• On the dynamics of the glass transition on Bethe lattices
• Facilitated spin models on Bethe lattice: bootstrap percolation, mode-coupling transition and glassy dynamics
• Non-equilibrium work relations
• Landscape of solutions in constraint satisfaction problems
• Floppy modes and the free energy: Rigidity and connectivity percolation on Bethe Lattices
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
• Geometrical organization of solutions to random linear Boolean equations
• Random Graph Coloring - a Statistical Physics Approach
• Bicoloring Random Hypergraphs
• Long range frustration in finite connectivity spin glasses: A mean field theory and its application to the random $K$-satisfiability problem

Cited by in corpus (48)

• Mean field theory of hard sphere glasses and jamming
• Jamming versus Glass Transitions
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Critical scaling and heterogeneous superdiffusion across the jamming/rigidity transition of a granular glass
• Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• Circumspect descent prevails in solving random constraint satisfaction problems
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• The backtracking survey propagation algorithm for solving random K-SAT problems
• Following Gibbs States Adiabatically - The Energy Landscape of Mean Field Glassy Systems
• Constraint satisfaction problems with isolated solutions are hard
• Reconstruction of Random Colourings
• On the sufficiency of pairwise interactions in maximum entropy models of biological networks
• Identifying essential genes in E. coli from a metabolic optimization principle
• Random subcubes as a toy model for constraint satisfaction problems
• Exhaustive enumeration unveils clustering and freezing in random 3-SAT
• Statistical Mechanics of maximal independent sets
• Replica Cluster Variational Method
• Biased landscapes for random Constraint Satisfaction Problems
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• The large deviations of the whitening process in random constraint satisfaction problems
• Ground-state topology of the Edwards-Anderson +/-J spin glass model
• Reconstruction of symmetric Potts Models
• The statistical mechanics of random set packing and a generalization of the Karp-Sipser algorithm
• Glassy Behavior and Jamming of a Random Walk Process for Sequentially Satisfying a Constraint Satisfaction Formula
• Ground-state configuration space heterogeneity of random finite-connectivity spin glasses and random constraint satisfaction problems
• Enhancing the efficiency of quantum annealing via reinforcement: A path-integral Monte Carlo simulation of the quantum reinforcement algorithm
• The Tightness of the Kesten-Stigum Reconstruction Bound of Symmetric Model with Multiple Mutations
• The asymptotics of the clustering transition for random constraint satisfaction problems
• Generating Hard Ising Instances With Planted Solutions Using Post-Quantum Cryptographic Protocols
• Entropic barriers as a reason for hardness in both classical and quantum algorithms
• The Ising spin glass on random graphs at zero temperature: not all spins are glassy in the glassy phase
• Realizing interdependent couplings as thermal or higher-order interactions
• Understanding the computational difficulty of a binary-weight perceptron and the advantage of input sparseness
• Self-Sustained Clusters as Drivers of Computational Hardness in $p$-spin Models
• Solution space heterogeneity of the random K-satisfiability problem: Theory and simulations
• On the behaviour of random K-SAT on trees
• Jamming transition in kinetically constrained models with reflection symmetry
• Slow Spin Dynamics and Self-Sustained Clusters in Sparsely Connected Systems
• Reconstruction/Non-reconstruction Thresholds for Colourings of General Galton-Watson Trees
• Computing a Knot Invariant as a Constraint Satisfaction Problem
• Inside the clustering window for random linear equations
• Systematic perturbation approach for a dynamical scaling law in a kinetically constrained spin model
• Rigid colourings of hypergraphs and contiguity
• Broadcasting colourings on trees. A combinatorial view
• An alternate view of complexity in k-SAT problems