The class $\textrm{NC}^i$ is the class functions computable by circuits families of bounded fan-in, $n^{O(1)}$ size and $O(\log^i(n))$ depth. The $\textrm{NC}$-hierarchy is the union of those classes.

Is there any study of the linear-size variant of this hierarchy? That is circuits families of bounded fan-in, polylog depth and linear size?

I know their exists some work with linear-$\textrm{AC}^0$ but nothing else. Remark that at least linear-$\textrm{NC}^1$ is nontrivial since it contains regular languages (and thus some $\textrm{NC}^1$-complete languages).


1 Answer 1


It follows from work of Valiant [1, 2] that linear-size $\textrm{NC}^1$ can be simulated by $2^{O(n / \log \log n)}$-size circuits of depth three and unbounded fan-in.

For a nice exposition of this result, see section 3 of the survey by Viola [3].

[1] Leslie G. Valiant. Graph-theoretic arguments in low-level complexity. In: Mathematical Foundations of Computer Science 1977. MFCS 1977. Lecture Notes in Computer Science, vol 53. Springer, Berlin, Heidelberg.

[2] Leslie G. Valiant. Exponential lower bounds for restricted monotone circuits. In: Proceedings of the fifteenth annual ACM symposium on Theory of computing (STOC '83). ACM, New York, NY, USA, 110-117.

[3] Emanuele Viola. On the power of small-depth computation . Foundations and Trends in Theoretical Computer Science, vol. 5, num. 1, pp. 1--72, 2009.

  • $\begingroup$ Thanks for the reference. I didn't know about it. I guess you are not aware of any more work on the subject, otherwise you would have added it to the post. $\endgroup$
    – C.P.
    Oct 17, 2018 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.