Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems

Abstract

An instance of a random constraint satisfaction problem defines a random subset S (the set of solutions) of a large product space (the set of assignments). We consider two prototypical problem ensembles (random k-satisfiability and q-coloring of random regular graphs), and study the uniform measure with support on S. As the number of constraints per variable increases, this measure first decomposes into an exponential number of pure states ("clusters"), and subsequently condensates over the largest such states. Above the condensation point, the mass carried by the n largest states follows a Poisson-Dirichlet process. For typical large instances, the two transitions are sharp. We determine for the first time their precise location. Further, we provide a formal definition of each phase transition in terms of different notions of correlation between distinct variables in the problem. The degree of correlation naturally affects the performances of many search/sampling algorithms. Empirical evidence suggests that local Monte Carlo Markov Chain strategies are effective up to the clustering phase transition, and belief propagation up to the condensation point. Finally, refined message passing techniques (such as survey propagation) may beat also this threshold.

6 pages, 6 figures, slightly revised version

References in corpus (2)

• Clustering of solutions in the random satisfiability problem
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs

Cited by in corpus (116)

• Critical phenomena in complex networks
• Theoretical perspective on the glass transition and amorphous materials
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Challenges and Opportunities in Quantum Optimization
• A Landscape Analysis of Constraint Satisfaction Problems
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Following the evolution of glassy states under external perturbations: compression and shear-strain
• Simple Glass Models and their Quantum Annealing
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• On the freezing of variables in random constraint satisfaction problems
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• On the path integral representation for quantum spin models and its application to the quantum cavity method and to Monte Carlo simulations
• Circumspect descent prevails in solving random constraint satisfaction problems
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• On quantum mean-field models and their quantum annealing
• Origin of the computational hardness for learning with binary synapses
• Locked constraint satisfaction problems
• Constraint satisfaction problems with isolated solutions are hard
• Mean-field theory for the inverse Ising problem at low temperatures
• Reconstruction of Random Colourings
• Statistical Mechanics of Steiner trees
• Information-theoretic thresholds for community detection in sparse networks
• Potts Glass on Random Graphs
• Statistical Mechanics of the Minimum Dominating Set Problem
• Minimal contagious sets in random regular graphs
• Relaxation dynamics in the energy landscape of glass-forming liquids
• Random subcubes as a toy model for constraint satisfaction problems
• A Lattice Model for Colloidal Gels and Glasses
• Exhaustive enumeration unveils clustering and freezing in random 3-SAT
• Machine-learning-assisted Monte Carlo fails at sampling computationally hard problems
• Approximating the XY model on a random graph with a $q$-state clock model
• Limits and performances of algorithms based on simulated annealing in solving sparse hard inference problems
• A solvable model of quantum random optimization problems
• Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective
• A rigorous analysis of the cavity equations for the minimum spanning tree
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Irreversible Monte Carlo algorithms for hard disk glasses: from event-chain to collective swaps
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• Solving Boolean satisfiability problems with resistive content addressable memories
• Quantum memory at nonzero temperature in a thermodynamically trivial system
• Hard Optimization Problems have Soft Edges
• $T\to 0$ mean-field population dynamics approach for the random 3-satisfiability problem
• Ground-State Entropy of the Random Vertex-Cover Problem
• Statistical physics of hard combinatorial optimization: The vertex cover problem
• Reconstruction of symmetric Potts Models
• Entropic Effects in the Very Low Temperature Regime of Diluted Ising Spin Glasses with Discrete Couplings
• Zero temperature solutions of the Edwards-Anderson model in random Husimi Lattices
• Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems
• Spectral estimation of the percolation transition in clustered networks
• Cycle-tree guided attack of random K-core: Spin glass model and efficient message-passing algorithm
• Minimizing Unsatisfaction in Colourful Neighbourhoods
• Ground-state configuration space heterogeneity of random finite-connectivity spin glasses and random constraint satisfaction problems
• Complex Replica Zeros of $\pm J$ Ising Spin Glass at Zero Temperature
• On the Atypical Solutions of the Symmetric Binary Perceptron
• Optimal control of a quantum sensor: A fast algorithm based on an analytic solution
• Random Constraint Satisfaction Problems
• Convergence of multivariate belief propagation, with applications to cuckoo hashing and load balancing
• Minimal Dominating Set problem studied by simulated annealing and cavity method: Analytics and population dynamics
• Learning by random walks in the weight space of the Ising perceptron
• PDP: A General Neural Framework for Learning Constraint Satisfaction Solvers
• Finite size scaling of the de Almeida-Thouless instability in random sparse networks
• Constraint optimization and landscapes
• Localization in the Discrete Non-Linear Schrödinger Equation and geometric properties of the microcanonical surface
• An improved Belief Propagation algorithm finds many Bethe states in the random field Ising model on random graphs
• Gibbs Measures and Phase Transitions on Sparse Random Graphs
• Maximally flexible solutions of a random $K$-satisfiability formula
• Clustering of solutions in hard satisfiability problems
• Polynomial Time Quantum Gibbs Sampling for Fermi-Hubbard Model at any Temperature
• Broadcasting on Two-Dimensional Regular Grids
• Biased measures for random Constraint Satisfaction Problems: larger interaction range and asymptotic expansion
• Optimization of the dynamic transition in the continuous coloring problem
• Relationship between clustering and algorithmic phase transitions in the random k-XORSAT model and its NP-complete extensions
• Partial local entropy and anisotropy in deep weight spaces
• Introduction to Phase Transitions in Random Optimization Problems
• Entropic barriers as a reason for hardness in both classical and quantum algorithms
• Statistical Mechanics of the Quantum K-Satisfiability problem
• Realizing interdependent couplings as thermal or higher-order interactions
• A residual-based message passing algorithm for constraint satisfaction problems
• Poisson-Dirichlet asymptotics in condensing particle systems
• The effect of quantum fluctuations on the coloring of random graphs
• A model with Darwinian dynamics on a rugged landscape
• What makes a phase transition? Analysis of the random satisfiability problem
• A simple one dimensional glassy Kac model
• The solution space structure of planted constraint satisfaction problems with growing domains
• Critical properties of disordered XY model on sparse random graphs
• Entropic long range order in a 3D spin glass model
• Organization mechanism and counting algorithm on Vertex-Cover solutions
• K-core attack, equilibrium K-core, and kinetically constrained spin system
• Reconstruction/Non-reconstruction Thresholds for Colourings of General Galton-Watson Trees
• The replica symmetric solution for Potts models on d-regular graphs
• The planted XY model: thermodynamics and inference
• Statistical mechanics of classical and quantum computational complexity
• Breaking of 1RSB in random MAX-NAE-SAT
• Bose-Einstein Condensation in Satisfiability Problems
• Algebraic dynamical systems from LDPC codes satisfy a strong negation of the weak Pinsker property
• Hearings and mishearings: decrypting the spoken word
• Academic Meeting Scheduling Using an Antiferromagnetic Potts Model
• Satisfiability transition in asymmetric neural networks
• Frozen $1$-RSB structure of the symmetric Ising perceptron
• Phase transition in the bipartite z-matching
• Algorithmic thresholds in combinatorial optimization depend on the time scaling
• Uniformly Random Colourings of Sparse Graphs
• Gibbs state sampling via cluster expansions
• Cluster structure of optimal solutions in bipartitioning of small worlds
• Biased thermodynamics can explain the behaviour of smart optimization algorithms that work above the dynamical threshold
• Complete Realization of Energy Landscape and Non-equilibrium Trapping Dynamics in Spin Glass and Optimization Problem
• Minority Takeover in Majority Dynamics: Searching for Rare Initializations via the History Passing Algorithm
• Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)
• Concentration of the number of solutions of random planted CSPs and Goldreich's one-way candidates
• CCCP Algorithms to Minimize the Bethe free energy of 3-SAT Problem
• Rényi complexity in mean-field disordered systems
• Dynamical Cavity Method for Hypergraphs and its Application to Quenches in the k-XOR-SAT Problem
• Interacting Copies of Random Constraint Satisfaction Problems
• Planted matching problems on random hypergraphs