March 13, 2003

Jesus De Loera, UC Davis

Lattice point counting in polyhedra: theory, applications, and software


A wide variety of problems in pure and applied mathematics involve the problem of counting the number of lattice points inside a region in space. Applications range from the pure (toric Hilbert functions, Kostant's partition function in representation theory, Ehrhart polynomials in combinatorics) to the applied (cryptography, integer programming, statistical contingency tables).
            Perhaps the most basic case is when the region is a convex bounded polyhedron. In the 1990's, new ideas from toric algebraic geometry by M. Brion, A. Khovanskii and others led A. Barvinok to propose rational generating functions as the ideal data structure for representing lattice points. In 1993 he constructed an elegant polynomial time algorithm when the dimension of a polytope is fixed. Today, further developments show that algebraic-analytic ideas are highly effective and computer experimentation allows us to consider new unsolved questions about lattices and polyhedra. This talk is a survey of this exciting research area.