ACO The ACO Seminar (2016–2017)

Feb. 24, 4:30pm, Wean 7500 (Note unusual day/time)
Allan Sly, Princeton
Counting solutions to random constraint satisfaction problems


Random constraint satisfaction problems encode many interesting questions in random graphs such as the chromatic and independence numbers. Ideas from statistical physics provide a detailed description of phase transitions and properties of these models. I will discuss the question of the number of solutions to random regular NAE-SAT. This involves understanding the condensation regime where the model undergoes what is known as a one step replica symmetry breaking transition. We expect these approaches to extend to a range of other models in the same universality class. Joint with with Nike Sun and Yumeng Zhang.

Back to the ACO home page