Abstract
For a large class of random CSPs, the satisfiability threshold, corresponding to the critical density of constraints above which no more solution exists, may be predicted by methods from statistical physics. Additionally, such methods revealed the existence of several other phase transitions before satisfiability undergone by the set of solutions, as the problem is increasingly constrained. We apply these technics to a generalization of the coloring problem on random graphs to random hyper-graphs. Given a fixed number of colors, what is the critical density of hyper-edges above which it is not possible to color the hyper-graph without monochromatic hyper-edges? Above which density sampling the set of proper colorings with a Markov chain becomes hard?
This is joint work with Lenka Zdeborova, Guilhem Semerjian, Varsha Dani and Laura Florescu, initiated at the Simons institute during the Counting Complexity and Phase Transitions Program.