Gödel Prize - 1994
Johan HåstadJohan Håstad:
"Almost optimal lower bounds for small depth circuits"
Advances in Computing Research 5 (1989), 143-170
This paper provided the first non-trivial bounds for unbounded fan-in circuit depth that are asymptotically optimal for any function in NP. Even more importantly, the main technique of this paper Håstad's "switching lemma") has had applications not only for circuit lower bounds, but also PRAM lower bounds, learnability, the IP hierarchy and in proving lower bounds for propositional proof systems. Håstad's paper has been very influential both in the direct application of its theorems and in the application of its ideas to other problem domains.