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 |
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 .
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 .
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.
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.