Johan hastad

Johan hastad Biografia
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
Outra informação
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 .

Biografia

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 .

Trabalho

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.

Honras

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.

Notas e referências

  1. CV na página de Johan Håstad
  2. (em) "  Johan Håstad  " no site Mathematics Genealogy Project
  3. Página afetada no banco de dados KTH
  4. Página de Johan Håstad no site oficial da Royal Swedish Academy of Sciences
  5. Lista das editoras do jornal Teoria da Computação , no site oficial.
  6. Johan Håstad, "Almost Optimal Lower Bounds for Small Depth Circuits" , em Proceedings of the 18th Annual {ACM} Symposium on Theory of Computing, maio 28-30, 1986, Berkeley, Califórnia, {EUA} , 1986( DOI  10.1145 / 12130.12132 ) , p.  6-20
  7. Johan Håstad , “Sobre o uso de RSA com baixo expoente em uma rede de chave pública” , em Advances in Cryptology - CRYPTO'85, Lecture Notes in Computer Science , vol.  218, Springer, p.  403-408
  8. Declaração oficial do Prêmio Gödel 1994
  9. Declaração oficial do Prêmio Gödel 2011
  10. Lista de Destinatários do Prêmio de Dissertação de Doutorado da Carnegie-Mellon University

links externos