Johan Torkel Håstad ( pronunciación sueca: [ˈjûːan ˈhǒːsta] ; nacido el 19 de noviembre de 1960) es un informático teórico sueco más conocido por su trabajo sobre la teoría de la complejidad computacional . Recibió el Premio Gödel en 1994 y 2011 y el Premio de Tesis Doctoral ACM en 1986, entre otros premios. Ha sido profesor de informática teórica en el Real Instituto de Tecnología KTH de Estocolmo , Suecia, desde 1988, convirtiéndose en profesor titular en 1992. Es miembro de la Real Academia Sueca de Ciencias desde 2001.
Recibió su licenciatura en Matemáticas en la Universidad de Estocolmo en 1981, su maestría en Matemáticas en la Universidad de Uppsala en 1984 y su doctorado. 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 circuitos booleanos de profundidad constante para la función de paridad . Después de que Andrew Yao demostró que tales 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 importante herramienta técnica en la complejidad de los circuitos con aplicaciones a la capacidad de aprendizaje , la jerarquía 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 proporcionar un verificador probabilístico para problemas NP que lee sólo tres bits. Además, utilizó estos resultados para demostrar 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 Erdős en la Universidad Hebrea de Jerusalén . En 2012, se convirtió en miembro de la Sociedad Estadounidense de Matemáticas . [6] Fue elegido miembro de ACM en 2018 por "contribuciones en la complejidad, aproximabilidad e inaproximabilidad de los circuitos, y fundamentos de la pseudoaleatoriedad ". [7]
En 2018 recibió el Premio Knuth "por su largo y sostenido historial de avances importantes en los fundamentos 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]