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.
for each 
, where 
is the set of edges incident to v. The fractional matching number of G, written 
, is the maximum of 
over all fractional matchings f. Let G be an n-vertex graph with minimum degree d, and let 
be the largest eigenvalue of G. In this talk, we prove that if k is a positive integer and ![\lambda_1(G) < d\sqrt{1+\frac{2k}{n-k}}[/latex], then [latex]\alpha'_*(G) > \frac{n-k}{2}](http://s0.wp.com/latex.php?latex=%5Clambda_1%28G%29+%3C+d%5Csqrt%7B1%2B%5Cfrac%7B2k%7D%7Bn-k%7D%7D%26%2391%3B%2Flatex%26%2393%3B%2C+then+%26%2391%3Blatex%26%2393%3B%5Calpha%27_%2A%28G%29+%3E+%5Cfrac%7Bn-k%7D%7B2%7D&bg=ffffff&fg=000000&s=0 "\lambda_1(G) < d\sqrt{1+\frac{2k}{n-k}}[/latex], then [latex]\alpha'_*(G) > \frac{n-k}{2}")
.