Combinatorics Seminar
When: Sunday, May 18, 10am
Where: Schreiber 309
Speaker: Alex Samorodnitsky, Hebrew University,
Title: Counting magic squares
Abstract:
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 from above by the 'golden ratio'.
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).
A joint work with Alexander Barvinok, Zur Luria, and Alex Yong.