A Landscape Analysis of Constraint Satisfaction Problems

Abstract

We discuss an analysis of Constraint Satisfaction problems, such as Sphere Packing, K-SAT and Graph Coloring, in terms of an effective energy landscape. Several intriguing geometrical properties of the solution space become in this light familiar in terms of the well-studied ones of rugged (glassy) energy landscapes. A `benchmark' algorithm naturally suggested by this construction finds solutions in polynomial time up to a point beyond the `clustering' and in some cases even the `thermodynamic' transitions. This point has a simple geometric meaning and can be in principle determined with standard Statistical Mechanical methods, thus pushing the analytic bound up to which problems are guaranteed to be easy. We illustrate this for the graph three and four-coloring problem. For Packing problems the present discussion allows to better characterize the `J-point', proposed as a systematic definition of Random Close Packing, and to place it in the context of other theories of glasses.

17 pages, 69 citations, 12 figures

References in corpus (41)

• Jamming at Zero Temperature and Zero Applied Stress: the Epitome of Disorder
• Is Random Close Packing of Spheres Well Defined?
• Analytical Solution of the Off-Equilibrium Dynamics of a Long Range Spin-Glass Model
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• On the Out of Equilibrium Relaxation of the Sherrington - Kirkpatrick model
• The structural glass transition and the entropy of the metastable states
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Packing of Compressible Granular Materials
• Packing Hyperspheres in High-Dimensional Euclidean Spaces
• Geometric origin of excess low-frequency vibrational modes in amorphous solids
• On the Rigidity of Amorphous Solids
• Phase Transitions in the Coloring of Random Graphs
• Rigorous Inequalities between Length and Time Scales in Glassy Systems
• Statistical mechanics of the random K-SAT model
• Coloring random graphs
• Phase space geometry and slow dynamics
• Isostatic phase transition and instability in stiff granular materials
• On the nature of the low-temperature phase in discontinuous mean-field spin glasses
• Aging as dynamics in configuration space
• A variational description of the ground state structure in random satisfiability problems
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• The ideal glass transition of Hard Spheres
• On the dynamics of the glass transition on Bethe lattices
• Effective potential in glassy systems: theory and simulations
• On the cooling-schedule dependence of the dynamics of mean-field glasses
• Temperature evolution and bifurcations of metastable states in mean-field spin glasses, with connections with structural glasses
• Landscape of solutions in constraint satisfaction problems
• Floppy modes and the free energy: Rigidity and connectivity percolation on Bethe Lattices
• Behavior of heuristics and state space structure near SAT/UNSAT transition
• Amorphous packings of hard spheres in large space dimension
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
• Comment on "Jamming at zero temperature and zero applied stress: The epitome of disorder"
• From Large Scale Rearrangements to Mode Coupling Phenomenology
• Random Graph Coloring - a Statistical Physics Approach
• Numerical study of metastable states in Ising spin glasses
• Marginal States in Mean Field Glasses
• Reply to "Comment on `Jamming at zero temperature and zero applied stress: The epitome of disorder' "
• Free energy landscapes, dynamics and the edge of chaos in mean-field models of spin glasses
• Quenched Computation of the Complexity of the Sherrington-Kirkpatrick Model
• Off-equilibrium confined dynamics in a glassy system with level-crossing states
• Comment to "Packing Hyperspheres in High-Dimensional Euclidean Space"

Cited by in corpus (98)

