Interacting Copies of Random Constraint Satisfaction Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914340384276480 |
|---|---|
| author | Angelini, Maria Chiara Budzynski, Louise Ricci-Tersenghi, Federico |
| author_facet | Angelini, Maria Chiara Budzynski, Louise Ricci-Tersenghi, Federico |
| contents | 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 $γ$ between the copies decreases the clustering threshold $α_d(γ)$, 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 $γ$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_15158 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Interacting Copies of Random Constraint Satisfaction Problems Angelini, Maria Chiara Budzynski, Louise Ricci-Tersenghi, Federico Disordered Systems and Neural Networks Statistical Mechanics 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 $γ$ between the copies decreases the clustering threshold $α_d(γ)$, 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 $γ$ 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. |
| title | Interacting Copies of Random Constraint Satisfaction Problems |
| topic | Disordered Systems and Neural Networks Statistical Mechanics |
| url | https://arxiv.org/abs/2504.15158 |