Johan Håstad

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Johan Håstad, né en 1960, est un informaticien théorique suédois connu particulièrement pour son travail sur la complexité algorithmique.

Biographie[modifier | modifier le code]

Il a reçu le prix Gödel[1],[2] en 1994[3] et 2011[4] et le Doctoral Dissertation Award de l'Association for Computing Machinery en 1986[5], ainsi que d'autres prix. Il est chercheur et professeur d'informatique théorique au Kungliga tekniska högskolan (KTH) de Stockholm depuis 1992[6]. Il est membre de l'Académie royale des sciences de Suède depuis 2001[7].

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 [8],[9].

Travaux[modifier | modifier le code]

La thèse de Johan Håstad avait pour objet des bornes inférieures sur des problèmes de circuits booléens. Ces travaux lui ont permis d'obtenir son premier prix Gödel. Le second récompensait des travaux sur l'inapproximabilité de certains problèmes.

Notes et références[modifier | modifier le code]

  1. Site officiel du Prix Gödel
  2. Un prix reconnu comme prestigieux par le CNRS, cf. Le rapport de 2010, p. 34
  3. Déclaration officielle du prix Gödel 1994
  4. Déclaration officielle du prix Gödel 2011
  5. Liste des récipiendaires des Doctoral Dissertation Award de l'université Carnegie-Mellon
  6. Page concernée dans la base de donnée de KTH
  7. Page de Johan Håstad sur le site officiel de l'Académie royale des sciences de Suède
  8. CV présent sur la page de Johan Håstad
  9. (en) Johan Håstad sur le site du Mathematics Genealogy Project

Liens externes[modifier | modifier le code]