<p>Assume that we have an unbounded fan-in circuit family of depth $d(n)$ and size $s(n)$. </p>

<p>What is <em>the smallest depth</em> (in terms of $d(n)$ and $n$ and $s(n)$) bounded fan-in circuit family of size $poly(s)$ for it?</p>

<p>In particular what is the largest depth $d(n)$ for which we know polynomial size unbounded fan-in circuit families of depth $d(n)$ are in $\mathsf{NC^1}$?</p>

CC BY-SA 3.0
2014-02-08T17:37:23.123Z
Is there any example of a family of circuits for which $d(n) = \omega(1), s(n) = n^{O(1)}$ but no equivalent $\mathsf{AC}^0$ family is known. Yet the computed family of functions is in $\mathsf{NC}^1$.
SamiD
CC BY-SA 3.0
2014-02-08T21:22:23.257Z
@SamiD, I don't know any natural example, for artificial one we can take a suitable variant of circuit evaluation problem, e.g. circuit evaluation for $AC$ circuits of depth $\lg \lg n$.
Kaveh
CC BY-SA 3.0
2014-02-08T21:24:40.190Z
ps: since the time I have posted the question I have asked a few experts in circuit complexity and the question seems to be open.
Kaveh
CC BY-SA 3.0
2014-02-09T07:06:53.537Z
I thought that class or even its uniform iterated version $\mathsf{FOLL}$ is not known to be comparable even to Logspace (see e.g. http://www.sciencedirect.com/science/article/pii/S0022000001917647)
SamiD
CC BY-SA 3.0
2014-02-09T07:28:03.100Z
Thanks @SamiD for the reference. It seems the problem is open even for smaller depths e.g. $\lg^*n$.
Kaveh
CC BY-SA 3.0
2014-02-10T07:48:37.453Z
I guess that is true though I cannot recall where (if anywhere) this is explicitly mentioned as an open question...
SamiD
<cc.complexity-theory><reference-request><circuit-complexity><circuit-depth>
Depth of bounded fan-in circuits for unbounded fan-in circuits
Kaveh
# Depth of bounded fan-in circuits for unbounded fan-in circuits

(Asked by: username_0 on 2014-01-21)

Assume that we have an unbounded fan-in circuit family of depth $d(n)$ and size $s(n)$.

What is *the smallest depth* (in terms of $d(n)$ and $n$ and $s(n)$) bounded fan-in circuit family of size $poly(s)$ for it?

In particular what is the largest depth $d(n)$ for which we know polynomial size unbounded fan-in circuit families of depth $d(n)$ are in $\mathsf{NC^1}$?

**Tags:** cc.complexity-theory, reference-request, circuit-complexity, circuit-depth
> **Comments:**
> **username_1**: Is there any example of a family of circuits for which $d(n) = \omega(1), s(n) = n^{O(1)}$ but no equivalent $\mathsf{AC}^0$ family is known. Yet the computed family of functions is in $\mathsf{NC}^1$.  
> **username_0**: @SamiD, I don't know any natural example, for artificial one we can take a suitable variant of circuit evaluation problem, e.g. circuit evaluation for $AC$ circuits of depth $\lg \lg n$.  
> **username_0**: ps: since the time I have posted the question I have asked a few experts in circuit complexity and the question seems to be open.  
> **username_1**: I thought that class or even its uniform iterated version $\mathsf{FOLL}$ is not known to be comparable even to Logspace (see e.g. http://www.sciencedirect.com/science/article/pii/S0022000001917647)  
> **username_0**: Thanks @SamiD for the reference. It seems the problem is open even for smaller depths e.g. $\lg^*n$.  
> **username_1**: I guess that is true though I cannot recall where (if anywhere) this is explicitly mentioned as an open question...  

---

## 0 answers

