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

  • $\begingroup$ 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$. $\endgroup$ – SamiD Feb 8 '14 at 17:37
  • $\begingroup$ @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$. $\endgroup$ – Kaveh Feb 8 '14 at 21:22
  • $\begingroup$ 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. $\endgroup$ – Kaveh Feb 8 '14 at 21:24
  • $\begingroup$ 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) $\endgroup$ – SamiD Feb 9 '14 at 7:06
  • $\begingroup$ Thanks @SamiD for the reference. It seems the problem is open even for smaller depths e.g. $\lg^*n$. $\endgroup$ – Kaveh Feb 9 '14 at 7:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.