Bicolouring random hypergraphs

2003/06/30 by Tommaso Castellani, Vincenzo Napolano, Federico Ricci-Tersenghi +2 · 2 citations
Computer Science · Physics and Astronomy · #Constraint Satisfaction and Optimization #Data Management and Algorithms #Data Mining Algorithms and Applications #cond-mat.dis-nn #cond-mat.stat-mech

paper · pdf · doi:10.1088/0305-4470/36/43/026

published as J. Phys. A 36, 11037 (2003) · 14 pages, 10 figures

arxiv created 2003/07/24 · openalex publication_date 2003/10/15 · arxiv updated 2009/11/30 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/30

Abstract

We study the problem of bicolouring random hypergraphs, both numerically and analytically. We apply the zero-temperature cavity method to find analytical results for the phase transitions (dynamic and static) in the one-step replica symmetry breaking (1RSB) approximation. These points appear to be in agreement with the results of the numerical algorithm. In the second part, we implement and test the survey propagation algorithm for specific bicolouring instances in the so-called HARD-SAT phase.

Citations

• The Thermodynamic Limit in Mean Field Spin Glass Models
• Complexity transitions in global algorithms for sparse linear systems over finite fields

Cited by

• Grassmann integral representation for spanning hyperforests
• On the Freezing of Variables in Random Constraint Satisfaction Problems