WASHINGTON -- The National Academy of Sciences will award the first annual Michael and Sheila Held Prize to Prasad Raghavendra, associate professor of electrical engineering and computer science at the University of California, Berkeley, and David Steurer, professor of theoretical computer science at ETH Zurich.  The pair are receiving the $100,000 prize “for a body of work which revolutionizes our understanding of optimization and complexity” in computer science. 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.

Researchers who study computational complexity identify problems that are classified as “hard” -- in other words, impossible for computers to solve within a reasonable time frame.  They then work to determine the “hardness of approximation,” or whether a computer can efficiently find an approximate solution to such a problem.  Individually or in collaboration, the work of Raghavendra and Steurer suggests that among all efficient algorithms, semidefinite programming (SDP) gives the best possible approximation guarantees for a host of hard optimization problems.

Raghavendra built upon the revolutionary 2003 “Unique Games Conjecture” theory to show that a concrete algorithm based on SDP is optimal for every constraint satisfaction problem -- problems that involve a set of required decisions, a fixed set of possibilities, and a set of constraints that allow only certain combinations of possibilities.  Later, Raghavendra and Steurer developed the “small set expansion hypothesis,” which yields an even greater array of algorithmic implications than those implied by Unique Games Conjecture. Their work yielded 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 SDP, which has led to new algorithms and a deeper understanding of SDP’s limitations.

The prize, made possible through a bequest from the estate of Michael and Sheila Held, will be presented to Raghavendra and Steurer on April 29 during the Academy's 155^th annual meeting.

The National Academy of Sciences is a private, nonprofit institution that was established under a congressional charter signed by President Abraham Lincoln in 1863. It recognizes achievement in science by election to membership, and -- with the National Academy of Engineering and the National Academy of Medicine – provides science, technology, and health policy advice to the federal government and other organizations.

Contacts:
Molly Galvin, Director, Executive Communications
Office of News and Public Information
202-334-2138; e-mail: news@nas.edu
http://www.nasonline.org/ 
Twitter: @theNASciences
Facebook: https://www.facebook.com/theNASciences