# Linear circuit complexity classes

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).

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.

• 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. – C.P. Oct 17 '18 at 15:03