2024 Fulkerson Prize Citations

Ben Cousins and Santosh Vempala,
"Gaussian Cooling and O*(n³) Algorithms for Volume and Gaussian Volume", SIAM Journal on Computing, Vol. 47, 2018.

Computing the volume of a convex body is an ancient challenge. Cousins and Vempala develop a fast algorithm that approximates the volume of a well-rounded convex body while querying membership of a cubic number of points, and also present the fastest algorithms for integrating and sampling from a Gaussian measure restricted to a convex body. The impact of the ideas goes far beyond the two core problems addressed.

Nathan Keller and Noam Lifshitz,
"The Junta Method for Hypergraphs and the Erdős-Chvátal Simplex Conjecture", Advances in Mathematics, Vol. 392, 2021.

The authors give a new approach for solving Turán-type problems, which concern the maximum number of edges a hypergraph can have without containing certain expansions of a given forbidden substructure. The junta method approximates these hypergraphs by juntas, and the authors successfully apply it to the Erdős-Chvátal simplex conjecture, the Erdős-Sós forbidding one intersection problem, and the Frankl-Füredi special simplex problem.

Zilin Jiang, Jonathan Tidor, Yuan Yao, Shengtong Zhang, and Yufei Zhao,
"Equiangular lines with a fixed angle", Annals of Mathematics, Vol. 194, 2021.

The authors solve a combinatorial geometry problem that has received considerable attention since the 1960s: determine the maximum number of lines in d-dimensional space such that the angle between every pair is exactly θ. For fixed θ and large d, the authors provide a sharp bound. The proofs combine combinatorial ideas with tools from spectral graph theory in a clever, original and elegant way.