Sanjeev Arora

Sanjeev Arora

Sanjeev Arora (* Januar 1968 in Jodhpur, Indien) ist ein US-amerikanischer 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 bis 1998 war er Sloan Research 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 Award der Association for Computing Machinery (ACM) für 2011 zugesprochen. 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, 2018 in die National Academy of Sciences gewählt. 2018 ist er Plenarsprecher auf dem ICM in Rio (Mathematics of machine learning: An introduction).

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
• mit C. Lund, R. Motwani, M. Sudan, M. Szegedy: Proof verification and the hardness of approximation problems, Journal of the ACM, Band 45, 1998, S. 501–555
• How NP got a new definition: a survey of probabilistically checkable proofs, ICM Peking 2002, Arxiv
• mit S. Rao, U. Vazirani: Expander flows, geometric embeddings and graph partitioning, Journal of the ACM (JACM), Band 56, 2009, S. 5
• mit Prashant Doshi: A Survey of Inverse Reinforcement Learning: Challenges, Methods and Progress, Arxiv 2018

Literatur

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

Weblinks

• Webseite in Princeton (englisch)
• Videos von und über Sanjeev Arora im AV-Portal der Technischen Informationsbibliothek