Marston Morse Lectures

Statistical physics of random CSPs

I will describe recent progress in determination of asymptotic behavior in random constraint satisfaction problems, including the independent set problem on random graphs, random regular NAE-SAT, and random SAT. The results include sharp phase transitions and some understanding of solution geometry, particularly in the setting of the random regular NAE-SAT problem. In this lecture I will survey the physics heuristics, and explain how they lead to combinatorial models for the solution geometry, which form a basis of mathematical approaches to these problems.

This lecture is based in part on joint works with Zsolt Bartha, Jian Ding, Allan Sly, and Yumeng Zhang.

 

Date & Time

April 19, 2021 | 3:00pm – 4:00pm

Location

Remote Access via Zoom videoconferencing (link below)

Speakers

Nike Sun

Speaker Affiliation

Massachusetts Institute of Technology

Event Series