Abstract:
The permanent of a matrix is syntactically very similar to the determinant. Roughly speaking, it's the determinant without the alternating sign (i.e., just drop the sgn of the permutation). In graph theoretic terms, it corresponds to the number of perfect matchings of a bipartite graph. Despite this similarity with the determinant, the permanent is impossible to compute exactly in polynomial time (under standard assumptions). We present a randomized algorithm which approximates (within an arbitrarily close precision) the permanent of any non-negative matrix in polynomial time. I'll focus the talk on an interesting feature of our algorithm where we successively use one Markov chain to design another chain. This is joint work with Mark Jerrum (Edinburgh) and Alistair Sinclair (Berkeley).