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).