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


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

| cite | improve this answer | |
  • $\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$ – Erfan Khaniki Jun 25 '19 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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