The large deviations of the whitening process in random constraint satisfaction problems

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.

55 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 (20)

• Theoretical perspective on the glass transition and amorphous materials
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Rigorous Inequalities between Length and Time Scales in Glassy Systems
• Survey propagation: an algorithm for satisfiability
• A Landscape Analysis of Constraint Satisfaction Problems
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• On the freezing of variables in random constraint satisfaction problems
• 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
• Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems
• Locked constraint satisfaction problems
• Constraint satisfaction problems with isolated solutions are hard
• Reconstruction of Random Colourings
• The cavity method at zero temperature
• On local equilibrium equations for clustering states
• Minimal contagious sets in random regular graphs
• Exhaustive enumeration unveils clustering and freezing in random 3-SAT
• Alternative solutions to diluted p-spin models and XORSAT problems
• Analysing Survey Propagation Guided Decimation on Random Formulas

Cited by in corpus (15)

• Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
• 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 $q$-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
• Self-Sustained Clusters as Drivers of Computational Hardness in $p$-spin Models
• Cutting-Plane Algorithms and Solution Whitening for the Vertex-Cover Problem
• 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