Johan Håstad
Lua error in package.lua at line 80: module 'strict' not found.
| Johan Håstad | |
|---|---|
| Born | 19 November 1960 |
| Nationality | Sweden |
| Fields | Computer science |
| Institutions | Royal Institute of Technology |
| Alma mater | Massachusetts Institute of Technology Uppsala University Stockholm University |
| Doctoral advisor | Shafrira Goldwasser |
| Doctoral students | Gustav Hast Viggo Kann Jakob Nordström Mårten Trolin Douglas Wikström |
| Notable awards | IMO gold medal (1977) ACM Doctoral Dissertation Award (1985) Gödel Prize (1994, 2011) |
Johan Torkel Håstad (Swedish pronunciation: [ˈjuːˈan ˈhoːˈ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.
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.[1][2]
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.
He received the 2011 Gödel Prize for his work on optimal inapproximability results. In 2012 he became a fellow of the American Mathematical Society.[3]
References
<templatestyles src="Reflist/styles.css" />
Cite error: Invalid <references> tag; parameter "group" is allowed only.
<references />, or <references group="..." />External links
Lua error in package.lua at line 80: module 'strict' not found.
<templatestyles src="Asbox/styles.css"></templatestyles>
- ↑ Johan Håstad at the Mathematics Genealogy Project
- ↑ Johan Håstad's ACM doctoral dissertation award
- ↑ List of Fellows of the American Mathematical Society, retrieved 2013-01-19.
- Pages with reference errors
- 1960 births
- Living people
- Swedish computer scientists
- Swedish mathematicians
- 20th-century mathematicians
- 21st-century mathematicians
- Gödel Prize laureates
- Uppsala University alumni
- Stockholm University alumni
- Royal Institute of Technology academics
- Members of the Royal Swedish Academy of Sciences
- Massachusetts Institute of Technology alumni
- Fellows of the American Mathematical Society
- International Mathematical Olympiad participants
- Computer scientist stubs
