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 (9)

• The Bethe lattice spin glass revisited
• Clustering of solutions in the random satisfiability problem
• Coloring random graphs
• Reconstruction on trees and spin glass transition
• Survey Propagation as local equilibrium equations
• A variational description of the ground state structure in random satisfiability problems
• On the cooling-schedule dependence of the dynamics of mean-field glasses
• Landscape of solutions in constraint satisfaction problems
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs

Cited by in corpus (257)

• Critical phenomena in complex networks
• Theoretical perspective on the glass transition and amorphous materials
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Mean field theory of hard sphere glasses and jamming
• Statistical physics of inference: Thresholds and algorithms
• Phase Transitions in the Coloring of Random Graphs
• Ising models on locally tree-like graphs
• 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
• Algorithmic barriers from phase transitions
• Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Universality of the SAT-UNSAT (jamming) threshold in non-convex continuous 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
• First-order transitions and the performance of quantum algorithms in random optimization problems
• Microscopic theory of the jamming transition of harmonic spheres
• Information-theoretic thresholds from the cavity method
• Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation
• A better algorithm for random k-SAT
• 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
• The asymptotic $k$-SAT threshold
• Statistical mechanics of complex neural systems and high dimensional data
• 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
• On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms
• Perspective: Gardner Physics in Amorphous Solids and Beyond
• Origin of the computational hardness for learning with binary synapses
• 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
• Constraint satisfaction problems with isolated solutions are hard
• The backtracking survey propagation algorithm for solving random K-SAT problems
• Following Gibbs States Adiabatically - The Energy Landscape of Mean Field Glassy Systems
• Mean-field theory for the inverse Ising problem at low temperatures
• Out-of-equilibrium dynamical mean-field equations for the perceptron model
• Reconstruction of Random Colourings
• Catching the k-NAESAT Threshold
• On independent sets in random graphs
• Statistical Mechanics of Steiner trees
• On the sufficiency of pairwise interactions in maximum entropy models of biological networks
• Networking - A Statistical Physics Perspective
• The Cavity Approach to Parallel Dynamics of Ising Spins on a Graph
• The Phase Diagram of 1-in-3 Satisfiability Problem
• Comparing Dynamics: Deep Neural Networks versus Glassy Systems
• Community detection in networks with unequal groups
• The condensation transition in random hypergraph 2-coloring
• Typology of phase transitions in Bayesian inference problems
• Minimal contagious sets in random regular graphs
• Information-theoretic thresholds for community detection in sparse networks
• Statistical Mechanics of the Minimum Dominating Set Problem
• Potts Glass on Random Graphs
• Quiet Planting in the Locked Constraint Satisfaction Problems
• Relaxation dynamics in the energy landscape of glass-forming liquids
• Random subcubes as a toy model for constraint satisfaction problems
• Physics and Complexity
• Information-theoretic thresholds for community detection in sparse networks
• A Lattice Model for Colloidal Gels and Glasses
• Exhaustive enumeration unveils clustering and freezing in random 3-SAT
• The condensation phase transition in random graph coloring
• Threshold Saturation in Spatially Coupled Constraint Satisfaction Problems
• Region graph partition function expansion and approximate free energy landscapes: Theory and some numerical results
• Charting the replica symmetric phase
• Statistical Mechanics of maximal independent sets
• The hard-core model on random graphs revisited
• The Jamming point street-lamp in the world of granular media
• Machine-learning-assisted Monte Carlo fails at sampling computationally hard problems
• A Spectral Approach to Analyzing Belief Propagation for 3-Coloring
• Decentralized Constraint Satisfaction
• Approximating the XY model on a random graph with a $q$-state clock model
• Dreaming neural networks: rigorous results
• Limits and performances of algorithms based on simulated annealing in solving sparse hard inference problems
• A solvable model of quantum random optimization problems
• Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
• A rigorous analysis of the cavity equations for the minimum spanning tree
• Learning may need only a few bits of synaptic precision
• Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective
• Walksat stalls well below the satisfiability threshold
• The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property
• Generating dense packings of hard spheres by soft interaction design
• Faster than Classical Quantum Algorithm for dense Formulas of Exact Satisfiability and Occupation Problems
• Biased landscapes for random Constraint Satisfaction Problems
• Maximum independent sets on random regular graphs
• Harnessing the Bethe free energy
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Irreversible Monte Carlo algorithms for hard disk glasses: from event-chain to collective swaps
• Phase transitions in the $q$-coloring of random hypergraphs
• 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
• Broadcasting on Random Directed Acyclic Graphs
• Computational hardness of spin-glass problems with tile-planted solutions
• Belief propagation for graph partitioning
• The nature of the different zero-temperature phases in discrete two-dimensional spin glasses: Entropy, universality, chaos and cascades in the renormalization group flow
• Limits of discrete distributions and Gibbs measures on random graphs
• Characterizing and Improving Generalized Belief Propagation Algorithms on the 2D Edwards-Anderson Model
• Communities of solutions in single solution clusters of a random K-Satisfiability formula
• Impact of jamming criticality on low-temperature anomalies in structural glasses
• Solving Boolean satisfiability problems with resistive content addressable memories
• 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
• Entropic Effects in the Very Low Temperature Regime of Diluted Ising Spin Glasses with Discrete Couplings
• Statistical physics of hard combinatorial optimization: The vertex cover problem
• Quantum memory at nonzero temperature in a thermodynamically trivial system
• Reconstruction of symmetric Potts Models
• A positive temperature phase transition in random hypergraph 2-coloring
• Numerical Solution-Space Analysis of Satisfiability Problems
• Quantum Jamming: Critical Properties of a Quantum Mechanical Perceptron
• Tuning and jamming reduced to their minima
• Phase Transitions of Traveling Salesperson Problems solved with Linear Programming and Cutting Planes
• Statistical mechanical analysis of sparse linear regression as a variable selection problem
• The random 2-SAT partition function
• On belief propagation guided decimation for random k-SAT
• Spin systems on Bethe lattices
• Mean field theory of jamming of nonspherical particles
• Decoding from Pooled Data: Sharp Information-Theoretic Bounds
• Revisiting the Challenges of MaxClique
• Solution space structure of random constraint satisfaction problems with growing domains
• Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems
• The statistical mechanics of random set packing and a generalization of the Karp-Sipser algorithm
• Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem
• The set of solutions of random XORSAT formulae
• Spectral estimation of the percolation transition in clustered networks
• A theory of non-equilibrium local search on random satisfaction problems
• Zero temperature solutions of the Edwards-Anderson model in random Husimi Lattices
• Planting colourings silently
• Determining the Solution Space of Vertex-Cover by Interactions and Backbones
• Statistical physics approach to graphical games: local and global interactions
• Cycle-tree guided attack of random K-core: Spin glass model and efficient message-passing algorithm
• Phase Transitions of the Typical Algorithmic Complexity of the Random Satisfiability Problem Studied with Linear Programming
• Minimizing Unsatisfaction in Colourful Neighbourhoods
• Entropy Inflection and Invisible Low-Energy States: Defensive Alliance Example
• Partition Function Expansion on Region-Graphs and Message-Passing Equations
• On the Atypical Solutions of the Symmetric Binary Perceptron
• Glassy Behavior and Jamming of a Random Walk Process for Sequentially Satisfying a Constraint Satisfaction Formula
• Complex Replica Zeros of $\pm J$ Ising Spin Glass at Zero Temperature
• Ground-state configuration space heterogeneity of random finite-connectivity spin glasses and random constraint satisfaction problems
• Optimization on Sparse Random Hypergraphs and Spin Glasses
• Random Constraint Satisfaction Problems
• Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries
• Fluctuations in the random-link matching problem
• Enhancing the efficiency of quantum annealing via reinforcement: A path-integral Monte Carlo simulation of the quantum reinforcement algorithm
• Learning by random walks in the weight space of the Ising perceptron
• Reconstruction Threshold for the Hardcore Model
• Convergence of multivariate belief propagation, with applications to cuckoo hashing and load balancing
• Optimal control of a quantum sensor: A fast algorithm based on an analytic solution
• Approximating random quantum optimization problems
• Minimal Dominating Set problem studied by simulated annealing and cavity method: Analytics and population dynamics
• PDP: A General Neural Framework for Learning Constraint Satisfaction Solvers
• Next nearest neighbour Ising models on random graphs
• Spin glass phase transitions in the random feedback vertex set problem
• 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
• Gibbs Measures and Phase Transitions on Sparse Random Graphs
• An improved Belief Propagation algorithm finds many Bethe states in the random field Ising model on random graphs
• The asymptotics of the clustering transition for random constraint satisfaction problems
• Circular Coloring of Random Graphs: Statistical Physics Investigation
• Polynomial Time Quantum Gibbs Sampling for Fermi-Hubbard Model at any Temperature
• Maximally flexible solutions of a random $K$-satisfiability formula
• Clustering of solutions in hard satisfiability problems
• Partial local entropy and anisotropy in deep weight spaces
• Biased measures for random Constraint Satisfaction Problems: larger interaction range and asymptotic expansion
• Random-link matching problems on random regular graphs
• Entropic barriers as a reason for hardness in both classical and quantum algorithms
• Optimization of the dynamic transition in the continuous coloring problem
• Sparse approximation problem: how rapid simulated annealing succeeds and fails
• MCMC sampling colourings and independent sets of G(n,d/n) near the uniqueness threshold
• Low-temperature excitations within the Bethe approximation
• Counting solutions from finite samplings
• The decimation process in random k-SAT
• Adversarial Satisfiability Problem
• Relationship between clustering and algorithmic phase transitions in the random k-XORSAT model and its NP-complete extensions
• Statistical Mechanics of the Quantum K-Satisfiability problem
• Introduction to Phase Transitions in Random Optimization Problems
• Broadcasting on Two-Dimensional Regular Grids
• Research on Solution Space of Bipartite Graph Vertex-Cover by Maximum Matchings
• Realizing interdependent couplings as thermal or higher-order interactions
• Poisson-Dirichlet asymptotics in condensing particle systems
• Understanding the computational difficulty of a binary-weight perceptron and the advantage of input sparseness
• Susceptibility Propagation for Constraint Satisfaction Problems
• A residual-based message passing algorithm for constraint satisfaction problems
• Revisiting the cavity-method threshold for random 3-SAT
• The effect of quantum fluctuations on the coloring of random graphs
• Composite CDMA - A statistical mechanics analysis
• The solution space structure of planted constraint satisfaction problems with growing domains
• High-density hard-core model on triangular and hexagonal lattices
• Solution space heterogeneity of the random K-satisfiability problem: Theory and simulations
• Criticality and Heterogeneity in the Solution Space of Random Constraint Satisfaction Problems
• What makes a phase transition? Analysis of the random satisfiability problem
• Bethe free-energy approximations for disordered quantum systems
• The number of solutions for random regular NAE-SAT
• Critical properties of disordered XY model on sparse random graphs
• Cavity approach to sphere packing in Hamming space
• Self-Sustained Clusters as Drivers of Computational Hardness in $p$-spin Models
• A simple one dimensional glassy Kac model
• A model with Darwinian dynamics on a rugged landscape
• Generalized Approximate Survey Propagation for High-Dimensional Estimation
• Organization mechanism and counting algorithm on Vertex-Cover solutions
• Reconstruction/Non-reconstruction Thresholds for Colourings of General Galton-Watson Trees
• Breaking of 1RSB in random MAX-NAE-SAT
• Statistical mechanics of classical and quantum computational complexity
• Slow Spin Dynamics and Self-Sustained Clusters in Sparsely Connected Systems
• Order-to-chaos transition in the hardness of random Boolean satisfiability problems
• The planted XY model: thermodynamics and inference
• Statistical Physics of Medical Diagnostics: Study of a Probabilistic Model
• Entropic long range order in a 3D spin glass model
• The replica symmetric solution for Potts models on d-regular graphs
• Decimation flows in constraint satisfaction problems
• K-core attack, equilibrium K-core, and kinetically constrained spin system
• Extending the applicability of Thermal Dynamics to Evolutionary Biology
• Boolean constraint satisfaction problems for reaction networks
• Cluster structure of optimal solutions in bipartitioning of small worlds
• Frozen $1$-RSB structure of the symmetric Ising perceptron
• Perturbed Message Passing for Constraint Satisfaction Problems
• Algebraic dynamical systems from LDPC codes satisfy a strong negation of the weak Pinsker property
• Statistical Mechanical Formulation and Simulation of Prime Factorization of Integers
• Witness of unsatisfiability for a random 3-satisfiability formula
• Academic Meeting Scheduling Using an Antiferromagnetic Potts Model
• Complex Cooperative Behaviour in Range-free Frustrated Many-body Systems
• Gibbs state sampling via cluster expansions
• Biased thermodynamics can explain the behaviour of smart optimization algorithms that work above the dynamical threshold
• Computing a Knot Invariant as a Constraint Satisfaction Problem
• Satisfiability transition in asymmetric neural networks
• Approaching the ground states of the random maximum two-satisfiability problem by a greedy single-spin flipping process
• Phase transition in the bipartite z-matching
• High-density hard-core model on ${\mathbb{Z}}^2$ and norm equations in ring $\mathbb{Z}[\sqrt[6]{-1}]$
• Finite-size scaling in random $K$-satisfiability problems
• Broadcasting on Bounded Degree DAGs
• Bose-Einstein Condensation in Satisfiability Problems
• Constructing Concrete Hard Instances of the Maximum Independent Set Problem
• Bipartitioning of directed and mixed random graphs
• Hearings and mishearings: decrypting the spoken word
• Uniformly Random Colourings of Sparse Graphs
• Algorithmic thresholds in combinatorial optimization depend on the time scaling
• Broadcasting colourings on trees. A combinatorial view
• Complete Realization of Energy Landscape and Non-equilibrium Trapping Dynamics in Spin Glass and Optimization Problem
• Dynamical Cavity Method for Hypergraphs and its Application to Quenches in the k-XOR-SAT Problem
• Identifying all irreducible conserved metabolite pools in genome-scale metabolic networks: a general method and the case of Escherichia coli
• Statistical mechanical models of integer factorization problem
• Interacting Copies of Random Constraint Satisfaction Problems
• 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)
• An alternate view of complexity in k-SAT problems
• Planted matching problems on random hypergraphs
• Rényi complexity in mean-field disordered systems
• Probabilistic Multilayer Networks
• Deterministic counting of graph colourings using sequences of subgraphs
• 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