• Mean field theory of hard sphere glasses and jamming
• Fractal free energy landscapes in structural glasses
• Statistical physics of inference: Thresholds and algorithms
• Probing the equilibrium dynamics of colloidal hard spheres above the mode-coupling glass transition
• Phase Transitions in the Coloring of Random Graphs
• Unified study of glass and jamming rheology in soft particle systems
• Jamming transitions in amorphous packings of frictionless spheres occur over a continuous range of volume fractions
• The glass transition of dense fluids of hard and compressible spheres
• Jamming versus Glass Transitions
• Universal microstructure and mechanical stability of jammed packings
• Mean-field theory of random close packings of axisymmetric particles
• Fundamental challenges in packing problems: from spherical to non-spherical particles
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• A theory of amorphous packings of binary mixtures of hard spheres
• Compressing nearly hard sphere fluids increases glass fragility
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Critical scaling and heterogeneous superdiffusion across the jamming/rigidity transition of a granular glass
• The jamming transition as a paradigm to understand the loss landscape of deep neural networks
• Glass transition and random close packing above three dimensions
• Memory of jamming - multiscale models for soft and granular matter
• A first-order phase transition at the random close packing of hard spheres
• Microscopic theory of the jamming transition of harmonic spheres
• Experimental evidences of the Gardner phase in a granular glass
• Glassiness, Rigidity and Jamming of Frictionless Soft Core Disks
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• Entropy of jammed matter
• An event-based architecture for solving constraint satisfaction problems
• Dynamic light scattering measurements in the activated regime of dense colloidal hard spheres
• A microscopic mean-field theory of the jamming transition
• Locked constraint satisfaction problems
• Following Gibbs States Adiabatically - The Energy Landscape of Mean Field Glassy Systems
• Double Trouble in Double Descent : Bias and Variance(s) in the Lazy Regime
• Networking - A Statistical Physics Perspective
• Anomalous structural evolution of soft particles: Equibrium liquid state theory
• Estimating random close packing in polydisperse and bidisperse hard spheres via an equilibrium model of crowding
• Jamming II: Edwards' statistical mechanics of random packings of hard spheres
• Free-then-freeze: transient learning degrees of freedom for introducing function in materials
• Random subcubes as a toy model for constraint satisfaction problems
• Search for Hyperuniformity in Mechanically Stable Packings of Frictionless Disks Above Jamming
• A Lattice Model for Colloidal Gels and Glasses
• Exhaustive enumeration unveils clustering and freezing in random 3-SAT
• Long-Range Anomalous Decay of the Correlation in Jammed Packings
• The Inherent Structure Landscape Connection Between Liquids, Granular materials and the Jamming Phase Diagram
• Scaling of the glassy dynamics of soft repulsive particles: a mode-coupling approach
• Fragility and hysteretic creep in frictional granular jamming
• Performance of simulated annealing in p-spin glasses
• The Jamming point street-lamp in the world of granular media
• Critical scalings and jamming in thermal colloidal systems
• Machine-learning-assisted Monte Carlo fails at sampling computationally hard problems
• Triple descent and the two kinds of overfitting: Where & why do they appear?
• Disordered Solids Without Well-Defined Transverse Phonons: The Nature of Hard Sphere Glasses
• Free volume distribution of nearly jammed hard sphere packings
• On weak ergodicity breaking in mean-field spin glasses
• Finite size analysis of zero-temperature jamming transition under applied shear stress
• Quasi-equilibrium in glassy dynamics: an algebraic view
• The large deviations of the whitening process in random constraint satisfaction problems
• Athermal Jamming vs Thermalized Glassiness in Sheared Frictionless Particles
• Critical scaling of jammed system after quench of temperature
• Finite size effects in the microscopic critical properties of jammed configurations: A comprehensive study of the effects of different types of disorder
• On the solution of a `solvable' model of an ideal glass of hard spheres displaying a jamming transition
• Communities of solutions in single solution clusters of a random K-Satisfiability formula
• Quasi-equilibrium in glassy dynamics: a liquid theory approach
• Numerical Solution-Space Analysis of Satisfiability Problems
• Statistical theory of correlations in random packings of hard particles
• A small subset of normal modes mimics the properties of dynamical heterogeneity in a model supercooled liquid
• Higher order corrections to the effective potential close to the jamming transition in the perceptron model
• Arrangement of nearby minima and saddles in the mixed spherical energy landscapes
• Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems
• Zero temperature solutions of the Edwards-Anderson model in random Husimi Lattices
• Ergodicity breaking transition in a glassy soft sphere system at small but non-zero temperatures
• Entropy Inflection and Invisible Low-Energy States: Defensive Alliance Example
• Glassy Behavior and Jamming of a Random Walk Process for Sequentially Satisfying a Constraint Satisfaction Formula
• Learning by random walks in the weight space of the Ising perceptron
• Toward a Theory of Phase Transitions in Quantum Control Landscapes
• Combined local search strategy for learning in networks of binary synapses
• Constraint optimization and landscapes
• On the interplay between data structure and loss function in classification problems
• Can the jamming transition be described using equilibrium statistical mechanics?
• When you can't count, sample! Computable entropies beyond equilibrium from basin volumes
• Optimization of the dynamic transition in the continuous coloring problem
• Active Jamming at Criticality
• When is the average number of saddle points typical?
• Theory of simple glasses
• Entropic barriers as a reason for hardness in both classical and quantum algorithms
• Relationship between clustering and algorithmic phase transitions in the random k-XORSAT model and its NP-complete extensions
• Introduction to Phase Transitions in Random Optimization Problems
• Visualizing Free Energy Landscapes for Four Hard Disks
• Perspective: A Phase Diagram for Deep Learning unifying Jamming, Feature Learning and Lazy Training
• Packing hard spheres with short-range attraction in infinite dimension: Phase structure and algorithmic implications
• Criticality and Heterogeneity in the Solution Space of Random Constraint Satisfaction Problems
• Far-from-equilibrium complex landscapes
• Topological Phase Transitions in a Constrained Two-Qubit Quantum Control Landscape
• Biased thermodynamics can explain the behaviour of smart optimization algorithms that work above the dynamical threshold
• Fluctuation Distributions of Energy Minima in Complex Landscapes
• Finite-size scaling in random $K$-satisfiability problems
• Following the evolution of metastable glassy states under external perturbations: compression and shear-strain
• Glass and jamming transition of simple liquids: static and dynamic theory