1994 Gödel Prize (original) (raw)

1994 Gödel Prize

Johan Håstad

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

Created byIan Parberry, March 25, 1999.
Last updated Thu Mar 25 10:06:23 CST 1999.