Sanjeev Arora, the Charles C. Fitzmorris Professor in Computer Science, has been elected a member of the National Academy of Sciences, one of the highest honors given to scientists in the United States.

Arora is an expert in computational complexity theory, a branch of computer science that seeks to pin down the resources required to solve computational problems. He is known for his contributions to the Probabilistic Checkable Proofs Theorem (PCP Theorem), which implies that it is possible to convert any mathematical proof into a form in which it can be checked in a few steps. This result has implications for the study of an important class of computational problems called NP-complete problems, and has had practical applications to verifying software and cryptocurrency.

Arora has also developed ways to compute near-optimal solutions to problems such as the classic “traveling salesman problem” of finding the shortest route to visiting a set of cities. He coauthored the textbook Computational Complexity: A Modern Approach; and was the founding director of the Center for Computational Intractability, a National Science Foundation-supported research hub launched at Princeton in 2008.

In recent years, Arora’s work involves theoretical machine learning, including investigating methods to identify structure in unlabeled data, such as large bodies of text.

“I’m trying to understand in a more formal way how these machine learning techniques work and why they work,” he said, noting that the math behind their operations is challenging.

Arora is currently a visiting professor in the School of Mathematics at the Institute for Advanced Study, where he is leading a program in Theoretical Machine Learning that seeks to advance fundamental knowledge of this emerging field.

Arora earned a doctorate in computer science from the University of California, Berkeley. He joined the Princeton faculty in 1994, and was appointed the Charles C. Fitzmorris Professor in Computer Science in 2011. He has twice shared the Gödel Prize for outstanding papers in theoretical computer science, in 2001 and 2011. He received the 2011 ACM-Infosys Foundation Award from the Association for Computing Machinery; he is a fellow of the ACM and of the American Academy of Arts and Sciences.

Arora is among 84 new members and 21 foreign associates elected to the National Academy of Sciences on May 1. Other Princeton faculty elected as members this year include: Orley Ashenfelter, Joseph Douglas Green 1895 Professor of Economics; Dalton Conley, Henry Putnam University Professor in Sociology; David MacMillan, James S. McDonnell Distinguished University Professor of Chemistry; Peter Ozsvath, Henry Burchard Fine Professor of Mathematics; and Virginia Zakian, Harry C. Wiess Professor in the Life Sciences and professor of molecular biology.

Faculty

  • Sanjeev Arora

Related Department

  • Computer Science

    Computer Science