Sanjeev Arora

Sanjeev Arora (* Januar 1968 in Jodhpur<ref name="Bio">Gemäß den biographischen Angaben auf seiner Homepage http://www.cs.princeton.edu/~arora/bio.html</ref>, Indien) ist ein US-amerikanischer<ref name="Bio" /> Informatiker indischer Herkunft.

Leben

Arora (der in Indien in den landesweiten Aufnahmeprüfungen für das Indian Institute of Technology 1986 als Bester abschnitt) studierte Mathematik und Informatik am Massachusetts Institute of Technology (Bachelor 1990) und wurde 1994 bei Umesh Vazirani an der University of California, Berkeley promoviert. Für seine Dissertation (Probabilistic checking of proofs and the hardness of approximation problems) über probabilistisch verifizierbare Beweise (probabilistically checkable proofs, PCP) mit Beweis des PCP-Theorems erhielt er den ACM Doctoral Dissertation Award. 1994 wurde er Assistant Professor, 1999 Associate Professor und 2003 Professor für Informatik an der Princeton University. Er war Gastwissenschaftler bei Microsoft Research (2006/07) und am Weizmann-Institut.

1996 war er Sloan Fellow. 2001 erhielt er mit anderen den Gödel-Preis für das PCP-Theorem und 2010 nochmals mit Joseph S. B. Mitchell für eine polynomialzeitliche Näherung für das euklidische Problem des Handlungsreisenden. Arora erhielt den ACM-Infosys Foundation Award in the Computing Sciences der Association for Computing Machinery (ACM) für 2011 zugesprochen.<ref>Princeton Computer Scientist Sanjeev Arora Honored for Breakthroughs that Have Advanced the Power of Computing bei der Association for Computing Machinery (acm.org); abgerufen am 29. März 2012</ref> 2002 war er Invited Speaker auf dem Internationalen Mathematikerkongress in Peking (How NP got a new definition: a survey of probabilistic checkable proofs). 2012 wurde er mit dem Fulkerson-Preis ausgezeichnet, 2015 in die American Academy of Arts and Sciences gewählt.

Zu seinen Doktoranden zählt Subhash Khot.

Schriften

• Mit Boaz Barak: Computational Complexity, Cambridge University Press 2009
• Mit Shmuel Safra: Probabilistic checking of proofs: A new characterization of NP, Journal of the ACM, Band 45, 1998, S. 70–122
• Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM, Band 45, 1998, S. 753–782

Literatur

• Ryan O'Donnel, Venkatesan Guruswami: History of the PCP Theorem (PDF; 599 kB)

Weblinks

• Webseite in Princeton (englisch)

Fußnoten

<references />