Speaker:Eric Vigoda
Time:2004-12-13 14:00:00
Place:Room 317-2, Bldg 302, SNU


In this talk we will look at Markov chain Monte Carlo algorithms for estimating the permanent of a matrix. The permanent is a classical problem in Theoretical Computer Science, with applications to a variety of scientific fields. Roughly speaking, the permanent is the determinant without the alternating sgn. We will first describe recent work with Jerrum and Sinclair, which gives the first polynomial time algorithm to approximate the permanent of any non-negative matrix. We will then describe some more recent advances which improves the running time to a more respectable O(n7) from the original O(n26). The algorithms are a simulated annealing algorithm involving random walks on the collection of perfect matchings of a bipartite graph.

[ List ]