---------- Forwarded message ---------- From: Henry Cohn <cohn(a)math.mit.edu> Date: Wed, Nov 27, 2013 at 11:57 AM Subject: Special seminar: Nike Sun, Monday at 11:00 in E18-466A To: allmath(a)math.mit.edu DATE: Monday, December 2, 2013 TIME: 11:00-12:00 LOCATION: E18-466A SPEAKER: Nike Sun (Stanford) TITLE: Random constraint satisfaction problems and replica symmetry breaking ABSTRACT: Satisfaction and optimization problems subject to random constraints are a well-studied area in the theory of computation. These problems also arise naturally in combinatorics, in the study of random graphs. In the sparse regime, many of these problems exhibit long-range correlations, described by statistical physicists as "replica symmetry breaking." The physics formalism yields "1RSB" predictions for the exact location of the SAT-UNSAT transition, but none have been previously proved. With Jian Ding and Allan Sly, we determine the exact SAT-UNSAT transition in two problems within this class, the random regular not-all-equal-SAT problem and the random regular graph independent set problem. By passing to a replica symmetric model for clusters of solutions, our approach validates the 1RSB formalism for these models. The proof applies methods for the replica symmetric regime developed in earlier work with Amir Dembo, Andrea Montanari, and Allan Sly. _______________________________________________ qip mailing list qip(a)mit.edu http://mailman.mit.edu/mailman/listinfo/qip