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