# Depth of bounded fan-in circuits for unbounded fan-in circuits

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}$?

• 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 Feb 8 '14 at 17:37
• @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 Feb 8 '14 at 21:22
• 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 Feb 8 '14 at 21:24
• I thought that class or even its uniform iterated version $\mathsf{FOLL}$ is not known to be comparable even to Logspace (see e.g. sciencedirect.com/science/article/pii/S0022000001917647) – SamiD Feb 9 '14 at 7:06
• Thanks @SamiD for the reference. It seems the problem is open even for smaller depths e.g. $\lg^*n$. – Kaveh Feb 9 '14 at 7:28