Professor Alexander Barvinok's paper, "A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed," has been selected as the recipient of the 2023 Foundations of Computer Science (FOCS) Test of Time award.

The 30-year award recognizes a paper from FOCS 1993 that has stood the test of time. The award will be presented at FOCS 2023, which will be held November 6-9, 2023, in Santa Cruz, California. 

As decribed on the FOCS 2023 web site:

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.

Congratulations Prof. Barvinok!