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&gt;0$.


  Q. Is there any nontrivial upper bound on the depth of a circuit of size quasi-polynomial or subexponential computing $f$?
[Too long for a comment, hence, an "answer".]

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}$.