**THE MALLAT FAMILY FUND FOR RESEARCH IN
MATHEMATICS **

**invites**** you to a**

**SPECIAL LECTURE SERIES**** **

**to**** be presented by**

Professor
Alexander Barvinok

The
lectures will be held in

Room 232

Technion - Israel Institute of Technology

Lecture
I:

**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:

**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:

**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.