# Does Cook and Ruzzo's result also hold for logspace-uniform AC0?

In Cook's famous paper on $$\mathsf{NC}$$, he cites the following result:

PROPOSITION 4.7 (Cook and Ruzzo, 1983). $$\mathsf{AC}^k$$ consists of those problems solvable by uniform unbounded fan-in circuit families in $$O(\log^k n)$$ depth and $$n^{O(1)}$$ size.

where $$\mathsf{AC}^k$$ here is defined for $$k \ge 1$$ as the class of problems solvable by an ATM in $$O(\log n)$$ space and $$O(\log^k n)$$ alternation depth. (Of course, the definition of $$\mathsf{AC}^k$$ usually goes the other way around, but given the equivalence it is all just a matter of presentation.)

Note the above is the logspace-uniform version of $$\mathsf{AC}$$. It was later acknowledged that for $$\mathsf{AC}^0$$ the more restrictive dlogtime-uniformity is preferable. There is also an interesting result regarding the (in)equality of dlogtime- and logspace-uniformity of $$\mathsf{AC}^0$$. We also know that dlogtime-uniform $$\mathsf{AC}^0$$ is characterizable as the class of problems solvable by ATMs in $$O(\log n)$$ time (instead of space above) and $$O(1)$$ alternation depth.

Given that dlogtime- and logspace-uniformity most likely does make a difference for $$\mathsf{AC}^0$$ I am interested whether the Cook and Ruzzo result can be extended to the case of $$k = 0$$ and logspace-uniform $$\mathsf{AC}^0$$. Unfortunately, in Cook's paper, "Cook and Ruzzo, 1983" is only listed as "unpublished theorem," so I was unable to check whether the proof also works for $$k=0$$ (and whether Cook and Ruzzo had simply neglected it for some reason).

• Wouldn't PARITY be a counterexample? – sdcvvc Aug 6 '19 at 22:14
• @sdcvvc Of course, the classic counterexample :) Make it an answer? I wonder now where exactly $k > 0$ is needed in the proof... – dkaeae Aug 7 '19 at 8:28