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 for models in the 1RSB universality class, the solution space condenses into large clusters, just below the satisfiability threshold. We establish this phenomenon for the first time for random regular NAE-SAT in the condensation regime. That is, 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.

---

Zoom ID: 832 222 6176 Password: saarc

The exponential random graph model (ERGM) is a version of the Erdos-Renyi graphs, obtained by tilting according to the subgraph counting Hamiltonian. Despite its importance in the theory of random graphs, lots of fundamental questions have remained unanswered owing to the lack of exact solvability. In this talk, I will introduce a series of new concentration of measure results for the ERGM in the entire sub-critical phase, including a Poincare inequality, Gaussian concentration, and a central limit theorem. Joint work with Shirshendu Ganguly.

---

Zoom ID: 832 222 6176 Password: saarc