up vote 10 down vote favorite
1

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

share|cite|improve this question
up vote 9 down vote accepted

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.

share|cite|improve this answer
New contributor
Robert Andrews is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • 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. yesterday

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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