***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Date: Thursday 17th November, 3:00 in Fine Hall 224.
 
Speaker: Patrick Devlin (Rutgers)

Title: Matrices with large permanent


The permanent of a matrix has long been an important quantity in combinatorics
and computer science, and more recently it has also had applications to physics
and linear-optical quantum computing.  A result of Gurvits bounds the permanent
of an n by n matrix in terms of its operator norm via  |perm(A)| \leq |A|^n,
and he characterized the matrices for which this is tight (they are essentially
just scalar multiples of permutation matrices except that each entry can be
replaced by anything with the same modulus).

In this talk, we prove a stability version of this result (conjectured by
Aaronson) asserting that unless A is very close (in a particular sense) to one
of these extremal matrices, its permanent is exponentially smaller than
Gurvits's upper bound would suggest.  Although the result deterministically
holds for all matrices over C (or R), our proof is entirely probabilistic.

The talk should be suitable for a broad audience, and no particular background
knowledge will be assumed.  Joint with Ross Berkowitz.

                       -----------

Next week:  no seminar (Thanksgiving). Week after: Eric Naslund (Princeton)

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)