Speaker: Alex Samorodnitsky (Hebrew University)

Title: "Random Weighting, Asymptotic Counting, and Inverse Isoperimetry"

Abstract:
---------
For a family X of k-subsets of {1...n}, let Gamma(X, mu) be the
expected maximum weight of a subset from X when the weights of 1...n are
chosen independently at random from a symmetric probability distribution
mu.

Motivated by problems of efficient combinatorial counting, we look for a
distribution for which Gamma(X) gives a good estimate of ln |X|
(in many interesting cases, Gamma can be easily computed while counting
can be hard). It turns out that 'good' distributions are those with
exponentially  decreasing tails. In particular the best (in a well-defined
sense) distribution to take is the logistic distribution.

This leads to efficient approximation algorithms for many counting
problems. Essentially, if |X| = alpha^k (think of large alpha), the
algorithm computes |X| up to a multiplicative error of order (ln alpha)^k.

If the weights of the coordinates 1...n are chosen to be 1, -1 with
probability 1/2, the problem of relating Gamma(X) and |X| reduces to
the usual vertex isoperimetric questions on the Boolean cube. For a
general symmetric distribution mu one has to deal with questions of the
following type: Among all subsets X of the Boolean cube of a fixed
cardinality |X|, which has the smallest (largest) average width according
to mu. It turns out that the sets of smallest average width (up to
an asymptotically negligible error) are either Hamming balls - of varying
dimensions and radii - or direct products of two such balls.

(Joint work with Alexander Barvinok)