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$?


1 Answer 1


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

  • $\begingroup$ Thanks a lot for the references. Right now I accept this as an answer because it captures the state of the art of this matter. $\endgroup$ Jun 25, 2019 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.