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.