Spring 2016

Counting Program Seminar Series

Friday, March 18th, 2016, 2:00 pm3:00 pm

Add to Calendar


Yumeng Zhang (UC Berkeley)


Calvin Lab Room 116

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.