[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.
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.
[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.