[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

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:

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 
calling (617) 253-6185.

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.