Johan Håstad
Johan Håstad | |
|---|---|
| Nacido | ( 19 de noviembre de 1960 )19 de noviembre de 1960 |
| Nacionalidad | sueco |
| Alma máter | |
| Premios |
|
| Carrera científica | |
| Campos | Ciencias de la Computación |
| Instituciones | Instituto Real de Tecnología KTH |
| Asesor de doctorado | Shafrira Goldwasser [1] |
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 en 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 Instituto Real de Tecnología KTH 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 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 centraron en 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 demostrara que dichos circuitos requieren un tamaño exponencial, Håstad demostró límites inferiores casi óptimos para 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 circuitos con aplicaciones en 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 de inaproximabilidad óptima. En particular, mejoró el teorema PCP (que ganó el mismo premio en 2001) para proporcionar un verificador probabilístico para problemas NP que lee solo tres bits. Además, utilizó estos resultados para demostrar resultados en la dificultad 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 miembro de la ACM en 2018 por "contribuciones en complejidad de circuitos, aproximabilidad e inaproximabilidad y fundamentos de pseudoaleatoriedad ". [7]
En 2018 recibió el Premio Knuth "por su largo y sostenido historial de avances fundamentales en los fundamentos de la ciencia informática, con enorme impacto en muchas áreas, incluidas la optimización, la criptografía, la computación paralela y la teoría de la complejidad". [8]
Referencias
- ^ Johan Håstad en el Proyecto de Genealogía Matemática
- ^ Instituto Simons: Johan Håstad, consultado el 5 de abril de 2018.
- ^ Premio Gödel 1994, consultado el 5 de abril de 2018
- ^ Premio Gödel 2011, consultado el 5 de abril de 2018
- ^ Håstad, Johan (1998). "Sobre la aproximación de problemas de optimización NP-hard". Doc. Math. (Bielefeld) Extra Vol. ICM Berlin, 1998, vol. III . págs. 441–450.
- ^ Lista de miembros de la American Mathematical Society, consultado el 19 de enero de 2013.
- ^ Los miembros de la ACM 2018 fueron reconocidos por sus logros fundamentales que sustentan la era digital, Association for Computing Machinery , 5 de diciembre de 2018
- ^ Johan Håstad recibe el premio Knuth 2018 (PDF) , ACM, 6 de agosto de 2018
Enlaces externos
- Página de inicio de Johan Håstad
- Resultados de Johan Håstad en la Olimpiada Internacional de Matemáticas
