Quick links

Sanjeev Arora

Photo of Sanjeev Arora
Charles C. Fitzmorris Professor
Ph.D., University of California, Berkeley, 1994
arora  (@cs.princeton.edu) (609) 258-3869 407 Computer Science


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:

Short Bio

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.

Selected Publications

  • “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.)
Follow us: Facebook Twitter Linkedin