Abstract

The permanent of a matrix is a well-studied combinatorial problem with applications in many fields. It corresponds to the number of perfect matchings of a bipartite graph. Recall, a perfect matching is a subset of edges which covers each vertex exactly once.

Mathematicians began studying the permanent, about two centuries ago, because of its syntactic similarity to the determinant. In physics, its computation is central to the study of the dimer and Ising models. However, Valiant proved that exact computation of the permanent is impossible in polynomial time for general bipartite graphs (under standard complexity theoretic assumptions).

We resolve the computational complexity of approximating the permanent. In particular, we give a randomized algorithm which approximates the permanent within an arbitrarily close factor in time polynomial in the size of the graph. In this talk, I will highlight an interesting feature of our algorithm where we successively use one Markov chain to design another chain.

This is joint work with Mark Jerrum and Alistair Sinclair.