The National Academy of Sciences Jan. 16 announced that it will award the first annual Michael and Sheila Held Prize to Prasad Raghavendra, associate professor of electrical engineering and computer science at U.C. Berkeley.
Joining the Indian American professor as a prize recipient was 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 NAS said in a news release.
The Michael and Sheila Held 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, the NAS said.
They then work to determine the “hardness of approximation,” or whether a computer can efficiently find an approximate solution to such a problem, it added.
“Individually or in collaboration, the work of Raghavendra and Steurer suggests that among all efficient algorithms, semidefinite programming gives the best possible approximation guarantees for a host of hard optimization problems,” the academy said in its announcement.
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, it said.
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, according to the news release.
Their work yielded a potential characterization of the limits up to which efficient algorithms can approximate broad classes of “NP-hard” optimization problems, NAS said.
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 news release noted.
Raghavendra and Steurer will be presented the award April 29 during NAS’ 155th annual meeting.