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). Nominations are being accepted now for the 2025 Prize.

Eshan Chattopadhyay, Cornell University, and David Zuckerman, University of Texas at Austin, received the 2024 Michael and Sheila Held Prize.

Chattopadhyay and Zuckerman’s groundbreaking work on randomness extraction and Ramsey graph construction has advanced theoretical computer science.

Using an innovative and creative approach, Chattopadhyay and Zuckerman solved a longstanding open problem by introducing an algorithm that combines two independent low-quality random sources to create one high-quality random source. Previous attempts needed at least one of the two input sources to be of moderately high-quality. The new algorithm, called a two-source extractor, also gives a major improvement to an important mathematical problem in Ramsey Theory.

Watch their acceptance speech.