Bicoloring Random Hypergraphs

Abstract

We study the problem of bicoloring 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 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 bicoloring instances in the so called HARD-SAT phase.

14 pages, 10 figures

References in corpus (11)

• The Bethe lattice spin glass revisited
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• The Thermodynamic Limit in Mean Field Spin Glass Models
• Statistical mechanics of the random K-SAT model
• On the nature of the low-temperature phase in discontinuous mean-field spin glasses
• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• A variational description of the ground state structure in random satisfiability problems
• Simplest random K-satisfiability problem
• Random Graph Coloring - a Statistical Physics Approach
• Higher-order QED corrections to single-W production in electron-positron collisions
• Complexity transitions in global algorithms for sparse linear systems over finite fields

Cited by in corpus (12)

• On the freezing of variables in random constraint satisfaction problems
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• The backtracking survey propagation algorithm for solving random K-SAT problems
• Constraint satisfaction problems with isolated solutions are hard
• Grassmann Integral Representation for Spanning Hyperforests
• Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective
• 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
• Satisfiability Thresholds for Regular Occupation Problems
• The threshold for SDP-refutation of random regular NAE-3SAT
• Interacting Copies of Random Constraint Satisfaction Problems