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 2018 he received the Knuth Prize "for his long and sustained record of milestone breakthroughs at the foundations of computer science, with huge impact on many areas including optimization, cryptography, parallel computing, and complexity theory."[8]
johan, håstad, johan, torkel, håstad, swedish, pronunciation, ˈjûːan, ˈhǒːsta, born, november, 1960, swedish, theoretical, computer, scientist, most, known, work, computational, complexity, theory, recipient, gödel, prize, 1994, 2011, doctoral, dissertation, a. Johan Torkel Hastad Swedish pronunciation ˈjuːan ˈhǒː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 Godel 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 KTH 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 Johan HastadBorn 1960 11 19 19 November 1960 age 63 NationalitySwedishAlma materMassachusetts Institute of Technology Uppsala University Stockholm UniversityAwardsIMO gold medal 1977 ACM Doctoral Dissertation Award 1985 Godel Prize 1994 2011 Knuth Prize 2018 Scientific careerFieldsComputer scienceInstitutionsKTH Royal Institute of TechnologyDoctoral advisorShafrira Goldwasser 1 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 Hastad s thesis and 1994 Godel 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 Hastad 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 Godel 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 1998 Hastad was an Invited Speaker of the International Congress of Mathematicians in Berlin 5 In 1999 he was an Erdos Lecturer at the Hebrew University of Jerusalem In 2012 he became a fellow of the American Mathematical Society 6 He was elected as an ACM Fellow in 2018 for contributions in circuit complexity approximability and inapproximability and foundations of pseudorandomness 7 In 2018 he received the Knuth Prize for his long and sustained record of milestone breakthroughs at the foundations of computer science with huge impact on many areas including optimization cryptography parallel computing and complexity theory 8 References edit Johan Hastad at the Mathematics Genealogy Project Simons Institute Johan Hastad retrieved 2018 04 05 1994 Godel Prize retrieved 2018 04 05 2011 Godel Prize retrieved 2018 04 05 Hastad Johan 1998 On approximating NP hard optimization problems Doc Math Bielefeld Extra Vol ICM Berlin 1998 vol III pp 441 450 List of Fellows of the American Mathematical Society retrieved 2013 01 19 2018 ACM Fellows Honored for Pivotal Achievements that Underpin the Digital Age Association for Computing Machinery December 5 2018 2018 Knuth Prize is Awarded to Johan Hastad PDF ACM August 6 2018External links editJohan Hastad s home page Johan Hastad s results at International Mathematical Olympiad Retrieved from https en wikipedia org w index php title Johan Hastad amp oldid 1211552017, wikipedia, wiki, book, books, library,
