Michael and Sheila Held Prize

The Michael and Sheila Held Prize is presented annually to honor outstanding, innovative, creative, and influential research in the areas of combinatorial and discrete optimization, or related parts of computer science, such as the design and analysis of algorithms and complexity theory. This $100,000 prize is intended to recognize recent work (defined as published within the last eight years).

Nima Anari, Stanford University, Kuikui Liu, Massachusetts Institute of Technology, and Shayan Oveis Gharan and Cynthia Vinzant, University of Washington, will receive the 2025 Michael and Sheila Held Prize.

Anari, Liu, Oveis Gharan, and Vinzant have made major advances in the theory of matroids and expanded our understanding of the mixing rates of Markov chains.

Their work has bridged the theory of high dimensional expanders, the geometry of polynomials, and the analysis of Markov chains. Their work resolves the 30-year-old Mihail-Vazirani conjecture that the basis exchange walk on a matroid mixes rapidly, and for initiating the highly influential theory of spectral independence.

Creating connections between these three subfields, their work has already led to numerous important developments in theoretical computer science and will continue to drive this work forward in the future.

The Held Prize will be presented in a ceremony on Sunday, April 27 during the National Academy of Sciences’ 162nd annual meeting. The ceremony will be livestreamed.