Place and Time: Monday, April 20th, 2009, Piece Hall 320, 29 Oxford Street
Refreshments at 2:30pm, talk at 2:45
A magic square is an integer
matrix with equal row and column sums. A contingency table is simply an integer
matrix. We will describe a quasi-polynomial-time algorithm to count magic
squares and, more generally, contingency tables with given row and column sums,
such that the ratio between the maximal and the minimal column (or row) sums is
bounded by 2.
An important ingredient of the analysis of this algorithm is understanding the behavior of the permanent of a random matrix, in which all the entries are i.i.d. exponential random variables. We are using the classical Bregman's and Egorychev-Falikman's bounds to estimate the permanents, and, unfortunately, can say very little beyond this. We will, however, describe some conjectures, generalizing the Bregman bound, which, if true, might allow us to count better (e.g., contingency tables with the ratio between column sums bounded by any constant).
Joint work with Alexander Barvinok, Zur Luria, and Alex Yong