School of Computer Science, Georgia Institute of Technology, Atlanta, Georgia, USA

*Friday 3PM-4PM*

Seminar series on discrete mathematics @ Dept. of Mathematical Sciences, KAIST.

Analyzing Markov Chains using Belief Propagation

Eric Vigoda

School of Computer Science, Georgia Institute of Technology, Atlanta, Georgia, USA

School of Computer Science, Georgia Institute of Technology, Atlanta, Georgia, USA

2016/12/16 *Friday 3PM-4PM*

For counting weighted independent sets weighted by a parameter λ (known as the hard-core model) there is a beautiful connection between statistical physics phase transitions on infinite, regular trees and the computational complexity of approximate counting on graphs of maximum degree D. For λ below the critical point there is an elegant algorithm devised by Weitz (2006). The drawback of his algorithm is that the running time is exponential in log D. In this talk we’ll describe recent work which shows O(n log n) mixing time of the single-site Markov chain when the girth>6 and D is at least a sufficiently large constant. Our proof utilizes BP (belief propagation) to design a distance function in our coupling analysis. This is joint work with C. Efthymiou, T. Hayes, D. Stefankovic, and Y. Yin which appeared in FOCS ’16.

Computational Phase Transitions for the Potts Model

Eric Vigoda

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

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

2015/4/14 Tue 4PM-5PM

This is a followup talk to my CS colloquium on March 2. In that talk I discussed the problems of counting independent sets and colorings. Those problems are examples of antiferromagnetic systems in which neighboring vertices prefer different assignments. In this talk we will look at ferromagnetic systems where neighboring vertices prefer the same assignment. We will focus on the ferromagnetic Potts model. We will look at the phase transitions in this model, and their connections to the complexity of associated counting/sampling problems and the performance of related Markov chains.

The talk is based on joint works with Andreas Galanis, Daniel Stefankovic, and Linji Yang.

The talk is based on joint works with Andreas Galanis, Daniel Stefankovic, and Linji Yang.

FYI (Lecture Series)

Approximating the Permanent

Eric Vigoda

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

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

2015/3/11 Wed 9AM-10:15AM (E3-1, Room 1501)

I’ll explain the canonical paths method for bounding the mixing time of a

Markov chain. I’ll show the analysis of a Markov chain for generating a

random matching of a graph and its extension for the estimating the

number of perfect matchings of a bipartite graph.

Markov chain. I’ll show the analysis of a Markov chain for generating a

random matching of a graph and its extension for the estimating the

number of perfect matchings of a bipartite graph.

FYI (Lecture Series)

Introduction to Markov Chain Monte Carlo Methods

Eric Vigoda

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

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

2015/3/6 Fri 9AM-10:15AM (E3-1, Room 1501)

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.