Theoretical Computer Science
cc.complexity-theory circuit-complexity lower-bounds
Updated Sun, 29 May 2022 17:46:09 GMT

Lower bounds for constant-depth formulae?


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.

Solution

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 (3)

  • +5 – this gives more than a quadratic increase in size. (Though, not super-polynomial increase, of course.) — Aug 17, 2010 at 11:18  
  • +2 – 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.? — Aug 17, 2010 at 15:48  
  • +3 – 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. — Aug 17, 2010 at 21:41  

References