Communications - June 2012

Milestones | DOI: 10.1145/2184319.2184328

An influential
Theoretician

Sanjeev Arora, winner of the 2011 ACM-Infosys Award, discusses his pivotal role in theoretical computer science.

At the very heart of comput- er 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 counterintui-tive 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,”

sanjeev Arora has been responsible for many significant advances in complexity theory during the last several decades.

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 compu-
tational complexity, algorithms, and
optimization that have helped reshape
our understanding of computation.”
Arora, 44, says he is currently work-
ing on several important open prob-
lems in approximation, such as graph
coloring, sparsest cut, and the unique
games conjecture. “I have also become
interested in bringing greater math-
ematical 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

Paul Hyman

trying to design algorithms with prov-
able bounds and performance.”
Regarding his working style, Arora
says he likes “to work on many dif-
ferent 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 teach-
ers as surely as I have been theirs.”
He is very active in the Center for
Computational Intractability at Princ-
eton, of which he is the founding di-
rector. Supported by funding from the
National Science Foundation, the cen-
ter is devoted to understanding, coping
with, and benefitting from computa-
tional 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 Hig-gins 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.”