Title: Counting solutions of random regular NAESAT beyond condensation threshold

Abstract: We consider the $k$-NAESAT problem on d random regular graphs and determine its $\log$ partition function in the so called condensation regime, where standard first moment estimation is known to inflate by a constant fraction. Our result partially verifies the "one step replica symmetry breaking" picture from statistical physics that in this regime, the solution space is dominated by a few large clusters of constant size. 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.