Sanjeev Arora, a professor of computer science, has been awarded the 2011 ACM-Infosys Foundation Award for work that brings new understanding to the ability to compute approximate solutions to a famous group of mathematical problems. These problems, called NP-complete, are considered essentially insolvable by mathematicians. Arora has explored the use of approximation as a possible approach to these problems, positing that a near-optimal solution may be as useful in practice as an optimal solution.
Arora, the Charles C. Fitzmorris Professor in Computer Science, was one of a group of researchers that developed the Probabilistic Checkable Proofs theorem (PCP Theorem), a breakthrough in understanding the class of NP-complete problems as well as a fundamental issue of computing called the P versus NP question.
Arora also helped develop tools for using approximation to approach difficult problems such as the Euclidean Traveling Salesman problem, which seeks the shortest route for a salesman travelling through a group of cities and only visiting each once.
The P versus NP question suggests that problems such as Traveling Salesman do not have any efficient solution methods. In its simplest terms, the P versus NP problem asks: if a computer can quickly verify an answer to a problem, does it follow that the computer must also be able to quickly solve the problem?
In the case of the Traveling Salesman, computing the most efficient route among a large number of cities seems very difficult because of the astronomical number of possible routes. But checking the cost of a given tour, or verifying that it doesn’t duplicate a visit to any city, is easy.
Researchers such as Arora wanted to know whether approximation could offer a practical alternative to computing optimum solutions to problems such as the Traveling Salesman. However, the PCP theorem demonstrated that reaching an approximate solution for many of these problems would not be any easier than finding an optimum solution.
“People were failing to develop new tools to compute approximate solutions,” Arora said, “and the PCP Theorem and subsequent results finally explained for many problems why progress had been stalled.”
More recently, Arora and his colleagues have used the difficulty of approximation to explain why certain financial derivatives (such as the ones implicated in the financial crash of 2008) are too complex. His most recent work concerns machine learning, which frequently involves extremely difficult computational problems. He is trying to use approximation and other notions to offer workable solutions for researchers.
“Approximation is one approach, but there are other things you can do,” he said. “Sometimes a very slight twist in the definition of a problem can make it vastly easier. You are working with a model of reality to begin with, so a slight change of the model may be inconsequential in terms of accuracy, yet hugely consequential in terms of computational difficulty.”
Arora received his doctorate in computer science from Berkeley, and joined the faculty at Princeton in 1994. He was appointed as the Charles C. Fitzmorris Professor in Computer Science in 2011. A fellow of the Association for Computing Machinery, Arora was awarded the G√∂del Prize in 2001 and 2010, and the Princeton University Engineering Council’s teaching award in 2008. He was the founding director of the Center for Computational Intractability, a joint effort of Princeton, the Institute for Advanced Study, Rutgers and New York University, that examines problems that seem impossible to solve on current computer models.
The Association for Computing Machinery is the world’s largest educational and scientific computing society. The ACM-Infosys Foundation Award, which includes a prize of $175,000, recognizes contributions by young scientists and system developers to innovation that exemplifies the greatest recent achievements in computing.
