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 obtenu deux fois le prix Gödel et une fois le prix Knuth .
Biographie
Il a reçu son Bachelor of Science mathématiques à l'université de Stockholm en 1981 , son master à l'université d'Uppsala en 1984 et son Ph.D. en mathématiques du Massachusetts Institute of Technology en 1986 , sous la direction de Shafi Goldwasser [ 1] , [ 2]
Il est chercheur et professeur d'informatique théorique au Kungliga tekniska högskolan (KTH) de Stockholm depuis 1992 [ 3] Académie royale des sciences de Suède depuis 2001 [ 4]
Il est par ailleurs éditeur de plusieurs journaux, dont Theory of computing [ 5]
Travaux
La thèse de Johan Håstad avait pour objet des bornes inférieures sur des problèmes de circuits booléens . Dans ce domaine, il est connu pour avoir introduit le switching lemma (en) [ 6] fonction parité n'est pas dans la classe de complexité appelée AC0 . Ces travaux lui ont permis d'obtenir son premier prix Gödel. Il est aussi connu pour ses travaux sur l'inapproximabilité de certains problèmes algorithmiques , basés sur le théorème PCP .
Il a aussi été l'auteur de l'une de premières attaques du chiffrement RSA en 1985[ 7]
Honneurs
Il a reçu le prix Gödel en 1994 [ 8] 2011 [ 9] Doctoral Dissertation Award de l'Association for Computing Machinery en 1986 [ 10]
↑ CV présent sur la page de Johan Håstad ↑ (en) « Johan Håstad le site du Mathematics Genealogy Project ↑ Page concernée dans la base de données de KTH ↑ Page de Johan Håstad sur le site officiel de l'Académie royale des sciences de Suède ↑ Liste des éditeurs du journal Theory of computing , sur le site officiel.↑
Johan Håstad, « Almost Optimal Lower Bounds for Small Depth Circuits » , dans Proceedings of the 18th Annual {ACM} Symposium on Theory of Computing,
May 28-30, 1986, Berkeley, California, {USA} , 1986 (DOI 10.1145/12130.12132 , p. 6-20
↑
Johan Håstad , « On using RSA with low exponent in a public key network » , dans Advances in Cryptology – CRYPTO’85, Lecture Notes in Computer Science , vol. 218, Springer, p. 403-408
↑ Déclaration officielle du prix Gödel 1994 ↑ Déclaration officielle du prix Gödel 2011 ↑ Liste des récipiendaires des Doctoral Dissertation Award de l'université Carnegie-Mellon
Liens externes
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
Samuel Fiorini
Serge Massar
Sebastian Pokutta
Hans Raj Tiwary
Ronald de Wolf Thomas Rothvoss
