THE MALLAT FAMILY FUND FOR RESEARCH IN MATHEMATICS
invites you to a
SPECIAL LECTURE SERIES
to be presented by
The lectures will be held in
Technion - Israel Institute of Technology
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.
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.
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.