Bicolouring random hypergraphs

Abstract

We study the problem of bicoloring random hypergraphs, both numerically and\nanalytically. We apply the zero-temperature cavity method to find analytical\nresults for the phase transitions (dynamic and static) in the 1RSB\napproximation. These points appear to be in agreement with the results of the\nnumerical algorithm. In the second part, we implement and test the Survey\nPropagation algorithm for specific bicoloring instances in the so called\nHARD-SAT phase.\n