Raghavendra NAS

U.C. Berkeley's Prasad Raghavendra was among the recipients of the inaugural Michael and Sheila Held Prize awarded by the National Academy of Sciences. The Indian American professor was honored for his work with David Steurer of ETH Zurich. (engineering.berkeley.edu photo)

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.

(0) comments

Welcome to the discussion.

Keep it Clean. Please avoid obscene, vulgar, lewd, racist or sexually-oriented language.
Don't Threaten. Threats of harming another person will not be tolerated.
Be Truthful. Don't knowingly lie about anyone or anything.
Be Nice. No racism, sexism or any sort of -ism that is degrading to another person.
Be Proactive. Use the 'Report' link on each comment to let us know of abusive posts.
Share with Us. We'd love to hear eyewitness accounts, the history behind an article.