Finding the right path: statistical mechanics of connected solutions in constraint satisfaction problems

2025/05/27 by Damien Barbier, Barbier, Damien · 1 citation
Computer Science · #Constraint Satisfaction and Optimization #Disordered Systems and Neural Networks (cond-mat.dis-nn) #FOS: Physical sciences #Statistical Mechanics (cond-mat.stat-mech)

paper · pdf · doi:10.48550/arxiv.2505.20954

openalex publication_date 2025/05/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We define and study a statistical mechanics ensemble that characterizes connected solutions in constraint satisfaction problems (CSPs). Built around a well-known local entropy bias, it allows us to better identify hardness transitions in problems where the energy landscape is dominated by isolated solutions. We apply this new device to the symmetric binary perceptron model (SBP), and study how its manifold of connected solutions behaves. We choose this particular problem because, while its typical solutions are isolated, it can be solved using local algorithms for a certain range of constraint density α and threshold κ. With this new ensemble, we unveil the presence of a cluster composed of delocalized connected solutions. In particular, we demonstrate its stability until a critical threshold κ^{\rm no-mem}_{\rm loc. stab.} (dependent on α). This transition appears as paths of solutions shatter, a phenomenon that more conventional statistical mechanics approaches fail to grasp. Finally, we compared our predictions to simulations. For this, we used a modified Monte-Carlo algorithm, designed specifically to target these delocalized solutions. We obtained, as predicted, that the algorithm finds solutions until κ≈κ^{\rm no-mem}_{\rm loc. stab.}.

Citations

• Capacity threshold for the Ising perceptron
• The star-shaped space of solutions of the spherical negative perceptron
• Transition paths in Potts-like energy landscapes: general properties and application to protein sequence models
• Accelerated Evolution by Diversity-Generating Retroelements
• Algorithms and Barriers in the Symmetric Binary Perceptron Model
• On-Line Balancing of Random Inputs
• The algorithmic hardness threshold for continuous random energy models
• Limits of local algorithms over sparse random graphs
• On the Solution-Space Geometry of Random Constraint Satisfaction Problems
• Probability distribution of molecular evolutionary trees: A new method of phylogenetic inference

Cited by

• Dynamical Learning in Deep Asymmetric Recurrent Neural Networks

Related

• Widely distributed clusters of the constraint satisfaction problem model d-k-CSP
• Interacting Copies of Random Constraint Satisfaction Problems
• Beyond-mean-field fluctuations for the solution of constraint satisfaction problems
• Conditional Random Fields, Planted Constraint Satisfaction, and Entropy\n Concentration
• Certifying solution geometry in random CSPs: counts, clusters and balance