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.
Lower bounds for constant-depth formulae?
cc.complexity theory;circuit complexity;lower bounds
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.