Computer Science/Discrete Mathematics Seminar I | |

Topic: | Counting solutions to random constraint satisfaction problems |

Speaker: | Allan Sly |

Affiliation: | Princeton University |

Date: | Monday, September 26 |

Time/Room: | 11:15am - 12:15pm/S-101 |

Video Link: | https://video.ias.edu/csdm/2016/0926-AllanSly |

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.