Combinatorics Seminar

When: Sunday, November 3, 10am Where: Schreiber 309 Speaker: Alex Samorodnitsky, Hebrew University Title: Bounds on the permanent of a doubly stochastic matrix

Abstract:

We show that the permanent of a doubly stochastic n-by-n matrix A = (a_ij) is at least as large as

\prod_{i,j} (1-a_ij)^(1-a_ij)

and at most as large as 2^n times this number. Combined with previous work, this improves on the deterministic approximation factor for the permanent, giving 2^n instead of e^n-approximation.

If time allows, we will also discuss some more applications, such as using the lower bound to prove S.Friedland's "Asymptotic Lower Matching Conjecture" for the monomer-dimer problem.

Joint work with Leonid Gurvits.