ColloquiaTalk by Eric Vigoda, University of Edinburgh - Thursday, April 26

[Margery Ishmael]

Thursday, April 26 at 2:30 p.m. in Ryerson 251

ERIC VIGODA, Division of Informatics, University of Edinburgh

Title: "Approximating the Permanent"

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.

*The talk will be followed by refreshments in Ryerson 255*
(If you would like to meet the speaker, please send e-mail to 
marge at cs.uchicago.edu)
-- 
Margery Ishmael
Department of Computer Science
The University of Chicago
1100 E. 58th Street
Chicago, IL. 60637

Tel. 773-834-8977  Fax. 773-702-8487