Thursday May 6: ORC Seminar: Alexander Barvinok : 4:15 PM

[Avisha Lalla <avisha math mit edu>]

Thursday, May 6, 2010

Alexander Barvinok
Professor of Mathematics University of Michigan, Ann Arbor
will be speaking on

Gaussian and Almost Gaussian Formulas for the Number of Integer Points 
in Polyhedra
---------------------------------------------------------
(Abstract and information about the speaker follow below.)

The talk will be held on Thursday, May 6 from 4:15 to 5:15 PM in MIT's 
E51-376
followed by refreshments in the ORC Conference Room (E40-106).

Building E51 (Tang Center) is located in the MIT Sloan School.  For
directions to the venue, please follow the following link:
http://whereis.mit.edu/map-jpg?selection=E51.

If you have any questions, please contact Matthew Fontana 
<mfontana mit edu>, Philipp
Keller <pkeller mit edu>, or Alexander Rikun <arikun mit edu> by email or 
by
calling (617) 253-6185.

Abstract
----------
In this work, joint with J.A. Hartigan (Yale), we present some rather 
simple and computationally efficient approximate formulas for the number 
of integer points in higher-dimensional polyhedra. The underlying 
intuition is provided by the maximum entropy principle and the Local 
Central Limit Theorem. We show that the formulas are asymptotically 
exact for a reasonably wide class of polyhedra, including multi-way 
transportation polytopes. For other interesting enumeration problems, 
such as those of counting non-negative integer matrices with prescribed 
row and column sums or counting labeled graphs with prescribed degree 
sequences, one has to employ an "Edgeworth correction factor", which is 
also efficiently computable.

About the speaker
-------------------
Alexander Barvinok is a professor of mathematics at the University of 
Michigan, Ann Arbor. He is interested in computational complexity and 
algorithms in algebra, geometry and optimization.