Sanjeev Arora

Sanjeev Arora

Sanjeev Arora (* 1968 in Indien) ist ein indischer Informatiker.

Inhaltsverzeichnis

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 mit Joseph S. B. Mitchell für eine polynomialzeitliche Näherung für das euklidische Problem des Handlungsreisenden.

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

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Arora — ist der Familienname folgender Personen: Amrita Arora (* 1981), indische Filmschauspielerin Malaika Arora Khan (* 1973), indisches Model und Schauspielerin Sanjeev Arora (* 1968), indischer Informatiker Der Name Arora bezeichnet einen freien… …   Deutsch Wikipedia

  • Prix Gödel — Nommé en l honneur du logicien Kurt Gödel, le prix Gödel a été créé en 1992 par l European Association for Theoretical Computer Science (EATCS), l Association for Computing Machinery (ACM) et le groupe de l ACM sur l algorithmique et la théorie… …   Wikipédia en Français

  • PCP theorem — In computational complexity theory, the PCP theorem states that every decision problem in the NP complexity class has probabilistically checkable proofs (proofs that can be checked by a randomized algorithm) of constant query complexity and… …   Wikipedia

  • Премия Гёделя — (англ. Gödel Prize)  премия в области теории вычислительных систем имени Курта Гёделя, вручаемая ежегодно организациями ACM SIGACT (Special Interest Group on Algorithms and Computation Theory) и EATCS (European Association for… …   Википедия

  • Interactive proof system — In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties. The parties, the verifier and the prover, interact by exchanging messages in order to… …   Wikipedia

  • PCP-Theorem — Das PCP Theorem ist ein Satz aus der theoretischen Informatik (Komplexitätstheorie). Es beruht auf dem Konzept des zufällig verifizierbaren Beweises eines mathematischen Satzes (probabilistic checkable proof, PCP), der wiederum auf das Konzept… …   Deutsch Wikipedia

  • Géraud Sénizergues — est professeur d informatique à l Université de Bordeaux et membre du Laboratoire bordelais de recherche en informatique. Récipiendaire du Prix Gödel en 2002 pour avoir démontré la décidabilité de l égalité des langages reconnus par des automates …   Wikipédia en Français

  • Johan Håstad — Johan Håstad, né en 1960, est un informaticien théorique suédois connu particulièrement pour son travail sur la complexité algorithmique. Il a reçu le Prix Gödel en 1994 et 2011 et le Doctoral Dissertation Award de l Association for Computing… …   Wikipédia en Français

  • László Lovász — (9 mars 1948, à Budapest ) est un mathématicien connu pour ses travaux en combinatoire et dans la théorie des graphes. Sommaire …   Wikipédia en Français

  • Manindra Agrawal — (hindi : मणीन्द्र अग्रवाल) (20 mai 1966 à Allâhâbâd ) est un mathématicien indien et professeur à l Institut indien de technologie de Kanpur. C est un des auteurs du test de primalité AKS. Lien externe Page personnelle (en) …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”