Johan Håstad

Johan Håstad

Johan Håstad (born 1960) is a Swedish theoretical computer scientist most known for his work on computational complexity theory. He was the recipient of the Gödel Prize in 1994 and the ACM Doctoral Dissertation Award in 1986, among other prizes. He is a professor in Theoretical Computer Science at the Royal Institute of Technology in Stockholm, Sweden since 1992. He is a member of the Royal Swedish Academy of Sciences since 2001.

He received his B.S. in Mathematics at Stockholm University in 1981, his M.S. in Mathematics at Uppsala University in 1984 and his Ph.D. in Mathematics from MIT in 1986.

Håstad's thesis and Gödel Prize concerned his work on lower bounds on the size of constant-depth Boolean circuits for the parity function. After Andrew Yao proved that such circuits require exponential size, Håstad proved nearly optimal lower bounds on the necessary size through his Switching Lemma, which became an important technical tool in Boolean function complexity.

External links

* [http://www.nada.kth.se/~johanh/ Johan Håstad's home page]
*


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Johan Håstad — Johan Håstad, né en 1960, est un informaticien théorique suédois connu particulièrement pour son travail sur la complexité algorithmique. Il a reçu le Prix Gödel en 1994 et 2011 et le Doctoral Dissertation Award de l Association for Computing… …   Wikipédia en Français

  • Johan Håstad — Nacimiento 19 de noviembre de 1960 (51 años)  Suecia Residencia Estocolmo …   Wikipedia Español

  • Johan Hastad — Johan Håstad Johan Håstad, né en 1960, est un informaticien théorique suédois connu particulièrement pour son travail sur la complexité algorithmique. Il a reçu le Prix Gödel en 1994 et le Doctoral Dissertation Award de l Association for… …   Wikipédia en Français

  • Johan Håstad — Johan Torkel Håstad (* 19. November 1960) ist ein schwedischer Informatiker. Hastad erhielt 1977 die Goldmedaille auf der Internationalen Mathematikolympiade. Er studierte Mathematik an der Universität Stockholm (Vordiplom, Högskoleexamen 1981)… …   Deutsch Wikipedia

  • Johan (given name) — Infobox Given Name Revised name = Johan imagesize= caption= pronunciation= gender = Male meaning = region = Germanic origin = related names = John footnotes = Johan is a masculine given name of German language origin, meaning God is gracious .… …   Wikipedia

  • Премия Гёделя — (англ. Gödel Prize)  премия в области теории вычислительных систем имени Курта Гёделя, вручаемая ежегодно организациями ACM SIGACT (Special Interest Group on Algorithms and Computation Theory) и EATCS (European Association for… …   Википедия

  • RSA-Kryptosystem — RSA ist ein asymmetrisches kryptographisches Verfahren, das sowohl zur Verschlüsselung als auch zur digitalen Signatur verwendet werden kann.[1] Es verwendet ein Schlüsselpaar, bestehend aus einem privaten Schlüssel, der zum Entschlüsseln oder… …   Deutsch Wikipedia

  • Prix Gödel — Nommé en l honneur du logicien Kurt Gödel, le prix Gödel a été créé en 1992 par l European Association for Theoretical Computer Science (EATCS), l Association for Computing Machinery (ACM) et le groupe de l ACM sur l algorithmique et la théorie… …   Wikipédia en Français

  • Codage RSA — Rivest Shamir Adleman Pour les articles homonymes, voir RSA. Rivest Shamir Adleman ou RSA est un algorithme asymétrique de cryptographie à clé publique, très utilisé dans le commerce électronique, et plus généralement pour échanger des données… …   Wikipédia en Français

  • Code RSA — Rivest Shamir Adleman Pour les articles homonymes, voir RSA. Rivest Shamir Adleman ou RSA est un algorithme asymétrique de cryptographie à clé publique, très utilisé dans le commerce électronique, et plus généralement pour échanger des données… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”