KAIST Discrete Math Seminar

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.

The hard-core model has received much attention in the past couple of decades as a lattice gas model with hard constraints in statistical physics, a multicast model of calls in communication networks, and as a weighted independent set problem in combinatorics, probability and theoretical computer science.
In this model, each independent set I in a graph G is weighted proportionally to λ^|I|, for a positive real parameter λ. For large λ, computing the partition function (namely, the normalizing constant which makes the weighting a probability distribution on a finite graph) on graphs of maximum degree Δ≥3, is a well known computationally challenging problem. More concretely, let λ_c(T_Δ) denote the critical value for the so-called uniqueness threshold of the hard-core model on the infinite Δ-regular tree; recent breakthrough results of Dror Weitz (2006) and Allan Sly (2010) have identified λ_c(T_Δ) as a threshold where the hardness of estimating the above partition function undergoes a computational transition.
We focus on the well-studied particular case of the square lattice Z², and provide a new lower bound for the uniqueness threshold, in particular taking it well above λ_c(T₄). Our technique refines and builds on the tree of self-avoiding walks approach of Weitz, resulting in a new technical sufficient criterion (of wider applicability) for establishing strong spatial mixing (and hence uniqueness) for the hard-core model. Our new criterion achieves better bounds on strong spatial mixing when the graph has extra structure, improving upon what can be achieved by just using the maximum degree. Applying our technique to Z² we prove that strong spatial mixing holds for all λ<2.3882, improving upon the work of Weitz that held for λ<27/16=1.6875. Our results imply a fully-polynomial deterministic approximation algorithm for estimating the partition function, as well as rapid mixing of the associated Glauber dynamics to sample from the hard-core distribution.
This is joint work with Ricardo Restrepo, Jinwoo Shin, Prasad Tetali, and Linji Yang. A preprint is available from the arXiv at: arxiv:1105.0914

The Markov Chain Monte Carlo (MCMC) method is a widely-used algorithmic approach for randomly sampling from and estimating the cardinality of large sets. In this talk I will give an introduction to the MCMC approach. Then I will explain a more sophisticated variant that gives a polynomial-time algorithm to approximate the permanent of a non-negative matrix. In graph-theoretic terminology, the permanent corresponds to the number of perfect matchings of a bipartite graph.