Banner Michael and Sheila Held Prize

Banner Michael and Sheila Held Prize

About the Michael and Sheila Held Prize

The Michael and Sheila Held Prize will be presented annually and carries with it a $100,000 prize. The prize honors 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 prize was established in 2017 by the bequest of Michael and Sheila Held.

Inaugural Presentation

Prasad Raghavendra, University of California, Berkeley, and David Steurer, ETH Zurich, will receive the inaugural Michael and Sheila Held Prize in 2018.

Raghavendra and Steurer have made revolutionary contributions to the understanding of optimization and complexity in computer science, work that has relevance for solving the most difficult and intractable of computing problems. 

Their work — conducted both individually and often in collaboration — suggests that among all efficient algorithms, semidefinite programming gives the best possible approximation guarantees for a host of “hard” optimization problems involving, for example, constraint satisfaction or graph partitioning. Read more about their work»

Recipients

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»
Press release»

Powered by Blackbaud
nonprofit software