The large deviations of the whitening process in random constraint satisfaction problems
arXiv:1602.01700 · doi:10.1088/1742-5468/2016/05/053401
Abstract
Random constraint satisfaction problems undergo several phase transitions as the ratio between the number of constraints and the number of variables is varied. When this ratio exceeds the satisfiability threshold no more solutions exist; the satisfiable phase, for less constrained problems, is itself divided in an unclustered regime and a clustered one. In the latter solutions are grouped in clusters of nearby solutions separated in configuration space from solutions of other clusters. In addition the rigidity transition signals the appearance of so-called frozen variables in typical solutions: beyond this threshold most solutions belong to clusters with an extensive number of variables taking the same values in all solutions of the cluster. In this paper we refine the description of this phenomenon by estimating the location of the freezing transition, corresponding to the disappearance of all unfrozen solutions (not only typical ones). We also unveil phase transitions for the existence and uniqueness of locked solutions, in which all variables are frozen. From a technical point of view we characterize atypical solutions with a number of frozen variables different from the typical value via a large deviation study of the dynamics of a stripping process (whitening) that unveils the frozen variables of a solution, building upon recent works on atypical trajectories of the bootstrap percolation dynamics. Our results also bear some relevance from an algorithmic perspective, previous numerical studies having shown that heuristic algorithms of various kinds usually output unfrozen solutions.
arXiv comment55 pages, 32 figures. v2: additional discussion of locked solutions. v3: erroneous value l_c(k=4) was corrected from 19 to 17 in Table I
References in corpus (52)
- Theoretical perspective on the glass transition and amorphous materials
- The Bethe lattice spin glass revisited
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- Phase Transitions in the Coloring of Random Graphs
- Rigorous Inequalities between Length and Time Scales in Glassy Systems
- Survey propagation: an algorithm for satisfiability
- A Landscape Analysis of Constraint Satisfaction Problems
- Reconstruction on trees and spin glass transition
- Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
- Learning by message-passing in networks of discrete synapses
- Survey Propagation as local equilibrium equations
- A variational description of the ground state structure in random satisfiability problems
- Clusters of solutions and replica symmetry breaking in random k-satisfiability
- Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses
- On the freezing of variables in random constraint satisfaction problems
- On the dynamics of the glass transition on Bethe lattices
- Trajectories in phase diagrams, growth processes and computational complexity: how search algorithms solve the 3-Satisfiability problem
- Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation
- A better algorithm for random k-SAT
- Optimizing spread dynamics on graphs by message passing
- Generalization of the cavity method for adiabatic evolution of Gibbs states
- The asymptotic -SAT threshold
- Circumspect descent prevails in solving random constraint satisfaction problems
- Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
- On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms
- Behavior of heuristics and state space structure near SAT/UNSAT transition
- On large deviation properties of Erdos-Renyi random graphs
- Relaxation and Metastability in the RandomWalkSAT search procedure
- Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems
- Locked constraint satisfaction problems
- Constraint satisfaction problems with isolated solutions are hard
- The backtracking survey propagation algorithm for solving random K-SAT problems
- Pairs of SAT Assignment in Random Boolean Formulae
- Large deviations of cascade processes on graphs
- Reconstruction of Random Colourings
- Catching the k-NAESAT Threshold
- On local equilibrium equations for clustering states
- The cavity method at zero temperature
- The condensation transition in random hypergraph 2-coloring
- Minimal contagious sets in random regular graphs
- Exhaustive enumeration unveils clustering and freezing in random 3-SAT
- Constraint Satisfaction by Survey Propagation
- Proof of the satisfiability conjecture for large k
- Bicoloring Random Hypergraphs
- Alternative solutions to diluted p-spin models and XORSAT problems
- A positive temperature phase transition in random hypergraph 2-coloring
- Analysing Survey Propagation Guided Decimation on Random Formulas
- Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem
- The set of solutions of random XORSAT formulae
- Properties of atypical graphs from negative complexities
- Efficient data compression from statistical physics of codes over finite fields
- The decimation process in random k-SAT
Cited by in corpus (16)
- Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
- The backtracking survey propagation algorithm for solving random K-SAT problems
- Walksat stalls well below the satisfiability threshold
- Generating dense packings of hard spheres by soft interaction design
- On the role of synaptic stochasticity in training low-precision neural networks
- Phase transitions in the -coloring of random hypergraphs
- Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs
- Optimization of the dynamic transition in the continuous coloring problem
- Biased measures for random Constraint Satisfaction Problems: larger interaction range and asymptotic expansion
- Cutting-Plane Algorithms and Solution Whitening for the Vertex-Cover Problem
- Self-Sustained Clusters as Drivers of Computational Hardness in -spin Models
- Slow Spin Dynamics and Self-Sustained Clusters in Sparsely Connected Systems
- Algorithmic thresholds in combinatorial optimization depend on the time scaling
- Biased thermodynamics can explain the behaviour of smart optimization algorithms that work above the dynamical threshold
- Interacting Copies of Random Constraint Satisfaction Problems
- Rigid colourings of hypergraphs and contiguity