Counting Program Seminar Series

Counting Solutions of Random Regular NAESAT Beyond Condensation Threshold

We consider the k-NAESAT problem on d random regular graphs and determine its log partition function in the  condensation regime, where standard first moment estimation is known to inflate by a constant fraction. The  result matches the prediction of statistical physicists based on the so-called the "one step replica symmetry breaking" heuristics. It also suggests that in this regime, the solution space is dominated by a few large clusters of constant fraction. Our method is based on analyzing a weighted Belief Propagation using a novel encoding of local neighborhood. This is joint work with Allan Sly and Nike Sun.