| 词条 | Johan Håstad |
| 释义 |
| name = Johan Håstad | image = | image_size = | caption = | birth_date = {{birth date and age|1960|11|19|df=y}} | birth_place = | death_date = | death_place = | nationality = Sweden | fields = Computer science | workplaces = Royal Institute of Technology | alma_mater = {{Plainlist|
}} | doctoral_advisor = Shafrira Goldwasser[1] | doctoral_students = | known_for = | awards = {{Plainlist|class=nowrap|
}} Johan Torkel Håstad ({{IPA-sv|²juːan ˈhoːsta}}; 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 has been a professor in theoretical computer science at the Royal Institute of Technology in Stockholm, Sweden since 1988, becoming a full professor in 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.[2] Håstad's thesis and 1994 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 circuit complexity with applications to learnability, the IP hierarchy, and proof systems.[3] He also received the 2011 Gödel Prize for his work on optimal inapproximability results. In particular, he improved the PCP theorem (which won the same prize in 2001) to give a probabilistic verifier for NP problems which reads only three bits. Further, he used these results to prove results in hardness of approximation.[4] In 1999 Håstad was an Erdős Lecturer at the Hebrew University of Jerusalem. In 2012, he became a fellow of the American Mathematical Society.[5] He was elected as an ACM Fellow in 2018 for "contributions in circuit complexity, approximability and inapproximability, and foundations of pseudorandomness".[6] References1. ^{{MathGenealogy|id=79819}} 2. ^[https://simons.berkeley.edu/people/johan-h%C3%A5stad Simons Institute: Johan Håstad], retrieved 2018-04-05. 3. ^[https://www.sigact.org/Prizes/Godel/1994.html 1994 Gödel Prize], retrieved 2018-04-05 4. ^[https://www.sigact.org/Prizes/Godel/2011.html 2001 Gödel Prize], retrieved 2018-04-05 5. ^List of Fellows of the American Mathematical Society, retrieved 2013-01-19. 6. ^{{citation|url=https://www.acm.org/media-center/2018/december/fellows-2018|title=2018 ACM Fellows Honored for Pivotal Achievements that Underpin the Digital Age|publisher=Association for Computing Machinery|date=December 5, 2018}} External links
15 : 1960 births|Living people|Swedish computer scientists|Swedish mathematicians|20th-century Swedish 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|Fellows of the Association for Computing Machinery|International Mathematical Olympiad participants |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。