Johan Håstad

Johan Håstad
Geboren 19. November 1960 (Alter 61)
Staatsangehörigkeit Schweden
Alma Mater
Auszeichnungen
Wissenschaftliche Karriere
Felder Informatik
Institutionen KTH Royal Institute of Technology
Doktorand Shafrira Goldwasser[1]

Johan Torkel Håstad (Schwedische Aussprache:[ˈJûːan ˈhǒːsta]; geboren am 19. November 1960) ist ein Schwedisch Theoretischer Informatiker am bekanntesten für seine Arbeit an Computerkomplexitätstheorie. Er war der Empfänger der Gödel -Preis in den Jahren 1994 und 2011 und der ACM Doktorarbeit im Jahr 1986 unter anderem Preise. Er war ein Professor in Theoretische Informatik bei KTH Royal Institute of Technology in Stockholm, Schweden seit 1988, 1992 voller Professor. Er ist Mitglied der Royal Swedish Academy of Sciences seit 2001.

Er erhielt seine B.S. in Mathematik bei Stockholmer Universität 1981 seine FRAU. in Mathematik bei Uppsala Universität im Jahr 1984 und seines Ph.D. in Mathematik von MIT 1986.[2]

Håstads These und 1994 Gödel -Preis besorgt seine Arbeit an Untergrenzen auf der Größe der Konstantentiefe Boolesche Schaltungen für die Paritätsfunktion. Nach Andrew Yao bewies, dass solche Schaltkreise eine exponentielle Größe erfordern, und Håstad erwies sich als nahezu optimale Untergrenze für die erforderliche Größe durch seine Lemma wechseln, was zu einem wichtigen technischen Instrument wurde in Komplexität der Schaltung mit Anwendungen auf Lernfähigkeit, das IP Hierarchie und Proofsysteme.[3]

Er erhielt auch den Gödel -Preis von 2011 für seine Arbeit zu optimalen unangemessenen Ergebnissen. Insbesondere verbesserte er das PCP -Theorem (der 2001 den gleichen Preis gewann), um einen probabilistischen Prüfer für zu geben Np Probleme, die nur drei Teile lesen. Darüber hinaus verwendete er diese Ergebnisse, um die Ergebnisse zu beweisen Annäherungshärte.[4]

1998 war Håstad ein eingeladener Redner der Internationaler Kongress der Mathematiker in Berlin.[5] 1999 war er ein ERDős Dozent Bei der Hebräische Universität von Jerusalem. 2012 wurde er Fellow der American Mathematical Society.[6] Er wurde als als gewählt ACM Fellow im Jahr 2018 für "Beiträge zur Komplexität der Schaltung, der Annäherung und Unangemessenheit sowie der Grundlagen der Pseudorandomness".[7]

2018 erhielt er das Knuth -Preis "Für seine langen und anhaltenden Aufzeichnung von Meilensteinbräumen auf den Fundamenten der Informatik mit enormen Auswirkungen auf viele Bereiche, einschließlich Optimierung, Kryptographie, paralleles Computing und Komplexitätstheorie."[8]

Verweise

  1. ^ Johan Håstad Bei der Mathematik Genealogie -Projekt
  2. ^ Simons Institute: Johan Håstad, abgerufen 2018-04-05.
  3. ^ 1994 Gödel Prize, abgerufen 2018-04-05
  4. ^ 2011 Gödel Prize, abgerufen 2018-04-05
  5. ^ Håstad, Johan (1998). "Bei der Approximierung von NP-HART-Optimierungsproblemen". Dokument. Mathematik. (Bielefeld) Extra Vol. ICM Berlin, 1998, vol. III. S. 441–450.
  6. ^ Liste der Stipendiaten der American Mathematical Society, abgerufen 2013-01-19.
  7. ^ 2018 ACM -Stipendiaten, die für entscheidende Erfolge geehrt wurden, die das digitale Zeitalter stützen, Verband für Rechenmaschinen, 5. Dezember 2018
  8. ^ Der KNUTH -Preis 2018 wird an Johan Håstad vergeben (PDF), ACM, 6. August 2018

Externe Links