Speaker: Francis Sullivan, IDA/Center for Computing Sciences

Title: Approximating the permanent

Abstract: It is well known that the problem of obtaining a numerical value for the permanent of a matrix is NP-hard, even if the entries of the matrix are 0/1. Yet, obtaining such values, or even approximating them with less than exponential work, is important for questions arising in statistical physics and related areas. There are many results about approximating the permanent, including the fundamental work of Jerrum and Sinclair that ultimately resulted in an FPRAS for the permanent. Interestingly, none of the rigorous approximation methods result in a simple and practical method that can be used to obtain actual numerical approximations, while heuristic methods that can be and are used in practice lack a firm mathematical foundation. We will explore this dichotomy, describe a way to use heuristics to make rigorous methods more practical, and remark on some possible directions for developing a more solid mathematical basis for some heuristic methods.

Department of Mathematical Sciences
George Mason University
4400 University Drive, MS 3F2
Fairfax, VA 22030-4444
http://math.gmu.edu/
Tel. 703-993-1460, Fax. 703-993-1491