<p>[Too long for a comment, hence, an "answer".]</p>

<p>It seems that, for <em>boolean</em> circuits, only logarithmic in the size improvements of the trivial depth are known: every circuit of size <span class="math-container">$S$</span> can be transformed to a circuit of depth <span class="math-container">$O(S/\log S)$</span> <a href="https://www.sciencedirect.com/science/article/pii/0304397576900906" rel="noreferrer">Paterson and Valiant</a>. For boolean (and arithmetic) <em>formulas</em>, the depth can be reduced to <span class="math-container">$O(\log S)$</span> (known as Spira's theorem). For arithmetic <em>circuits</em>, we can do much better than in the boolean case: then the resulting circuit has depth only about <span class="math-container">$(\log S)(\log d)$</span> and size <span class="math-container">$O(S^3)$</span>, where <span class="math-container">$d$</span> is the degree of the computed polynomial: <a href="https://epubs.siam.org/doi/abs/10.1137/0212043" rel="noreferrer">Valiant, Skyum, Berkowitz and Rackoff</a>. Earlier, Hyafil (see the citation in the above paper) has obtained a similar upper bound on the depth, but the size increased until about <span class="math-container">$S^{\log d}$</span>.</p>

CC BY-SA 4.0
2019-06-25T18:30:20.720Z
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.
Erfan Khaniki
CC BY-SA 4.0
2019-06-25T17:24:14.960Z
2019-06-25T17:24:14.960Z
Stasys
<p>Suppose <span class="math-container">$f:\{0,1\}^n \to \{0,1\}$</span> is a function such that it can be computed by a circuit of size <span class="math-container">$n^c$</span> for some constant <span class="math-container">$c&gt;0$</span>.</p>

<blockquote>
  <p>Q. Is there any nontrivial upper bound on the depth of a circuit of size quasi-polynomial or subexponential computing <span class="math-container">$f$</span>?</p>
</blockquote>

<cc.complexity-theory><circuit-complexity>
Upper bounds on the circut depth
Erfan Khaniki
# Upper bounds on the circut depth

(Asked by: username_0 on 2019-06-25)

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

**Tags:** cc.complexity-theory, circuit-complexity

---

## 1 answers

### Answer by username_1 on 2019-06-25. Score: 6 | Accepted answer

[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](https://www.sciencedirect.com/science/article/pii/0304397576900906). 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](https://epubs.siam.org/doi/abs/10.1137/0212043). 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}$.

> **Comments:**
> **username_0**: 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.  

---

