||This biographical article needs additional citations for verification. (January 2013)|
|Born||19 November 1960|
|Institutions||Royal Institute of Technology|
|Alma mater||Massachusetts Institute of Technology
|Doctoral advisor||Shafrira Goldwasser|
|Doctoral students||Viggo Kann|
|Notable awards||IMO gold medal (1977)
ACM Doctoral Dissertation Award (1985)
Gödel Prize (1994, 2011)
Johan Torkel Håstad (born 19 November 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 2011 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.
Håstad's thesis and Gödel Prize (1994) 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.
|P ≟ NP||This biographical article relating to a computer scientist is a stub. You can help Wikipedia by expanding it.|