Matrices with large permanent

Matrices with large permanent

-
Patrick Devlin , Rutgers University
Fine Hall 224

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.