Gödel Prize - 1994

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.

e-max.it: your social media marketing partner
European Association for Theoretical Computer Science - Maintained and hosted by RU1 / CTI.