Johan Håstad
# Johan Håstad

Johan Torkel Håstad (* 19. November 1960) ist ein schwedischer Informatiker.

Hastad erhielt 1977 die Goldmedaille auf der Internationalen Mathematikolympiade. Er studierte Mathematik an der Universität Stockholm (Vordiplom, Högskoleexamen 1981) und der Universität Uppsala, wo er 1984 sein Diplom (Licenciat) in Mathematik erwarb. 1986 wurde er am Massachusetts Institute of Technology bei Shafrira Goldwasser promoviert mit einer Arbeit, die den ACM Doctoral Dissertation Award bekam. Er ist seit 1988 Professor für Informatik an der Königlich Technischen Hochschule in Stockholm (ab 1992 in einer vollen Professur). 2000/2001 war er Mitglied des Institute for Advanced Study.

Hastad befasst sich mit Komplexitätstheorie. Insbesondere fand er in seiner Dissertation neue untere Grenzen für die Schaltkreis-Komplexität Boolescher Funktionen. Er beschäftigte sich auch mit Kryptographie und erfand einen Angriff auf das RSA-Kryptosystem. 1989 war er Mitautor der Veröffentlichung des HJLS-Algorithmus zur Berechnung von Ganzzahlbeziehungen zwischen kommensurablen reellen Zahlen.

1994 und 2011 erhielt er den Gödel-Preis, 1999 den Göran Gustafsson Preis in Mathematik und 2018 den Knuth-Preis. 1998 war Håstad Invited Speaker auf dem ICM in Berlin (On approximating NP-hard optimization problems). 2004 hielt er einen der Plenarvorträge auf dem Europäischen Mathematikerkongress (Efficient computational proofs and inapproximability). Seit 2001 ist er Mitglied der Königlich Schwedischen Akademie der Wissenschaften und seit 2007 der Academia Europaea. Er ist Fellow der American Mathematical Society und seit 2018 der Association for Computing Machinery.

