THE MALLAT FAMILY FUND FOR RESEARCH IN MATHEMATICS

invites you to a

SPECIAL LECTURE SERIES

to be presented by

Professor Alexander Barvinok

University of Michigan

The lectures will be held in

Room 232

Amado Mathematics Building
Technion - Israel Institute of Technology
Haifa, Israel

Lecture I:  Thursday 31 May, 2007 at 15:30

An asymptotic equivalence of

optimization and counting

In this talk, based on a joint work with Alex Samorodnitsky (Hebrew Univ.), I plan to discuss how one can get an asymptotically accurate estimate of the cardinality of a combinatorially defined set (such as the set of perfect matchings in a given graph) by solving a randomly generated optimization problem on the set (such as to find  the maximum weight of a perfect matching in the edge- weighted graph). In many interesting cases the optimization is easy (polynomial time), while counting seems to be hard. The argument is based on a certain isoperimetric inequality in the Boolean cube, which relates the cardinality of a subset of the Boolean cube and the average maximum value of a random linear functional on the subset.

Lecture II:  Sunday, 3 June, 2007  at 15:30

Counting magic squares,

contingency tables, integer flows, and more

In this ongoing project with Alex Samorodnitsky (Hebrew Univ.) and Alex Yong (Univ. of Minnesota), we discuss a way to count contingency tables (non-negative integer matrices with the prescribed row and column sums), magic squares (same as above, but all the row and column sums are equal) and integer feasible flows in a network (same as in the contingency tables, but with zeros in prescribed positions). The idea is to represent the desired quantity as the expectation of the permanent of a random matrix and then reduce the expectation to the integral of a log-concave density. We manage to prove efficient complexity bounds in a number of cases (including the enumeration of magic squares) while our computational experiments suggest that the algorithm is essentially nicer than we are able to prove.

Lecture III:  Monday, 4 June, 2007  at 15:30

Integer points and rational functions

The formula for the sum of the geometric series demonstrates that a potentially long, even infinite, Laurent polynomial can be written as a short rational function. Further proven examples of this phenomenon include generating functions for integer points in rational polyhedra, integer semigroups, and some others, while conjecturally the phenomenon of "compression" of long polynomials to short rational functions is even broader.