<p>Specifically I'm thinking about NC<span class="math-container">$^1$</span>/poly and NC<span class="math-container">$^1$</span>/rpoly (randomized advice). Are there any statements like</p>
<p>&quot;If <span class="math-container">$\{C_n\}$</span> is a family of NC<span class="math-container">$^1$</span>/(r)poly circuits with depth <span class="math-container">$C\log n$</span>, then there exists a family <span class="math-container">$\{\tilde{C}_n\}$</span> of NC<span class="math-container">$^1$</span>/(r)poly circuits with depth <span class="math-container">$\tilde{C}\log n$</span> such that <span class="math-container">$\tilde{C} &lt; 1$</span> and <span class="math-container">$C_n(x) = \tilde{C}_n(x)$</span>&quot;?</p>
<p>Or would that be too powerful?</p>

CC BY-SA 4.0
2022-05-04T06:51:40.460Z
What is randomized advice? Is that stronger or weaker than normal advice?
Emil Jeřábek
CC BY-SA 4.0
2022-05-04T07:04:28.533Z
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)$.
Emil Jeřábek
CC BY-SA 4.0
2022-05-04T09:03:34.423Z
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$.
Emil Jeřábek
CC BY-SA 4.0
2022-05-04T11:52:40.980Z
I see, this can't be true then. Thanks.
trillianhaze
<cc.complexity-theory><circuit-complexity><circuit-depth>
Does advice reduce depth?
trillianhaze
# Does advice reduce depth?

(Asked by: username_0 on 2022-05-04)

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?

**Tags:** cc.complexity-theory, circuit-complexity, circuit-depth

> **Comments:**
> **username_1**: What is randomized advice? Is that stronger or weaker than normal advice?  
> **username_1**: 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)$.  
> **username_1**: 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$.  
> **username_0**: I see, this can't be true then. Thanks.  

---

## 0 answers

