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

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

<p>[1] Leslie G. Valiant. <a href="https://doi.org/10.1007/3-540-08353-7_135" rel="noreferrer">Graph-theoretic arguments in low-level complexity</a>. In: Mathematical Foundations of Computer Science 1977. MFCS 1977. Lecture Notes in Computer Science, vol 53. Springer, Berlin, Heidelberg.</p>

<p>[2] Leslie G. Valiant. <a href="https://doi.org/10.1145/800061.808739" rel="noreferrer">Exponential lower bounds for restricted monotone circuits</a>. In: Proceedings of the fifteenth annual ACM symposium on Theory of computing (STOC '83). ACM, New York, NY, USA, 110-117.</p>

<p>[3] Emanuele Viola. <a href="http://www.ccs.neu.edu/home/viola/papers/shallow.pdf" rel="noreferrer">On the power of small-depth computation
</a>. Foundations and Trends in Theoretical Computer Science, vol. 5, num. 1, pp. 1--72, 2009.</p>

CC BY-SA 4.0
2018-10-17T15:03:00.543Z
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.
CC BY-SA 4.0
2018-10-17T02:52:22.503Z
2018-10-17T02:52:22.503Z
Robert Andrews
<p>The class <span class="math-container">$\textrm{NC}^i$</span> is the class functions computable by circuits families of bounded fan-in, <span class="math-container">$n^{O(1)}$</span> size and <span class="math-container">$O(\log^i(n))$</span> depth. 
The <span class="math-container">$\textrm{NC}$</span>-hierarchy is the union of those classes. </p>

<p>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?</p>

<p>I know their exists some work with linear-<span class="math-container">$\textrm{AC}^0$</span> but nothing else. Remark that at least linear-<span class="math-container">$\textrm{NC}^1$</span> is nontrivial since it contains regular languages (and thus some <span class="math-container">$\textrm{NC}^1$</span>-complete languages). </p>

<cc.complexity-theory><circuit-complexity>
Linear circuit complexity classes
C.P.
# Linear circuit complexity classes

(Asked by: username_0 on 2018-10-16)

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

**Tags:** cc.complexity-theory, circuit-complexity

---

## 1 answers

### Answer by username_1 on 2018-10-17. Score: 10 | Accepted answer

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](https://doi.org/10.1007/3-540-08353-7_135). 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](https://doi.org/10.1145/800061.808739). 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](http://www.ccs.neu.edu/home/viola/papers/shallow.pdf). Foundations and Trends in Theoretical Computer Science, vol. 5, num. 1, pp. 1--72, 2009.

> **Comments:**
> **username_0**: 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.  

---

