Johan Håstad

Johan Torkel Hastad (born November 19, 1960) is a Swedish theoretical computer scientist most known for his work on computational complexity theory. He received the Godel Prize in 1994 and 2011 and the ACM Doctoral Dissertation Award in 1986, and has been a professor in theoretical computer science at KTH Royal Institute of Technology in Stockholm since 1988, becoming full professor in 1992. His 1994 Godel Prize concerned lower bounds on the size of constant-depth Boolean circuits for the parity function, proved through his switching lemma, an important technical tool in circuit complexity. His 2011 Godel Prize was for work on optimal inapproximability results, improving the PCP theorem to give a probabilistic verifier for NP problems that reads only three bits. He was elected an ACM Fellow in 2018 for contributions in circuit complexity, approximability and inapproximability, and foundations of pseudorandomness, and in 2018 received the Knuth Prize for milestone breakthroughs at the foundations of computer science.