Clusters of solutions and replica symmetry breaking in random k-satisfiability

Abstract

We study the set of solutions of random k-satisfiability formulae through the cavity method. It is known that, for an interval of the clause-to-variables ratio, this decomposes into an exponential number of pure states (clusters). We refine substantially this picture by: (i) determining the precise location of the clustering transition; (ii) uncovering a second `condensation' phase transition in the structure of the solution set for k larger or equal than 4. These results both follow from computing the large deviation rate of the internal entropy of pure states. From a technical point of view our main contributions are a simplified version of the cavity formalism for special values of the Parisi replica symmetry breaking parameter m (in particular for m=1 via a correspondence with the tree reconstruction problem) and new large-k expansions.

30 pages, 14 figures, typos corrected, discussion of appendix C expanded with a new figure

References in corpus (26)

• The Bethe lattice spin glass revisited
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• On the Adam-Gibbs-Wolynes scenario for the viscosity increase in glasses
• The structural glass transition and the entropy of the metastable states
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Phase Transitions in the Coloring of Random Graphs
• Recipes for metastable states in Spin Glasses
• Rigorous Inequalities between Length and Time Scales in Glassy Systems
• Statistical mechanics of the random K-SAT model
• On the nature of the low-temperature phase in discontinuous mean-field spin glasses
• 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
• A variational description of the ground state structure in random satisfiability problems
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• Mosaic multi-state scenario vs. one-state description of supercooled liquids
• On the freezing of variables in random constraint satisfaction problems
• On the dynamics of the glass transition on Bethe lattices
• Glauber dynamics on trees:Boundary conditions and mixing time
• Focused Local Search for Random 3-Satisfiability
• Landscape of solutions in constraint satisfaction problems
• Pairs of SAT Assignment in Random Boolean Formulae
• Potts Glass on Random Graphs
• Higher-order QED corrections to single-W production in electron-positron collisions
• Spin glass models with ferromagnetically biased couplings on the Bethe lattice: analytic solutions and numerical simulations
• Near optimal configurations in mean field disordered systems

Cited by in corpus (65)

• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• Cavity method for quantum spin glasses on the Bethe lattice
• On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms
• An event-based architecture for solving constraint satisfaction problems
• Exact thresholds for Ising-Gibbs samplers on general graphs
• Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems
• Locked constraint satisfaction problems
• The backtracking survey propagation algorithm for solving random K-SAT problems
• Constraint satisfaction problems with isolated solutions are hard
• Minimal contagious sets in random regular graphs
• Exhaustive enumeration unveils clustering and freezing in random 3-SAT
• Threshold Saturation in Spatially Coupled Constraint Satisfaction Problems
• Entropy landscape of solutions in the binary perceptron problem
• Statistical Mechanics of maximal independent sets
• Limits and performances of algorithms based on simulated annealing in solving sparse hard inference problems
• Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
• Biased landscapes for random Constraint Satisfaction Problems
• Phase transitions in the $q$-coloring of random hypergraphs
• The large deviations of the whitening process in random constraint satisfaction problems
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• Energy landscapes of combinatorial optimization in Ising machines
• Communities of solutions in single solution clusters of a random K-Satisfiability formula
• Characterizing and Improving Generalized Belief Propagation Algorithms on the 2D Edwards-Anderson Model
• Statistical physics of hard combinatorial optimization: The vertex cover problem
• $T\to 0$ mean-field population dynamics approach for the random 3-satisfiability problem
• Ground-State Entropy of the Random Vertex-Cover Problem
• Weight space structure and analysis using a finite replica number in the Ising perceptron
• Numerical Solution-Space Analysis of Satisfiability Problems
• Replica symmetry breaking, complexity and spin representation in the generalized random energy model
• Solution space structure of random constraint satisfaction problems with growing domains
• A very fast inference algorithm for finite-dimensional spin glasses: Belief Propagation on the dual lattice
• Random-field p-spin glass model on regular random graphs
• Ground-state configuration space heterogeneity of random finite-connectivity spin glasses and random constraint satisfaction problems
• Glassy Behavior and Jamming of a Random Walk Process for Sequentially Satisfying a Constraint Satisfaction Formula
• Enhancing the efficiency of quantum annealing via reinforcement: A path-integral Monte Carlo simulation of the quantum reinforcement algorithm
• Minimal Dominating Set problem studied by simulated annealing and cavity method: Analytics and population dynamics
• Spin glass phase transitions in the random feedback vertex set problem
• New Understanding of the Bethe Approximation and the Replica Method
• Maximally flexible solutions of a random $K$-satisfiability formula
• The asymptotics of the clustering transition for random constraint satisfaction problems
• Optimization of the dynamic transition in the continuous coloring problem
• Entropic barriers as a reason for hardness in both classical and quantum algorithms
• Adversarial Satisfiability Problem
• The network source location problem: ground state energy, entropy and effects of freezing
• Realizing interdependent couplings as thermal or higher-order interactions
• A residual-based message passing algorithm for constraint satisfaction problems
• Self-Sustained Clusters as Drivers of Computational Hardness in $p$-spin Models
• Quantum Cluster Variational Method and Message Passing Algorithms Revisited
• On the behaviour of random K-SAT on trees
• The solution space structure of planted constraint satisfaction problems with growing domains
• Solution space heterogeneity of the random K-satisfiability problem: Theory and simulations
• Entropic long range order in a 3D spin glass model
• Boolean constraint satisfaction problems for reaction networks
• Replica Symmetry and Replica Symmetry Breaking for the Traveling Salesperson Problem
• Slow Spin Dynamics and Self-Sustained Clusters in Sparsely Connected Systems
• Perturbed Message Passing for Constraint Satisfaction Problems
• Bose-Einstein Condensation in Satisfiability Problems
• Approaching the ground states of the random maximum two-satisfiability problem by a greedy single-spin flipping process
• 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
• Replica analysis of Franz-Parisi potential for sparse systems
• The closest vector problem and the zero-temperature p-spin landscape for lossy compression
• Minority Takeover in Majority Dynamics: Searching for Rare Initializations via the History Passing Algorithm
• Interacting Copies of Random Constraint Satisfaction Problems