Skip to main content
3 of 4
added 51 characters in body; edited tags
Kaveh
  • 21.8k
  • 8
  • 84
  • 185

Turning unbounded fan-in circuits to bounded fan-in circuits

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

What is the best depth (in $d(n)$ and $n$) $poly(n)$ size bounded fan-in circuit family that can be obtained for it?

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

Kaveh
  • 21.8k
  • 8
  • 84
  • 185