Congratulations to Sanjeev Arora, the Charles C. Fitzmorris Professor of Computer Science at Princeton, who yesterday was named the recipient of the 2011 ACM-Infosys Foundation Award in the Computing Sciences for his “contributions to computational complexity, algorithms, and optimization that have reshaped our understanding of computation.”
According to an ACM–Infosys press release:
Arora’s research revolutionized the approach to essentially unsolvable problems that have long bedeviled the computing field, the so-called NP-complete problems. These results have had implications for problems common to cryptography, computational biology, and computer vision, among other fields [more following the link].
Arora … is an ACM Fellow, and won the Gödel Prize for both 2001 and 2010, as well as the ACM Doctoral Dissertation Award in 1995. He was the founding director of the Center for Computational Intractability [at Princeton], which addresses the phenomenon that many problems seem inherently impossible to solve on current computational models.
“With his new tools and techniques, Arora has developed a fundamentally new way of thinking about how to solve problems,” said ACM President Alain Chesnais. “…In particular, his work on the PCP theorem is considered the most important development in computational complexity theory in the last 30 years. He also perceived the practical applications of his work, which has moved computational theory into the realm of real world uses.”
The full citation for Arora’s award:
Sanjeev Arora is one of the architects of the Probabilistically Checkable Proofs (PCP) theorem, which revolutionized our understanding of complexity and the approximability of NP-hard problems. He helped create new approximation algorithms for fundamental optimization problems such as the Sparsest Cuts problem and the Euclidean Travelling Salesman problem, and contributed to the development of semi-definite programming as a practical algorithmic tool. He has played a pivotal role in some of the deepest and most influential results in theoretical computer science, and continues to inspire colleagues and new generations of researchers.
Since 2007, the ACM-Infosys Foundation Award has recognized “personal contributions by young scientists and system developers to a contemporary innovation that exemplifies the greatest recent achievements in the computing field.” The award includes a $175,000 prize, funded through an endowment from the Infosys Foundation.
ACM will present Arora with the award at its annual Awards Banquet on June 16 in San Francisco, CA.
To learn more, check out the press release and award description.
(Contributed by Erwin Gianchandani, CCC Director)
