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 have been chosen as the winners of the first Michael and Sheila Held prize. They were chosen “for a body of work which revolutionizes our understanding of optimization and complexity in computer science” announces a press release from the academy.
The duo will be awarded a cash prize of $ 100,000 during the Academy’s 155th annual meeting to be held on 29 April 2018.
Raghavendra and Steurer work on computational complexity--problems that are classified as hard and considered impossible for a computer to completely solve within a reasonable time frame. Their work helps determine if a computer can find an approximate solution to such problems. The duo showed that compared to other algorithms, semidefinite programming (SDP)—a type of optimization of complexity problems, gives the best possible approximation for several of the hard optimization problems. According to the press release from the academy,“the awardees have advanced a theoretical framework for SDP, which has led to new algorithms and a deeper understanding of SDP’s limitations.”
The Michael and Sheila Held prize presented for the first time this year, will be awarded annually to ‘honour 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 was established in 2017 by the bequest of Michael and Sheila Held.
The National Academy of Sciences (NAS) is a private, non-profit society of distinguished scholars, based in USA. The scientists are elected by their peers to membership in the NAS for outstanding contributions to research. The NAS, along with the National Academy of Engineering and National Academy of Medicine --provides science, technology, and health policy advice to the federal government and other organizations.