Entropy landscape and non-Gibbs solutions in constraint satisfaction problems

Abstract

We study the entropy landscape of solutions for the bicoloring problem in random graphs, a representative difficult constraint satisfaction problem. Our goal is to classify which type of clusters of solutions are addressed by different algorithms. In the first part of the study we use the cavity method to obtain the number of clusters with a given internal entropy and determine the phase diagram of the problem, e.g. dynamical, rigidity and SAT-UNSAT transitions. In the second part of the paper we analyze different algorithms and locate their behavior in the entropy landscape of the problem. For instance we show that a smoothed version of a decimation strategy based on Belief Propagation is able to find solutions belonging to sub-dominant clusters even beyond the so called rigidity transition where the thermodynamically relevant clusters become frozen. These non-equilibrium solutions belong to the most probable unfrozen clusters.

38 pages, 10 figures

References in corpus (17)

• The Bethe lattice spin glass revisited
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Phase Transitions in the Coloring of Random Graphs
• Statistical mechanics of systems with heterogeneous agents: Minority Games
• Statistical mechanics of the random K-SAT model
• Coloring random graphs
• On the nature of the low-temperature phase in discontinuous mean-field spin glasses
• A Landscape Analysis of Constraint Satisfaction Problems
• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• Learning by message-passing in networks of discrete synapses
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• Efficient supervised learning in networks with binary synapses
• On the freezing of variables in random constraint satisfaction problems
• Landscape of solutions in constraint satisfaction problems
• Bicoloring Random Hypergraphs
• Statistical mechanics of combinatorial auctions

Cited by in corpus (39)

• Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems
• Locked constraint satisfaction problems
• Constraint satisfaction problems with isolated solutions are hard
• Following Gibbs States Adiabatically - The Energy Landscape of Mean Field Glassy Systems
• The backtracking survey propagation algorithm for solving random K-SAT problems
• Catching the k-NAESAT Threshold
• The condensation transition in random hypergraph 2-coloring
• Exhaustive enumeration unveils clustering and freezing in random 3-SAT
• Entropy landscape of solutions in the binary perceptron problem
• Statistical Mechanics of maximal independent sets
• Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective
• 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
• Communities of solutions in single solution clusters of a random K-Satisfiability formula
• A positive temperature phase transition in random hypergraph 2-coloring
• Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs
• Clustering of neural codewords revealed by a first-order phase transition
• Efficient data compression from statistical physics of codes over finite fields
• 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
• The asymptotics of the clustering transition for random constraint satisfaction problems
• Maximally flexible solutions of a random $K$-satisfiability formula
• Counting and Hardness-of-Finding Fixed Points in Cellular Automata on Random Graphs
• Code optimization, frozen glassy phase and improved decoding algorithms for low-density parity-check codes
• Coordination problems on networks revisited: statics and dynamics
• The network source location problem: ground state energy, entropy and effects of freezing
• Satisfiability Thresholds for Regular Occupation Problems
• Biased thermodynamics can explain the behaviour of smart optimization algorithms that work above the dynamical threshold
• The closest vector problem and the zero-temperature p-spin landscape for lossy compression
• Interacting Copies of Random Constraint Satisfaction Problems
• An alternate view of complexity in k-SAT problems
• Rigid colourings of hypergraphs and contiguity
• The threshold for SDP-refutation of random regular NAE-3SAT