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 en 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 GoldwasserCV présent sur la page de Johan Håstad.
Il est chercheur et professeur d'informatique théorique au Kungliga tekniska högskolan (KTH) de Stockholm depuis 1992Page concernée dans la base de données de KTH. Il est membre de l'Académie royale des sciences de Suède depuis 2001Page de Johan Håstad sur le site officiel de l'Académie royale des sciences de Suède .
Il est par ailleurs éditeur de plusieurs journaux, dont Theory of computingListe des éditeurs du journal Theory of computing, sur le site officiel..
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 , dont l'un des corollaires est que la 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.
Honneurs
Il a reçu le prix Gödel en 1994Déclaration officielle du prix Gödel 1994 et 2011Déclaration officielle du prix Gödel 2011 et le Doctoral Dissertation Award de l'Association for Computing Machinery en 1986Liste des récipiendaires des Doctoral Dissertation Award de l'université Carnegie-Mellon, ainsi que d'autres prix.
Notes et références
Liens externes
Catégorie:Mathématicien suédois du XXe siècle Catégorie:Mathématicien suédois du XXIe siècle Catégorie:Personnalité suédoise de l'informatique Catégorie:Personnalité en informatique théorique Catégorie:Naissance en novembre 1960 Catégorie:Naissance en Suède Catégorie:Étudiant de l'université de Stockholm Catégorie:Étudiant de l'université d'Uppsala Catégorie:Docteur du Massachusetts Institute of Technology Catégorie:Professeur à l'Institut royal de technologie Catégorie:Lauréat du prix Gödel Catégorie:Membre de l'Académie royale des sciences de Suède Catégorie:Membre de l'American Mathematical Society Catégorie:Participant aux Olympiades internationales de mathématiques Catégorie:Lauréat du prix Knuth