We study the problems of sampling and counting for a huge set of combinatorial objects, e.g., the collection of all independent sets or colorings of a graph. This genre of problems arises in a variety of scientific fields, such as phylogenetic reconstruction and inference in graphical models. We will show a beautiful connection that has been established between the efficiency of counting/sampling problems on general graphs and statistical physics phase transitions on trees. We will then explain related recent work proving fast convergence of Markov Chain Monte Carlo (MCMC) methods and loopy belief propagation (BP) algorithms, and the interplay between these two popular algorithms.
Eric Vigoda is a Professor of Computer Science and the director of the Algorithms and Randomness Center (ARC) at Georgia Tech. Vigoda received his PhD in Computer Science from UC Berkeley in 1999, and his BS and MS from Johns Hopkins University in 1994. After short postdoc stints at the University of Edinburgh and the Weizmann Institute, Vigoda started as an Assistant Professor at the University of Chicago in 2002, and moved to Georgia Tech in 2004. Vigoda received a Machtey award (1999), Fulkerson prize (2004) and is a fellow of the American Mathematical Society (AMS).