An Influential Theoretician

Princeton University Professor Sanjeev Arora — Sanjeev Arora has been responsible for many significant advances in complexity theory during the last several decades.

At the very heart of computer science is the question of which problems, such as the P versus NP question, can be solved efficiently.

Sanjeev Arora, the Charles C. Fitzmorris Professor of Computer Science at Princeton University, has been at the center of major developments in complexity theory during the last several decades, first gaining fame for his contributions toward proving the PCP Theorem in 1992 and the hardness of computing approximate solutions to NP-hard optimization problems.

The PCP Theorem states that every mathematical proof, of any length, can be efficiently converted into a special format in which correctness can be verified with extremely high probability by reading only a few random bits of the proof. This strikingly counterintuitive statement goes against the normal understanding of proofs where a single small error can ruin correctness. How can a small random sample find all such possible bugs? Technically, the proof of the PCP Theorem is a tour de force, making this one of the most difficult theorems in computer science.

Since then Arora has also contributed fundamental new algorithms to compute approximate solutions to the traveling salesman problem, as well as to graph partitioning problems. And his textbook, Computational Complexity, co-authored with Boaz Barak, has became a standard text in many universities for advanced undergraduate or introductory graduate courses on this central area of theoretical computer science.

“We are recognizing the contributions of one of the century’s greatest theoreticians, who has played a pivotal role in some of the deepest and most influential results in theoretical computer science and its applications,” says Henry Kautz, chair of the department of computer science at the University of Rochester and chair of the 2011 ACM-Infosys Foundation Award in the Computing Sciences.

The 2011 ACM-Infosys Award, which carries a $175,000 prize and recognizes work by young computer scientists and systems developers, was awarded to Arora for “contributions to computational complexity, algorithms, and optimization that have helped reshape our understanding of computation.”

Arora, 44, says he is currently working on several important open problems in approximation, such as graph coloring, sparsest cut, and the unique games conjecture. “I have also become interested in bringing greater mathematical rigor to machine learning,” he says. “Currently, that field relies on heuristic approaches—i.e., algorithms whose performance we are currently unable to prove mathematically. I am trying to design algorithms with provable bounds and performance.”

Regarding his working style, Arora says he likes “to work on many different areas of theoretical computer science and explore new ideas and research topics. Fresh insights often arise from ideas jumping from one area to another.”

While the ACM-Infosys Award is for research accomplishments, Arora’s Princeton colleagues describe him as “a great mentor and advisor, with many students and postdocs, some already leaders in their own right.”

Arora expresses gratitude toward the “students over the years who have been willing to accompany me on new explorations. They have been my teachers as surely as I have been theirs.”

He is very active in the Center for Computational Intractability at Princeton, of which he is the founding director. Supported by funding from the National Science Foundation, the center is devoted to understanding, coping with, and benefitting from computational intractability.

“We are hard-pressed to think of another theoretical computer scientist under 50 whose work has exhibited the sustained depth over a couple of decades, and who has had such a large impact on so many areas,” says Bernard Chazelle, the Eugene Higgins Professor of Computer Science at Princeton.

Arora hails from Kota, India, and moved to the U.S. at age 20. “It is fair to say that growing up in a small city in India, I could not have imagined the fun, interesting, and satisfying life—personal and professional—that I have ended up having.”