Johan Torkel Håstad ( pronunciación sueca: [ˈjûːan ˈhǒːsta] ; nacido el 19 de noviembre de 1960) es un científico informático teórico sueco más conocido por su trabajo en la teoría de la complejidad computacional . Recibió el Premio Gödel en 1994 y 2011 y el Premio de Disertación Doctoral ACM en 1986, entre otros premios. Ha sido profesor de informática teórica en KTH Royal Institute of Technology en Estocolmo , Suecia desde 1988, convirtiéndose en profesor titular en 1992. Es miembro de la Real Academia Sueca de Ciencias desde 2001.
Recibió su BS en Matemáticas en la Universidad de Estocolmo en 1981, su MS en Matemáticas en la Universidad de Uppsala en 1984 y su Ph.D. en Matemáticas del MIT en 1986. [2]
La tesis de Håstad y el premio Gödel de 1994 se referían a su trabajo sobre los límites inferiores del tamaño de los circuitos booleanos de profundidad constante para la función de paridad . Después de que Andrew Yao demostró que dichos circuitos requieren un tamaño exponencial, Håstad demostró límites inferiores casi óptimos en el tamaño necesario a través de su lema de conmutación , que se convirtió en una herramienta técnica importante en la complejidad de los circuitos con aplicaciones para la capacidad de aprendizaje , la jerarquía de IP y los sistemas de prueba . [3]
También recibió el Premio Gödel 2011 por su trabajo sobre resultados óptimos de inaproximabilidad. En particular, mejoró el teorema PCP (que ganó el mismo premio en 2001) para dar un verificador probabilístico para problemas NP que lee solo tres bits. Además, utilizó estos resultados para probar los resultados en dureza de aproximación . [4]
En 1998, Håstad fue orador invitado del Congreso Internacional de Matemáticos en Berlín. [5] En 1999 fue profesor de Erdős en la Universidad Hebrea de Jerusalén . En 2012, se convirtió en miembro de la American Mathematical Society . [6] Fue elegido como miembro de ACM en 2018 por "contribuciones en la complejidad del circuito, la aproximabilidad y la inaproximabilidad, y los fundamentos de la pseudoaleatoriedad". [7]
En 2018 recibió el Premio Knuth "por su largo y sostenido historial de hitos en los cimientos de la informática, con un gran impacto en muchas áreas, incluidas la optimización, la criptografía, la computación paralela y la teoría de la complejidad". [8]