MIT Probability Seminar

Monday, May 03, 2021 at 4:15pm to 5:15pm

Virtual Event

Speaker: Youngtak Sohn, Stanford

Title: Replica symmetry breaking for random regular NAE-SAT.

Abstract: In a wide class of random constraint satisfaction problems, ideas from statistical physics predict that there is a rich set of phase transitions governed by one-step replica symmetry breaking(1RSB). In particular, it is conjectured that there is the condensation regime below the satisfiability threshold, where the solution space condenses into the large clusters. We establish this phenomenon for the random regular NAE-SAT model by showing that most of the solutions lie in a bounded number of clusters and the overlap of two independent solutions concentrates on two points. Central to the proof is to calculate the moments of the number of clusters whose size is in an O(1) window.

This is joint work with Danny Nam and Allan Sly.

Event Type


Events By Interest


Events By Audience


Events By School

School of Science


prob_sem, aldixon


Department of Mathematics


Contact Email

Add to my calendar

Recent Activity

You're not going yet!

This event requires registration.