FYI (CS Colloquium)

Phase Transitions in Approximate Counting

Eric Vigoda

College of Computing, Georgia Institute of Technology, Atlanta, GA, USA

College of Computing, Georgia Institute of Technology, Atlanta, GA, USA

2015/3/2 Mon 4PM-5PM (E3-1, Room 1501)

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.