Skip to main content
Tweeted twitter.com/#!/StackCSTheory/status/425888374915100672
added 9 characters in body
Source Link
Kaveh
  • 21.8k
  • 8
  • 84
  • 185

Turning unbounded Depth of bounded fan-in circuits to boundedfor unbounded fan-in circuits

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

What is the bestsmallest depth (in terms of $d(n)$ and $n$) and $poly(n)$ size$s(n)$) bounded fan-in circuit family that can be obtainedof size $poly(s)$ for it?

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

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

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

added 51 characters in body; edited tags
Source Link
Kaveh
  • 21.8k
  • 8
  • 84
  • 185

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

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?

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

added 51 characters in body; edited tags
Source Link
Kaveh
  • 21.8k
  • 8
  • 84
  • 185

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

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

Assume that we have an unbounded fan-in circuit of depth $d$ and poly size. What is the best depth poly size bounded fan-in circuit that can be obtained for it?

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?

Source Link
Kaveh
  • 21.8k
  • 8
  • 84
  • 185
Loading