[CS Colloquium] Eric Vigoda, Phase Transitions in Approximate Counting

FYI (CS Colloquium)

Phase Transitions in Approximate Counting
Eric Vigoda
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.


Comments are closed.