KAIST Discrete Math Seminar

In this talk we will explain a series of recent works that establish a beautiful connection between the computational complexity of approximate counting problems and statistical physics phase transitions. Our focus is on counting problems such as given a graph with n vertices can we estimate the number of independent sets or k-colorings of this graph in time polynomial in n? We will show that these problems experience a computational phase transition – on one side there is an efficient approximation algorithm and on the other side it is NP-hard to approximate. The critical point for this computational change coincides exactly with a statistical physics phase transition on infinite trees. Our recent work extends these connections to more general models. The key technical contribution is a novel approach for analyzing random regular graphs. This is joint work with Andreas Galanis (Oxford) and Daniel Stefankovic (Rochester) that appeared in STOC ’14.