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, National Academy of Sciences, 2018; Member, American Academy of Arts and Sciences, 2015; Fulkerson Prize, 2012; Gödel Prize, 2010 and 2001; ACM Fellow, 2009
Sanjeev Arora is the Charles C. Fitzmorris Professor in Computer Science. He joined Princeton in 1994 after earning his PhD from the UC Berkeley. Professor Arora won the Fulkerson Prize in Discrete Mathematics in 2012, the ACM Prize in Computing in 2011, EATCS-SIGACT Gödel Prize (cowinner) twice, in 2001 and 2010, the Packard Fellowship (1997) and the ACM Doctoral Dissertation Award (1995). He was a plenary lecturer at International Congress of Mathematicians in 2018. He was appointed a Simons Foundation investigator in 2012, and also won best paper awards in IEEE FOCS 2010 and ACM STOC 2004. Professor Arora was the founding director and lead PI at the NSF-funded Center for Computational Intractability in 2008-13.
See Google Scholar for new work
- “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.)
- For new papers please see the Google Scholar Page.