Research Duo Awarded the Fulkerson Prize

Computing the volume of a convex body is an ancient problem that mathematicians have been working on for centuries. School of Computer Science (SCS) Professor Santosh Vempala and Ph.D. alumnus Ben Cousins were recently awarded for their solution.

The researchers received the Fulkerson Prize, which awards outstanding papers in discrete mathematics. The Mathematical Optimization Society and the American Mathematical Society jointly award the prize every three years. This year’s prize was presented at the International Symposium on Mathematical Programming (ISMP 2024) in July in Montreal.

Many solutions have been proposed to estimate the volume of a convex body, but these have all been time-consuming and highly impractical. In 2018, Vempala and Cousins found a method that is faster in theory and practical in thousands of dimensions.

Their new method makes it faster to estimate the volume by working with a sequence of Gaussian distributions- or high-dimensional bell curves- inside the convex body of interest.

To achieve these improvements, the method involves a faster and more efficient way of picking random points inside the shape. It also chains together these samples to obtain an accurate estimate of the volume. Sampling and volume computation have diverse applications in fields such as Bayesian inference, differential privacy, systems biology, and others.

"The algorithmic perspective in high dimension has been very rewarding; I am grateful to have been introduced to it early in my research life and eager to see what lies ahead,” said Vempala.

Renowned computer science researcher Ravi Kannan offered his congratulations to Vempala. In 1991, Kannan received the Fulkerson Prize for his work with Martin Dyer and Alan Frieze on the first theoretically efficient approximation of the volume of a convex body.

"He has been a leader in high dimensional geometric algorithms derived with the help of his deep insights into the mathematical structure and richly deserves the prize," Kannan said. 

Along with his role in SCS, Vempala serves as the Frederick Storey II Chair of Computing and as an adjunct professor in the School of Mathematics and the H. Milton Stewart School of Industrial and Systems Engineering. He is also the director of Georgia Tech’s Ph.D. program in Algorithms, Combinatorics, and Optimization, which includes faculty from multiple Georgia Tech schools.