<p>This question has been completely resolved (up to constant factors) by a recent result of Benjamin Rossman (<a href="http://eccc.hpi-web.de/report/2013/169/">http://eccc.hpi-web.de/report/2013/169/</a>).</p>

<p>As Kaveh points out above, a depth $d$, size $S$, circuit can be converted to a depth $d$, size $S^d$ formula. </p>

<p>Rossman shows that this is essentially tight. For any depth $d$, he exhibits a function that can be computed by a constant-depth circuit of depth $d$ and size $S = O(n^3)$, but any constant-depth formula (or even a $\sqrt{\log n}$-depth formula) needs size $S^{\Omega(d)}$ to compute it. </p>

<p>(Forgot to say this before: Thanks to Benjamin Rossman for letting me know about this result.)</p>

CC BY-SA 3.0
2014-01-21T16:03:39.487Z
2014-01-22T12:27:41.320Z
2014-01-22T12:27:41.320Z
Robin Kothari
<p>It is easy to convert a constant depth circuit to a constant depth formula of the same depth with polynomial size increase, by making copies of gates used more than once. If the depth of the circuit is $d$ and its size is $O(p(n))$, the formula will have depth $d$ and size $O((p(n))^d)$. Therefore the answer is no.</p>

CC BY-SA 2.5
2010-08-17T11:18:41.057Z
this gives more than a quadratic increase in size. (Though, not super-polynomial increase, of course.)
Iddo Tzameret
CC BY-SA 2.5
2010-08-17T15:48:55.607Z
Thanks for the answer. Any idea about a particular function f which has a constant-depth circuit of size S, but needs a formula of size S^2, or S^10, etc.?
Robin Kothari
CC BY-SA 2.5
2010-08-17T21:41:16.547Z
I think the relation between depth and circuit size is still open (It is known that "depth" is teta of formula size). See chapters 7 and 8 in Wegener's book "Complexity of boolean functions" for some function with explicit formula size lower-bounds. There is one with almost quadratic increase ($n^2/log n$), didn't notice anything better.
Kaveh
CC BY-SA 2.5
2010-08-17T07:20:12.763Z
2010-08-17T08:17:42.563Z
2010-08-17T08:17:42.563Z
Kaveh
<p>We know a lot about the limitations of (polynomial size) constant-depth circuits. Since (polynomial size) constant-depth formulae are an even more restricted model of computation, all problems known not to be in AC<sup>0</sup> are also not computable by a constant-depth formula.  However, since it's an easier model, I'm guessing there are more problems known to be not computable in this model.  Has this been studied? (I'm guessing it has been, but I'm probably not using the right search terms.)</p>

<p>Specifically I am interested in the following question: Is there some function f, which can be computed by an AC<sup>0</sup> circuit of size S, but needs a constant-depth formula of size at least quadratic in S, or super-polynomial in S?  What's the best known result of this kind?</p>

<p>In case it is not clear what I mean by constant-depth formula, I mean a formula which if you write out as a tree (with internal nodes being AND/OR/NOT gates, and leaves being inputs), then this tree has constant height. Equivalently, a constant-depth formula is a constant-depth circuit in which all non-input gates have fanout 1.</p>

<cc.complexity-theory><circuit-complexity><lower-bounds>
Lower bounds for constant-depth formulae?
Robin Kothari
# Lower bounds for constant-depth formulae?

(Asked by: username_0 on 2010-08-17)

We know a lot about the limitations of (polynomial size) constant-depth circuits. Since (polynomial size) constant-depth formulae are an even more restricted model of computation, all problems known not to be in AC0 are also not computable by a constant-depth formula. However, since it's an easier model, I'm guessing there are more problems known to be not computable in this model. Has this been studied? (I'm guessing it has been, but I'm probably not using the right search terms.)

Specifically I am interested in the following question: Is there some function f, which can be computed by an AC0 circuit of size S, but needs a constant-depth formula of size at least quadratic in S, or super-polynomial in S? What's the best known result of this kind?

In case it is not clear what I mean by constant-depth formula, I mean a formula which if you write out as a tree (with internal nodes being AND/OR/NOT gates, and leaves being inputs), then this tree has constant height. Equivalently, a constant-depth formula is a constant-depth circuit in which all non-input gates have fanout 1.

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

---

## 2 answers

### Answer by username_1 on 2010-08-17. Score: 12 | Accepted answer

It is easy to convert a constant depth circuit to a constant depth formula of the same depth with polynomial size increase, by making copies of gates used more than once. If the depth of the circuit is $d$ and its size is $O(p(n))$, the formula will have depth $d$ and size $O((p(n))^d)$. Therefore the answer is no.

> **Comments:**
> **username_2**: this gives more than a quadratic increase in size. (Though, not super-polynomial increase, of course.)  
> **username_0**: Thanks for the answer. Any idea about a particular function f which has a constant-depth circuit of size S, but needs a formula of size S^2, or S^10, etc.?  
> **username_1**: I think the relation between depth and circuit size is still open (It is known that "depth" is teta of formula size). See chapters 7 and 8 in Wegener's book "Complexity of boolean functions" for some function with explicit formula size lower-bounds. There is one with almost quadratic increase ($n^2/log n$), didn't notice anything better.  

---

### Answer by username_0 on 2014-01-21. Score: 17

This question has been completely resolved (up to constant factors) by a recent result of Benjamin Rossman (<http://eccc.hpi-web.de/report/2013/169/>).

As Kaveh points out above, a depth $d$, size $S$, circuit can be converted to a depth $d$, size $S^d$ formula.

Rossman shows that this is essentially tight. For any depth $d$, he exhibits a function that can be computed by a constant-depth circuit of depth $d$ and size $S = O(n^3)$, but any constant-depth formula (or even a $\sqrt{\log n}$-depth formula) needs size $S^{\Omega(d)}$ to compute it.

(Forgot to say this before: Thanks to Benjamin Rossman for letting me know about this result.)


---

