Counting solutions to random constraint satisfaction problems

Counting solutions to random constraint satisfaction problems - Allan Sly

Allan Sly
Princeton University
September 26, 2016
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.