Interacting Copies of Random Constraint Satisfaction Problems

Abstract

We study a system of $y=2$ coupled copies of a well-known constraint satisfaction problem (random hypergraph bicoloring) to examine how the ferromagnetic coupling between the copies affects the properties of the solution space. We solve the replicated model by applying the cavity method to the supervariables taking $2^y$ values. Our results show that a coupling of strength $\gamma$ between the copies decreases the clustering threshold ${\alpha }_d(\gamma )$, at which typical solutions shatters into disconnected components, therefore preventing numerical methods such as Monte Carlo Markov Chains from reaching equilibrium in polynomial time. This result needs to be reconciled with the observation that, in models with coupled copies, denser regions of the solution space should be more accessible. Additionally, we observe a change in the nature of the clustering phase transition, from discontinuous to continuous, in a wide $\gamma$ range. We investigate how the coupling affects the behavior of the Belief Propagation (BP) algorithm on finite-size instances and find that BP convergence is significantly impacted by the continuous transition. These results highlight the importance of better understanding algorithmic performance at the clustering transition, and call for a further exploration into the optimal use of re-weighting strategies designed to enhance algorithmic performances.

19 pages, 8 figures

References in corpus (27)

• The Bethe lattice spin glass revisited
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Rigorous Inequalities between Length and Time Scales in Glassy Systems
• Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
• A variational description of the ground state structure in random satisfiability problems
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Quantum fluctuations can promote or inhibit glass formation
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms
• Efficiency of quantum versus classical annealing in non-convex learning problems
• Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems
• The backtracking survey propagation algorithm for solving random K-SAT problems
• Typology of phase transitions in Bayesian inference problems
• Disordered Systems Insights on Computational Hardness
• Limits and performances of algorithms based on simulated annealing in solving sparse hard inference problems
• Walksat stalls well below the satisfiability threshold
• Generating dense packings of hard spheres by soft interaction design
• 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
• Bicoloring Random Hypergraphs
• Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs
• The Copycat Perceptron: Smashing Barriers Through Collective Learning
• Maximally flexible solutions of a random $K$-satisfiability formula
• The Ising spin glass on random graphs at zero temperature: not all spins are glassy in the glassy phase
• Biased measures for random Constraint Satisfaction Problems: larger interaction range and asymptotic expansion