Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

Title/Position

Charles C. Fitzmorris Professor

Degree

Ph.D., University of California, Berkeley, 1994

arora (@cs.princeton.edu)
(609) 258-3869
407 Computer Science

Homepage

**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); Goedel Prize, (2010 and 2010); ACM Fellow, (2009)

**Research Areas:**

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.)