# Hierarchy theorems for circuit depth

What kind of hierarchy theorems are there for circuit depth?

Statements like

if $g(n) \in o(f(n))$ and $f(n) \in n^{O(1)}$ then $\mathsf{SizeDepth}(n^{O(1)}, g(n)) \subsetneq \mathsf{SizeDepth}(n^{O(1)}, f(n))$.

• Nothing really. We don't know if $\mathsf{NC}^1 = \mathsf{P}/\mathrm{poly}$ ! – Kristoffer Arnsfelt Hansen Oct 9 '12 at 15:47
• @Kristoffer, yes, that is right, I gave it as an example of the kind of statements I am looking for. In other words interesting classes of circuits where increasing depth is known to make the class larger. – Kaveh Oct 9 '12 at 16:02
• Am not quite sure, but this should work. We know that the minimum depth of a circuit for $f$ is $\approx$ logarithm of the minimum size of a formula for $f$. Now, the hierarchy for formula size should be possible to show in the same manner as for circuit size (using Shannon-Lupanov results). Say, circuits of size $4t$ are properly stronger than circuits of size $t$. Of course, things get a bit more complicated, if we require the size to be polynomial. – Stasys Oct 10 '12 at 11:52

## 2 Answers

A paper of Klawe, Paul, Pippenger, and Yannakakis gives an hierarchy theorem for constant depth monotone formulas: http://dl.acm.org/citation.cfm?id=808717

Specifically, for every $k$ it gives a function that can be computed by a formula of depth $k$ and size $n$ but requires formulas of depth $k-1$ of size $\exp(n^{1/k})$.

Raz and McKenzie, in Separation of the monotone NC hierarchy, show that the monotone NC hierarchy is strict, and separate monotone NC from monotone P.