Bicoloring Random Hypergraphs

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.

• Publication year

  2003

• Venue

  arXiv: Disordered Systems and Neural Networks

• Publication date

  2003-06-13

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1088/0305-4470/36/43/026arXiv cond-mat/0306369
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On the nature of the low-temperature phase in discontinuous mean-field spin glasses

  2003cited by this paper
• Two Solutions to Diluted p-Spin Models and XORSAT Problems

  2003cited by this paper
• Replica Bounds for Optimization Problems and Diluted Spin Systems

  2002cited by this paper
• The Cavity Method at Zero Temperature

  2002cited by this paper
• Random graph coloring: statistical physics approach.

  2002cited by this paper
• Analytic and Algorithmic Solution of Random Satisfiability Problems

  2002cited by this paper
• The Thermodynamic Limit in Mean Field Spin Glass Models

  2002cited by this paper
• Rigorous decimation-based construction of ground pure states for spin-glass models on random lattices.

  2002cited by this paper
• Random K-satisfiability problem: from an analytic solution to an efficient algorithm.

  2002cited by this paper
• Complexity transitions in global algorithms for sparse linear systems over finite fields

  2002cited by this paper
• Factor graphs and the sum-product algorithm

  2001cited by this paper
• THE EUROPEAN PHYSICAL JOURNAL B c○ EDP Sciences

  2000cited by this paper
• Higher-order QED corrections to single-W production in electron–positron collisions

  2000cited by this paper
• Simplest random K-satisfiability problem

  2000cited by this paper
• The Bethe lattice spin glass revisited

  2000cited by this paper
• Sharp thresholds of graph properties, and the -sat problem

  1999cited by this paper
• Determination of semi-muonic branching ratios and fragmentation functions of heavy quarks ine+e− annihilation at $$\langle \sqrt s \rangle $$ =34.6 GeV

  1986cited by this paper
• Complexity of Computer Computations

  1972cited by this paper

• Sampling with flows, diffusion, and autoregressive neural networks from a spin-glass perspective

  2023cites this paper
• Biased landscapes for random constraint satisfaction problems

  2018cites this paper
• Satisfiability Thresholds for Regular Occupation Problems

  2018cites this paper
• Phase transitions in the q-coloring of random hypergraphs

  2017cites this paper
• The large deviations of the whitening process in random constraint satisfaction problems

  2016cites this paper
• Satisfiability Threshold for Random Regular nae-sat

  2013cites this paper
• Reweighted Belief Propagation and Quiet Planting for Random K-SAT

  2012cites this paper
• Statistical Physics of Hard Optimization Problems

  2008cites this paper
• Constraint satisfaction problems with isolated solutions are hard

  2008cites this paper
• Grassmann integral representation for spanning hyperforests

  2007cites this paper
• On the Freezing of Variables in Random Constraint Satisfaction Problems

  2007cites this paper