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

Conferences/Seminars/Lectures

Events By Interest

Academic

Events By Audience

Public

Events By School

School of Science

Tags

prob_sem, aldixon

Website

https://math.mit.edu/seminars/probabi...

Department
Department of Mathematics
Hashtag

#Mathematics

Contact Email

aldixon@mit.edu

Add to my calendar

Recent Activity

You're not going yet!

This event requires registration.