Probability Seminar | Youngtak Sohn (Brown)
Thursday, October 23, 2025 |
4:00 PM - 5:00 PM CT
Title: Phase transitions of random constraint satisfaction problems
Abstract: The framework of constraint satisfaction problems (CSPs) captures many fundamental problems in combinatorics and computer science, such as finding a proper coloring of a graph or solving Boolean satisfiability problems. To study the typical cases of CSPs, statistical physicists have proposed a detailed picture of the solution space for random CSPs based on non-rigorous methods from spin glass theory. In this talk, I will first survey the conjectured rich phase diagrams of random CSPs in the one-step replica symmetry breaking universality class. Then, I will describe mathematical progress in understanding the global and local geometry of solutions, particularly in random regular NAE-SAT problem. This is based on joint work with Danny Nam and Allan Sly.
Audience
- Faculty/Staff
- Post Docs/Docs
- Graduate Students