KAIST Discrete Math Seminar

I’ll introduce Markov chains and their key properties. Then I’ll explain the PageRank algorithm of Brin and Page which is the basis of the Google search engine.

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.