Clustering of solutions in the random satisfiability problem

Abstract

Using elementary rigorous methods we prove the existence of a clustered phase in the random $K$-SAT problem, for $K\ge 8$. In this phase the solutions are grouped into clusters which are far away from each other. The results are in agreement with previous predictions of the cavity method and give a rigorous confirmation to one of its main building blocks. It can be generalized to other systems of both physical and computational interest.

4 pages, 1 figure

References in corpus (11)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• 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
• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• The glassy phase of Gallager codes
• Polynomial iterative algorithms for coloring and analyzing random graphs
• Facilitated spin models on Bethe lattice: bootstrap percolation, mode-coupling transition and glassy dynamics
• A frozen glass phase in the multi-index matching problem
• Threshold values of Random K-SAT from the cavity method

Cited by in corpus (80)

• Critical phenomena in complex networks
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Phase Transitions in the Coloring of Random Graphs
• Algorithmic barriers from phase transitions
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• On the freezing of variables in random constraint satisfaction problems
• Landscape of solutions in constraint satisfaction problems
• Circumspect descent prevails in solving random constraint satisfaction problems
• Behavior of heuristics and state space structure near SAT/UNSAT transition
• Survey-propagation decimation through distributed local computations
• Lossy data compression with random gates
• Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems
• Pairs of SAT Assignment in Random Boolean Formulae
• Clustering of non-ergodic eigenstates in quantum spin glasses
• Geometrical organization of solutions to random linear Boolean equations
• Reducing Frustration in Spin Systems: Social Balance as an XOR-SAT problem
• Random subcubes as a toy model for constraint satisfaction problems
• Exhaustive enumeration unveils clustering and freezing in random 3-SAT
• Disordered Systems Insights on Computational Hardness
• TASI lectures on complex structures
• Relaxed Survey Propagation for The Weighted Maximum Satisfiability Problem
• Decentralized Constraint Satisfaction
• A Quantum Lovasz Local Lemma
• The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property
• 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
• Mapping between Spin-Glass Three-Dimensional (3D) Ising Model and Boolean Satisfiability Problem
• Energy landscapes of combinatorial optimization in Ising machines
• Clustering of solutions in the symmetric binary perceptron
• Communities of solutions in single solution clusters of a random K-Satisfiability formula
• Continuous- and discrete-time Glauber dynamics. First- and second-order phase transitions in mean-field Potts models
• Optimizing Mean Field Spin Glasses with External Field
• $T\to 0$ mean-field population dynamics approach for the random 3-satisfiability problem
• Numerical Solution-Space Analysis of Satisfiability Problems
• A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz
• Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs
• The Overlap Gap Property in Principal Submatrix Recovery
• Solution space structure of random constraint satisfaction problems with growing domains
• Determining the Solution Space of Vertex-Cover by Interactions and Backbones
• Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems
• Ground-state configuration space heterogeneity of random finite-connectivity spin glasses and random constraint satisfaction problems
• Clustering in Hilbert space of a quantum optimization problem
• A New Look at Survey Propagation and its Generalizations
• Satisfiability, sequence niches, and molecular codes in cellular signaling
• Tightness of LP via Max-product Belief Propagation
• Enhancing the efficiency of quantum annealing via reinforcement: A path-integral Monte Carlo simulation of the quantum reinforcement algorithm
• Reconstruction and Clustering in Random Constraint Satisfaction Problems
• Clustering of solutions in hard satisfiability problems
• Maximally flexible solutions of a random $K$-satisfiability formula
• Entropic barriers as a reason for hardness in both classical and quantum algorithms
• Generating Hard Ising Instances With Planted Solutions Using Post-Quantum Cryptographic Protocols
• Phase transition for Local Search on planted SAT
• Susceptibility Propagation for Constraint Satisfaction Problems
• Gap Amplification for Reconfiguration Problems
• Combinatorial NLTS From the Overlap Gap Property
• Group testing and local search: is there a computational-statistical gap?
• Barriers and local minima in energy landscapes of stochastic local search
• On the Max-Cut of Sparse Random Graphs
• The solution space structure of planted constraint satisfaction problems with growing domains
• Tailoring the overlap distribution in driven mean-field spin models
• The Connectivity of Boolean Satisfiability: No-Constants and Quantified Variants
• Organization mechanism and counting algorithm on Vertex-Cover solutions
• Spanning Trees in Random Satisfiability Problems
• The Overlap Gap Property limits limit swapping in the QAOA
• Order-to-chaos transition in the hardness of random Boolean satisfiability problems
• Inside the clustering window for random linear equations
• Inside the clustering threshold for random linear equations
• Constructing Concrete Hard Instances of the Maximum Independent Set Problem
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm
• Algorithmic thresholds in combinatorial optimization depend on the time scaling
• Satisfying assignments of Random Boolean CSP: Clusters and Overlaps
• q-Overlaps in the Random Exact Cover Problem
• Pruning Processes and a New Characterization of Convex Geometries
• On the Satisfiability Threshold and Clustering of Solutions of Random 3-SAT Formulas
• On the random satisfiable process
• The Connectivity of Boolean Satisfiability: Dichotomies for Formulas and Circuits
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)
• On the diameter of the set of satisfying assignments in random satisfiable k-CNF formulas
• Fluctuations induce transitions in frustrated sparse networks