Events
Spring 2016

Counting Program Seminar Series

Mar 18, 2016 2:00 pm – 3:00 pm 

Add to Calendar

Speaker: 

Yumeng Zhang (UC Berkeley)

Location: 

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.