10
$\begingroup$

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

Improve this question
$\endgroup$
6
  • $\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
    Commented Feb 8, 2014 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
    Commented Feb 8, 2014 at 21:22
  • 1
    $\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
    Commented Feb 8, 2014 at 21:24
  • 1
    $\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
    Commented Feb 9, 2014 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
    Commented Feb 9, 2014 at 7:28

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.