Interests: Uses of randomness in complexity theory and algorithms; Efficient algorithms for finding approximate solutions to NP-hard problems (or proving that they don't exist); Cryptography.
Member, American Academy of Arts and Sciences (2015); Fulkerson Prize, 2012; Goedel Prize, 2010 and 2010; ACM Fellow, 2009
Sanjeev Arora is the Charles C. Fitzmorris Professor in Computer Science. He joined Princeton in 1994 after earning his doctorate from the University of California, Berkeley. He was a visiting professor at the Weizmann Institute in 2007, a visiting researcher at Microsoft in 2006-07, and a visiting associate professor at Berkeley during 2001-02. Professor Arora’s honors include the D.R. Fulkerson Prize in Discrete Mathematics (awarded by the American Mathematical Society and Math Optimization Society) in 2012, the ACM-Infosys Foundation Award in the Computing Sciences in the same year, the Best paper award from IEEE Foundations of Computer Science in 2010, and the EATCS-SIGACT Gödel Prize (cowinner), also in 2010. He was appointed a Simons Foundation investigator in 2012, and was elected an ACM fellow in 2009. Professor Arora was the founding director and lead PI at the Center for Computational Intractability in 2008, a project funded partly by an NSF Expeditions in Computing grant.
- “Computational Complexity: A Modern Approach. “ S. Arora and B. Barak, Cambridge University Press, 2009. (book)
- “Proof verification and intractability of approximation problems.” “S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. JACM 45(3):501–555, 1998. (Prelim. Version IEEE FOCS 1992.)
- “Probabilistic Checking of Proofs: A New Characterization of NP.” S. Arora and S. Safra. Journal of the ACM 45(1):70–122, 1998. (Prelim. Version IEEE FOCS 1992.)
- “Expander flows, geometric embeddings, and graph partitioning.” S. Arora, S. Rao, and U. Vazirani. JACM 2008. (Prelim version ACM STOC, 2004.)
- “The hardness of approx.imate optima in lattices, codes, and systems of linear equations.” S. Arora, L. Babai, J. Stern, and Z. Sweedyk. JCSS, 54(2):317-331, 1997. (Prelim. version in IEEE FOCS 1993.)