Johana Håstada

Johana Håstada
Urodzić się	( 19.11.1960 ) 19 listopada 1960
Narodowość	szwedzki
Alma Mater	Instytut Technologii w Massachusetts Uniwersytet w Uppsali Uniwersytet Sztokholmski
Nagrody	Złoty medal IMO (1977) Nagroda za rozprawę doktorską ACM (1985) Nagroda Gödla (1994, 2011) Nagroda Knutha (2018)
Kariera naukowa
Pola	Informatyka
Instytucje	KTH Królewski Instytut Technologiczny
Doradca doktorski	Szafirę Goldwasser

Johan Torkel Håstad ( szwedzka wymowa: [ˈjûːan ˈhǒːsta] ; ur. 19 listopada 1960) to szwedzki informatyk teoretyczny najbardziej znany ze swojej pracy nad teorią złożoności obliczeniowej . Był laureatem Nagrody Gödla w 1994 i 2011 oraz Nagrody Doktorskiej ACM w 1986, między innymi nagrodami. Był profesorem informatyki teoretycznej w KTH Royal Institute of Technology w Sztokholmie , Szwecja od 1988 r., profesorem zwyczajnym został w 1992 r. Od 2001 r. jest członkiem Królewskiej Szwedzkiej Akademii Nauk .

Uzyskał tytuł licencjata z matematyki na Uniwersytecie Sztokholmskim w 1981 r., tytuł magistra matematyki na Uniwersytecie w Uppsali w 1984 r., a doktorat. w matematyce z MIT w 1986 roku.

Teza Håstada i nagroda Gödla z 1994 r. Dotyczyły jego pracy nad dolnymi granicami wielkości obwodów boolowskich o stałej głębokości dla funkcji parzystości . Po tym, jak Andrew Yao udowodnił, że takie obwody wymagają rozmiaru wykładniczego, Håstad udowodnił prawie optymalne dolne granice niezbędnego rozmiaru poprzez swój lemat o przełączaniu , który stał się ważnym narzędziem technicznym w złożoności obwodów z zastosowaniami do uczenia się , hierarchii adresów IP i systemów dowodowych .

Otrzymał również Nagrodę Gödla 2011 za pracę nad optymalnymi wynikami nieprzybliżenia. W szczególności ulepszył twierdzenie PCP (które zdobyło tę samą nagrodę w 2001 r.), aby dać probabilistyczny weryfikator problemów NP , który czyta tylko trzy bity. Ponadto wykorzystał te wyniki, aby udowodnić wyniki przybliżenia twardości .

W 1998 Håstad był zaproszonym mówcą Międzynarodowego Kongresu Matematyków w Berlinie. W 1999 był wykładowcą Erdősa na Uniwersytecie Hebrajskim w Jerozolimie . W 2012 roku został członkiem Amerykańskiego Towarzystwa Matematycznego . Został wybrany na członka ACM w 2018 roku za „wkład w złożoność obwodów, przybliżenie i nieprzybliżenie oraz podstawy pseudolosowości”.

W 2018 roku otrzymał nagrodę Knutha „za długi i trwały rekord przełomowych przełomów 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”.

Linki zewnętrzne

• Strona domowa Johana Håstada
• Wyniki Johana Håstada na Międzynarodowej Olimpiadzie Matematycznej