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.