ACM-Infosys Foundation Award Goes to Architect of New Approaches for Hard-to-Solve Computational Problems

Share Article

Princeton computer scientist Sanjeev Arora's research revolutionized the approach to 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.

2011 ACM-Infosys Foundation Award Recipient Sanjeev Arora of Princeton University

Arora perceived the practical applications of his work, which have moved computational theory into the realm of real world uses.

ACM (the Association for Computing Machinery) and Infosys Foundation announced today that Sanjeev Arora, 44, of Princeton University, is the recipient of the 2011 ACM-Infosys Foundation Award in the Computing Sciences for his innovative approaches to problem solving. 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.

The ACM-Infosys Foundation Award, established in August 2007, recognizes personal contributions by young scientists and system developers to a contemporary innovation that exemplifies the greatest recent achievements in the computing field. Financial support for the award, which was increased this year to $175,000, is provided by an endowment from the Infosys Foundation.

"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. "He also demonstrated that when we can’t solve these problems, we understand why this is the case. 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."

Arora’s work provides key theoretical concepts for distinguishing between problems that can be approximated efficiently and those that cannot. He played a key role in the development of probabilistically checkable proofs (PCP) that resulted in the PCP theorem, which leads to designs for more secure use of agents common in cloud computing, and for studying human allergic reactions. He also contributed new ways to find approximate solutions to problems. His efforts have inspired other computer theory researchers and helped raise the level of funding for theoretical computer science.

"Infosys is proud to partner with ACM to recognize Dr. Arora’s contributions in computing. His research on approximation algorithms, and the tools he has developed, can help speed the pace of innovation, which is critical in today’s increasingly fast-paced global economy," said S. D. Shibulal, CEO and Managing Director of Infosys. "The ACM-Infosys Foundation Award underscores our ongoing commitment to support advances in computing sciences, and encourage groundbreaking uses of technology to help build tomorrow’s enterprises."

The Charles Fitzmorris Professor of Computer Science at Princeton, Arora was a co-winner of both the 2001 and 2010 Gödel Prize, an award sponsored jointly by the European Association for Theoretical Computer Science (EATCS) and the ACM Special Interest Group on Algorithms and Computation Theory (ACM SIGACT). He was named an ACM Fellow in 2008, and a co-winner of the ACM Doctoral Dissertation Award in 1995. He coauthored Computational Complexity: A Modern Approach with Boaz Barak, which has become a popular text in higher education. A graduate of the Massachusetts Institute of Technology with an S.B. degree in Mathematics and Computer Science, Arora earned a Ph.D. degree in Computer Science from the University of California, Berkeley. He also attended the Indian Institute of Technology at Kanpur for two years before moving to the U.S.

ACM will present the ACM˗Infosys Foundation Award at its annual Awards Banquet on June 16, in San Francisco, CA.

Share article on social media or email:

View article via:

Pdf Print

Contact Author

Virginia Gold
ACM
212-626-0505
Email >
Visit website