The containment $NC^1 \subseteq DSPACE[\log{n}]$ is simple and well-known (assuming a reasonable notion of uniformity for $NC^1$) and follows by:
- start with an $O(\log{n})$-depth polynomial sized Boolean circuit of fan-in $2$ over $\{\vee, \wedge,\neg\}$
- convert it to a formula (i.e. a circuit where all gates have fan-out bounded by 1) with a polynomial blowup in size and maintaining the depth,
- run a stack algorithm with an $O(\log{n})$ depth stack with entries which are bits indicating the values of gates that have been evaluated along a path from current node to the output node
Thus the space used is logarithmic in the input completing the proof. Notice, that the entries are single bits because we didn't explicitly need to store the name of the gates along with the value since the circuit is a formula (just storing the name of the current gate suffices since tracing back its ancestor chain and thus the name of the gates whose values we have in the stack, is easy).
In trying to generalize this directly to $NC^i$ circuits ($i > 1$) the second step above does not seem possible (unless the $NC$ hierarchy collapses to $NC^1$). So in order to perform the simulation it seems necessary to remember the name of the gates along the ancestor chain. Notice that instead we could also remember $\log{f}$ bits where $f$ is an upper bound on the fan-out of a gate since this would also uniquely identify the chain of nodes from which the current node is descended from. This impli $NC^i \subseteq DSPACE[\log^{i+1}{n}]$ since the trivial upper bound on $f$ is polynomial.
My question is can we bound $f$ by a constant or through some other means show that $NC^i \subseteq DSPACE[\log^i{n}]$. This answer seems to indicate that this is indeed the case. I am interested in knowing the reference and/or the proof.
