Aniversário |
19 de novembro de 1960 Suécia |
---|---|
Nacionalidade | sueco |
Casa | Estocolmo |
Treinamento |
Uppsala University Stockholm University Massachusetts Institute of Technology |
Atividades | Matemático , cientista da computação , engenheiro , professor universitário |
Trabalhou para | Instituto Real de Tecnologia |
---|---|
Campo | Ciência da Computação |
Membro de |
Academia Real Sueca de Ciências American Mathematical Society Academia Europaea (2007) |
Supervisor | Shafrira Goldwasser |
Local na rede Internet | www.nada.kth.se/~johanh |
Prêmios |
Johan Håstad , nascido em 1960 , é um cientista da computação teórico sueco mais conhecido por seu trabalho sobre complexidade algorítmica . Ele ganhou o Prêmio Gödel duas vezes e o Prêmio Knuth uma vez .
Ele recebeu seu diploma de bacharel em matemática na Universidade de Estocolmo em 1981 , seu mestrado na Universidade de Uppsala em 1984 e seu doutorado em matemática pelo MIT em 1986 , dirigido por Shafi Goldwasser .
Ele é pesquisador e professor de ciência da computação teórica na Kungliga tekniska högskolan (KTH) em Estocolmo desde 1992 . Ele é membro da Real Academia Sueca de Ciências desde 2001 .
Ele também é editor de vários jornais, incluindo Teoria da Computação .
A tese de Johan Håstad centrou-se nos limites inferiores dos problemas do circuito booleano . Neste campo, ele é conhecido por ter introduzido o lema de comutação (en) , um dos corolários do qual é que a função de paridade não está na classe de complexidade chamada AC 0 . Este trabalho permitiu-lhe obter o seu primeiro Prémio Gödel. Ele também é conhecido por seu trabalho sobre a não aproximabilidade de certos problemas algorítmicos , com base no teorema PCP .
Ele também foi o autor de um dos primeiros ataques de criptografia RSA em 1985.
Ele recebeu o Prêmio Gödel em 1994 e 2011 e o Prêmio de Dissertação de Doutorado da Association for Computing Machinery em 1986 , além de outros prêmios.