Specifically I'm thinking about NC$^1$/poly and NC$^1$/rpoly (randomized advice). Are there any statements like

"If $\{C_n\}$ is a family of NC$^1$/(r)poly circuits with depth $C\log n$, then there exists a family $\{\tilde{C}_n\}$ of NC$^1$/(r)poly circuits with depth $\tilde{C}\log n$ such that $\tilde{C} < 1$ and $C_n(x) = \tilde{C}_n(x)$"?

Or would that be too powerful?

  • $\begingroup$ What is randomized advice? Is that stronger or weaker than normal advice? $\endgroup$ May 4, 2022 at 6:51
  • $\begingroup$ As far as I can tell, with usual advice, i.e., non-uniform $\mathrm{NC}^1$ circuits, the statement is as false as possible: for any $d<n-\log n$ or so (such as $C\log n$), there exist functions computable by circuits of depth $d+1$, but not by circuits of depth $d$. Proof: if not, then all Boolean functions are computable by circuits of depth $d$, and therefore size $2^d$, as you can just take an arbitrary circuit, and keep reducing subcircuits of depth $d+1$ to $d$ until none remain. However, almost all functions require circuit size $\Omega(2^n/n)$. $\endgroup$ May 4, 2022 at 7:04
  • $\begingroup$ Of course, with $\tilde C<1$ as written, it’s much easier to disprove: a circuit of depth $\tilde C\log n$ with $\tilde C<1$ has size at most $n^{\tilde C}<n$, hence it cannot even depend on all bits of the input. Thus, even simple functions such as $\mathrm{AND}(x_1,\dots,x_n)$ have no circuits of depth $\tilde C\log n$. $\endgroup$ May 4, 2022 at 9:03
  • $\begingroup$ I see, this can't be true then. Thanks. $\endgroup$ May 4, 2022 at 11:52


Your Answer

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