Prasad Raghavendra wins inaugural NAS Michael and Sheila Held Prize

CS Associate Prof. Prasad Raghavendra has won the inaugural Michael and Sheila Held Prize.  The award, sponsored by the National Academy of Sciences (NAS), 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.  Raghavendra and co-recipient David Steurer are being recognized “For a body of work which revolutionizes our understanding of optimization and complexity. It better explains the exact limits to efficient approximation of NP-hard problems. It provides better understanding of the computational assumptions underlying hardness of approximation. And it develops a structure theory of linear and semi-definite programming and their hierarchies, which leads to new algorithms and new lower bounds.”  The prize comes with $100,000 and will be presented at the NAS annual meeting in April.