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).

Irit Dveer Dinur, Institute for Advanced Study, Princeton and Weizmann Institute, Rehovot; Subhash Khot, New York University; Guy Kindler, Hebrew University of Jerusalem; Dor Minzer, Massachusetts Institute of Technology; and Muli Safra, Tel Aviv University, received the 2026 Michael and Sheila Held Prize.

Dinur, Khot, Kindler, Minzer, and Safra’s breakthrough work on the 2-to-2 Games Theorem has advanced theoretical computer science.

Their groundbreaking series of works—the result of several years of deep collaboration and the development of novel mathematical techniques— led to the proof of the 2-to-2 Games Theorem, the most significant advance and strongest evidence to date for the Unique Games Conjecture, a central open question in theoretical computer science.

This monumental achievement has profoundly altered the landscape of hardness of approximation and Probabilistically Checkable Proofs, introducing deep new insights into combinatorics and discrete analysis. The theorem itself has important consequences for problems such as vertex cover and graph coloring.

Watch them receive the award online during the 163rd NAS Annual Meeting on April 26th.