Johan hastad

Johan hastad Biografia
Nascita 19 novembre 1960
Svezia
Nazionalità svedese
Casa Stoccolma
Formazione
Università di Uppsala Università di Stoccolma
Massachusetts Institute of Technology
Attività Matematico , informatico , ingegnere , professore universitario
Altre informazioni
Lavorato per Royal Institute of Technology
Campo Informatica
Membro di Accademia reale svedese delle scienze
American Mathematical Society
Academia Europaea (2007)
Supervisore Shafrira Goldwasser
Sito web www.nada.kth.se/~johanh
Premi

Johan Håstad , nato nel 1960 , è un informatico teorico svedese meglio conosciuto per il suo lavoro sulla complessità algoritmica . Ha vinto due volte il Premio Gödel e una volta il Premio Knuth .

Biografia

Ha conseguito la laurea in matematica presso l' Università di Stoccolma nel 1981 , il master presso l' Università di Uppsala nel 1984 e il dottorato in matematica al MIT nel 1986 , diretto da Shafi Goldwasser .

Dal 1992 è ricercatore e professore di informatica teorica presso la Kungliga tekniska högskolan (KTH) di Stoccolma . È membro della Royal Swedish Academy of Sciences dal 2001 .

È anche editore di diversi giornali, tra cui Theory of computing .

Lavori

La tesi di Johan Håstad si è concentrata sui limiti inferiori sui problemi del circuito booleano . In questo campo, è noto che ha introdotto il lemma di commutazione  (en) , uno dei corollari del quale è che la funzione di parità non è nella classe di complessità chiamata AC 0 . Questo lavoro gli ha permesso di ottenere il suo primo premio Gödel. È anche noto per il suo lavoro sull'inavvicinabilità di alcuni problemi algoritmici , basato sul teorema PCP .

È stato anche l'autore di uno dei primi attacchi di crittografia RSA nel 1985.

Onori

Ha ricevuto il Premio Gödel nel 1994 e 2011 e la tesi di dottorato Award dalla Association for Computing Machinery nel 1986 , così come altri premi.

Note e riferimenti

  1. CV sulla pagina di Johan Håstad
  2. (in) "  Johan Håstad  " nel sito Mathematics Genealogy Project
  3. Pagina interessata nel database KTH
  4. Pagina di Johan Håstad sul sito ufficiale dell'Accademia delle scienze reale svedese
  5. Elenco degli editori del quotidiano Theory of computing , sul sito ufficiale.
  6. Johan Håstad, "Almost Optimal Lower Bounds for Small Depth Circuits" , in Proceedings of the 18th Annual {ACM} Symposium on Theory of Computing, 28-30 maggio 1986, Berkeley, California, {USA} , 1986( DOI  10.1145 / 12130.12132 ) , pag.  6-20
  7. Johan Håstad , "On using RSA with low exponent in a public key network" , in Advances in Cryptology - CRYPTO'85, Lecture Notes in Computer Science , vol.  218, Springer, p.  403-408
  8. Dichiarazione ufficiale del Premio Gödel 1994
  9. Dichiarazione ufficiale del Premio Gödel 2011
  10. Elenco dei destinatari del premio per la tesi di dottorato della Carnegie-Mellon University

link esterno