We prove that a modification of Andreev's function is not computable by (3 + \alpha - \varepsilon) \log{n} depth De Morgan formula with (2\alpha - \varepsilon)\log{n} layers of AND gates at the top for any 1/5 > \alpha > 0 and any constant \varepsilon > 0. In order to do ... more >>>

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., \mathbf{P}\not\subseteq \mathbf{NC}^{1}). Karchmer, Raz, and Wigderson (Computational Complexity 5(3/4), 1995) suggested to approach this problem by proving that depth complexity of a composition of functions f \diamond g is roughly ... more >>>