Johan Hastad, Stasys Jukna and Pavel Pudlak
Top-Down
Lower Bounds for Depth-Three Circuits
Abstract
We present a top-down lower bound method for depth-three AND, OR, NOT
circuits which is simpler than the previous methods and in some cases gives
better lower bounds. In particular, we prove that depth-three AND, OR,
NOTcircuits that compute parity (or majority) require size at least $2^{0.618\ldots\sqrt{n}}$
(or $2^{0.849\ldots\sqrt{n}}$, respectively). This is the first simple
proof of a strong lower bound by a top-down argument for non-monotone circuits.
[FOCS'93. Journal version appeared in: Computational Complexity]
Back
to my home page