Raghavendra and Steurer 2018 Held Prize

Raghavendra and Steurer 2018 Held Prize

Join us in congratulating Prasad Raghavendra and David Steurer!

Prasad Raghavendra, University of California, Berkeley,and David Steurer, ETH Zurich, jointly received 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.

Raghavendra built upon Subhash Khot’s 2003 unique games conjecture (UGC) to show that a concrete algorithm based on the technique of semidefinite programming is optimal for every constraint satisfaction problem. Later, Raghavendra and Steurer developed the small set expansion hypothesis that yields an even greater array of algorithmic implications than those implied by the unique games conjecture. These works yield a potential characterization of the limits up to which efficient algorithms can approximate broad classes of NP-hard optimization problems. Subsequently, the awardees have advanced a theoretical framework for semidefinite programming, one that has led to new algorithms and a deeper understanding of the limitations of semidefinite programming.  

The Michael and Sheila Held Prize, presented for the first time in 2018, 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. The 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.

Please use the following sample social media posts and other materials to congratulate Prasad Raghavendra and David Steurer.

Facebook - copy the text and click on the Facebook button to share

 Watch Prasad Raghavendra of @UCBerkeley and David Steurer of @ETH_en receive @theNASciences Michael and Sheila Held Prize at #NAS155! They have revolutionized our understanding of optimization and complexity in computer science. The award will be presented during the 155th NAS Annual Meeting on Sunday, April 29. #algorithm http://bit.ly/155awards

Twitter - click on the Twitter button to share your favorite message

Congratulations Prasad Raghavendra of @UCBerkeley and David Steurer of @ETH_en, recipients of 2018 @theNASciences Michael and Sheila Held Prize! #algorithm http://www.nasonline.org/programs/awards/2018/Raghavendra-Steurer.html

Prasad Raghavendra of @UCBerkeley and David Steurer of @ETH_en earn @theNASciences Michael and Sheila Held Prize for revolutionizing our understanding of optimization and complexity in computer science. http://www.nasonline.org/programs/awards/2018/Raghavendra-Steurer.html

Watch Prasad Raghavendra of @UCBerkeley and David Steurer of @ETH_en receive @theNASciences Michael and Sheila Held Prize at #NAS155! http://www.nasonline.org/programs/awards/2018/Raghavendra-Steurer.html

Graphics - save the image to accompany your post

Links

Watch the Acceptance Speech »

Press Release »

Michael and Sheila Held Prize »

2018 NAS Award Recipients »

Powered by Blackbaud
nonprofit software