### GEORGE MASON
UNIVERSITY

DEPARTMENT OF MATHEMATICAL
SCIENCES

COLLOQUIUM

MARCH 20, 2015

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

**Time:** Friday, March 20, 2015, 3:30-4:20 p.m.

**Place:** Exploratory Hall, room 4106

**Refreshments** will be served at 3:00 p.m.

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