Sanjeev Arora

Sanjeev Arora (* January 1968 in Jodhpur, India) is an American computer scientist of Indian origin.

Life

Arora ( the section as the best in India in the national entrance examinations for the Indian Institute of Technology, 1986) studied mathematics and computer science at the Massachusetts Institute of Technology (Bachelor 1990) and received his doctorate at Umesh Vazirani at the University of California, Berkeley in 1994. For his dissertation ( Probabilistic checking of proofs and the hardness of approximation problems ) on probabilistically verifiable proofs ( probabilistically checkable proofs, PCP) with proof of the PCP theorem, he received the ACM Doctoral Dissertation Award. In 1994 he was Assistant Professor, in 1999 Associate Professor and in 2003 Professor of computer science at Princeton University. He was a visiting scientist at Microsoft Research (2006/ 07) and at the Weizmann Institute.

In 1996 he was Sloan Fellow. In 2001 he received with other Gödel Prize for the PCP theorem, and once again in 2010 with Joseph SB Mitchell for a polynomialzeitliche approximation for the Euclidean traveling salesman problem ends. Arora received the ACM -Infosys Foundation Award in the Computing Sciences of the Association for Computing Machinery (ACM ) awarded in 2011. In 2002 he was invited speaker at the International Congress of Mathematicians in Beijing ( How NP got a new definition: a survey of probabilistic checkable proofs ). In 2012 he was awarded the Fulkerson Prize.

Writings

  • With Boaz Barak, Computational Complexity, Cambridge University Press 2009
  • With Shmuel Safra: Probabilistic checking of proofs: A new characterization of NP, Journal of the ACM, Volume 45, 1998, pp. 70-122
  • Polynomial -time approximation schemes for Euclidean TSP and other Geometric problem, Journal of the ACM, Volume 45, 1998, pp. 753-782
Indian Institutes of Technology PCP-Theorem Weizmann Institute of Science Sloan Fellows Joseph S. B. Mitchell Integrated Authority File
706040
de