Seminar - Counting Solutions to Random Constraint Satisfaction Problems

Counting Solutions to Random Constraint Satisfaction Problems
Date & Time: 
Monday, May 16, 2016 - 12:15 to 13:30
Allan Murray Sly, University of California
Room 301, NYU Shanghai | 1555 Century Avenue, Pudong New Area, Shanghai

The seminar is sponsored by NYU-ECNU Institute of Mathematical Sciences at NYU Shanghai.



Satisfaction problems subject to random constraints are a well-studied area in combinatorics and the theory of computation, for example random colourings of random graphs and random k-sat. Ideas from statistical physics provide a detailed description of phase transitions and properties of these models. I will discuss the condensation regime where these model undergo a one-step replica symmetry breaking transition.
Joint work with Nike Sun and Yumeng Zhang.


Allan Murray Sly is an Associate Professor of Statistics at the University of California, Berkeley. His research interests include Discrete Probability, Probability in statistical physics and theoretical computer science, Mixing Times of Markov Chains, Stochastic Processes on Networks, Combinatorial statistics.

Location & Details: 

Transportation Tips:

  • Taxi card
  • Metro: Century Avenue Station, Metro Lines 2/4/6/9 Exit 6 in location B
  • Shuttle bus:
    From Zhongbei Campus, Click here
    From ECNU Minhang Campus, Click here