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.
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 Goldwasser.
Il est chercheur et professeur d'informatique théorique au Kungliga tekniska högskolan (KTH) de Stockholm depuis 1992. Il est membre de l'Académie royale des sciences de Suède depuis 2001.
Il est par ailleurs éditeur de plusieurs journaux, dont Theory of computing.
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.
Il a reçu le prix Gödel en 1994 et 2011 et le Doctoral Dissertation Award de l'Association for Computing Machinery en 1986, ainsi que d'autres prix.
Page personnelle de Johan Håstad
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é
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.