Johan Håstad - Johan Håstad
Johan Håstad | |
|---|---|
| Urodzić się | 19 listopada 1960 |
| Narodowość | Szwecja |
| Alma Mater | |
| Nagrody | |
| Kariera naukowa | |
| Pola | Informatyka |
| Instytucje | Królewski Instytut Technologiczny KTH |
| Doradca doktorski | Shafrira Goldwasser |
Johan Torkel Håstad ( szwedzka wymowa: [ˈjûːan ˈhǒːsta] ; ur. 19 listopada 1960) to szwedzki teoretyk informatyk najbardziej znany ze swojej pracy nad teorią złożoności obliczeniowej . Był laureatem m.in. nagrody Gödla w 1994 i 2011 roku oraz nagrody doktorskiej ACM w 1986 roku. Był profesorem w teoretycznej informatyki w KTH Royal Institute of Technology w Sztokholmie , w Szwecji od 1988 roku, stając się profesorem w roku 1992. Jest członkiem Królewskiej Szwedzkiej Akademii Nauk od 2001 roku.
Uzyskał tytuł licencjata z matematyki na Uniwersytecie Sztokholmskim w 1981 r., tytuł magistra matematyki na Uniwersytecie w Uppsali w 1984 r. oraz doktorat. w matematyce z MIT w 1986 roku.
Teza Håstada i Nagroda Gödla z 1994 r. dotyczyły jego pracy nad dolnymi ograniczeniami wielkości obwodów logicznych o stałej głębokości dla funkcji parzystości . Po tym, jak Andrew Yao udowodnił, że takie obwody wymagają wykładniczego rozmiaru, Håstad udowodnił prawie optymalne dolne granice niezbędnego rozmiaru dzięki lematowi przełączania , który stał się ważnym narzędziem technicznym w złożoności obwodów z aplikacjami do uczenia się , hierarchią IP i systemami dowodowymi .
Otrzymał również Nagrodę Gödla 2011 za pracę nad optymalnymi wynikami nieprzybliżeniowości. W szczególności poprawił twierdzenie PCP (które zdobyło tę samą nagrodę w 2001 r.), aby dać probabilistyczny weryfikator dla problemów NP , który odczytuje tylko trzy bity. Następnie wykorzystał te wyniki do udowodnienia wyników w zakresie twardości aproksymacji .
W 1998 roku Håstad był zaproszonym przewodniczącym Międzynarodowego Kongresu Matematyków w Berlinie. W 1999 roku był wykładowcą Erdősa na Uniwersytecie Hebrajskim w Jerozolimie . W 2012 został stypendystą Amerykańskiego Towarzystwa Matematycznego . Został wybrany na członka ACM Fellow w 2018 roku za „wkład w złożoność obwodów, przybliżanie i nieprzybliżalność oraz podstawy pseudolosowości”.
W 2018 roku otrzymał Nagrodę Knutha „za długi i trwały zapis przełomowych osiągnięć w podstawach informatyki, mających ogromny wpływ na wiele dziedzin, w tym optymalizację, kryptografię, obliczenia równoległe i teorię złożoności”.