Banner Michael and Sheila Held Prize
Scheduled for presentation in 2024, recipients will be announced in January 2024. To get awards news straight to your inbox, make sure to sign up for our Connect with Awards newsletter.
About the 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). The Held prize was established in 2017 by the bequest of Michael and Sheila Held.
Most Recent Recipient
 |
Thomas Vidick, California Institute of Technology and Weizmann Institute of Sciences, will receive the 2023 Michael and Sheila Held Prize.
Vidick has deepened and transformed our understanding of quantum complexity and quantum cryptography.
Vidick’s research is at the interface of theoretical computer science, quantum information and cryptography. Read more about Vidick's work»
Recipients
Thomas Vidick (2023)
For his breakthroughs in quantum complexity and quantum cryptography that led to the proof that the class of languages in which membership may be established by quantum multi-prover interactive proof systems is equal to the class of recursively enumerable languages.
Read more about Vidick's work»
Amit Sahai (2022)
For a leading role in development of cryptographic Software Obfuscation and its applications, starting from initial conception of "Indistinguishability Obfuscation" and culminating in new constructions based upon well-founded cryptographic assumptions. These breakthroughs highlight how computational complexity can enable secrecy while computing in insecure environments.
Read more about Sahai's work»
Watch Sahai's acceptance speech»
Adam W. Marcus, Daniel Alan Spielman, and Nikhil Srivastava (2021)
For their breakthrough works on the Kadison-Singer problem and on Ramanujan graphs, and the underlying theory that leads to new connections between computer science, mathematics and physics.
Read more about their work»
Watch their acceptance speech»
Julia Chuzhoy (2020)
For her foundational research on algorithms for routing in networks and finding disjoint paths in graphs, which has introduced powerful new techniques and resolved deep open questions in both discrete optimization and in the structure of graphs.
Read more about Chuzhoy's work»
Watch Chuzhoy's acceptance speech»
Ola Svensson (2019)
For breakthroughs in combinatorial optimization and graph-theoretic algorithms culminating in the first constant factor approximation algorithm for the asymmetric traveling salesman problem.
Read more about Svensson's work»
Watch Svensson's acceptance speech»
Prasad Raghavendra and David Steurer (2018)
For a body of work which revolutionizes our understanding of optimization and complexity. It better explains the exact limits to efficient approximation of NP-hard problems. It provides better understanding of the computational assumptions underlying hardness of approximation. And it develops a structure theory of linear and semi-definite programming and their hierarchies, which leads to new algorithms and new lower bounds.
Read more about their work»
Watch their acceptance speech»
Press release»
