EVENT DETAILS AND ABSTRACT

Title: Counting solutions of random regular NAESAT beyond condensation threshold
Speaker: Yumeng Zhang
Speaker Info: Berkeley
Brief Description:
Special Note:
Abstract:

Consider the k-NAESAT problem on d random regular graphs. It is known that in a certain regime before the satisfaction threshold, the expected number of solutions is exponentially larger than the typical value. In this talk we give an explicit formula for the typical number of solutions and explain its relationship to the statistical physic theory of "one step replica symmetry breaking" models.