Test of Time 1993 Award

Alexander Barvinok:
A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension Is Fixed

This exceptional paper presented the first polynomial time algorithm for counting the number of lattice points inside a polyhedron (equivalently, the number of feasible solutions to an integer program) in any fixed dimension d.  Previously a polynomial time algorithm was known only for d ≤ 4.  The paper makes ingenious use of Brion’s identity for exponential sums over polyhedra, as well as other tools such as Laurent expansion and decompositions into primitive cones.

The paper gives a complete solution to a natural problem. Its method is elegant and innovative. The types of analytical tools used in the paper have seen further significant development in recent years. The algorithm in the paper has had wide ranging applications in many areas from mathematical programming to algebraic geometry. The result itself has been improved in some aspects but has never been superseded.