# Upper bounds on the circut depth

Suppose $$f:\{0,1\}^n \to \{0,1\}$$ is a function such that it can be computed by a circuit of size $$n^c$$ for some constant $$c>0$$.

Q. Is there any nontrivial upper bound on the depth of a circuit of size quasi-polynomial or subexponential computing $$f$$?

It seems that, for boolean circuits, only logarithmic in the size improvements of the trivial depth are known: every circuit of size $$S$$ can be transformed to a circuit of depth $$O(S/\log S)$$ Paterson and Valiant. For boolean (and arithmetic) formulas, the depth can be reduced to $$O(\log S)$$ (known as Spira's theorem). For arithmetic circuits, we can do much better than in the boolean case: then the resulting circuit has depth only about $$(\log S)(\log d)$$ and size $$O(S^3)$$, where $$d$$ is the degree of the computed polynomial: Valiant, Skyum, Berkowitz and Rackoff. Earlier, Hyafil (see the citation in the above paper) has obtained a similar upper bound on the depth, but the size increased until about $$S^{\log d}$$.