<p>Any <span class="math-container">$NC^0$</span> circuit family <span class="math-container">$(C_n)_{n \geq 0}$</span> can only depend on a constant number of bits, whether they're input bits or random bits. Let's say there are <span class="math-container">$n$</span> inputs and <span class="math-container">$r$</span> random bits, but our circuit <span class="math-container">$C_n$</span> only depends on <span class="math-container">$n_0$</span> inputs and <span class="math-container">$r_0$</span> random bits, which are both fixed independent of <span class="math-container">$n$</span>. So, create <span class="math-container">$2^{r_0}$</span> copies of <span class="math-container">$C_n$</span> and hardwire each possible combination of the <span class="math-container">$r_0$</span> random bits into each copy of the circuit. Note that <span class="math-container">$2^{r_0}$</span> is still a constant, so we can take the majority of these copies of the circuit and get our answer deterministically. The depth of such a circuit will be the depth of <span class="math-container">$C_n$</span> plus the depth of the MAJ circuit, which is still a constant, so the resulting deterministic computation is still in <span class="math-container">$NC^0$</span>.</p>
<p>For an example of a constant-depth circuit class that isn't known to be closed under randomness, look at <span class="math-container">$CC^0$</span>, the class of unbounded-fanin polynomially-sized constant-depth circuits of <span class="math-container">$MOD_m$</span> gates for fixed <span class="math-container">$m$</span>. It is known that <span class="math-container">$BPCC^0 = BPACC^0 = ACC^0$</span> (see Hansen and Koucký below), so derandomizing <span class="math-container">$CC^0$</span> is equivalent to showing <span class="math-container">$CC^0 = ACC^0$</span>.</p>
<p><em>Hansen, Kristoffer Arnsfelt; Koucký, Michal</em>, <a href="https://doi.org/10.1007/s00037-010-0287-z" rel="nofollow noreferrer"><strong>A new characterization of (\text{ACC}^{0}) and probabilistic (\text{CC}^{0})</strong></a>, Comput. Complexity 19, No. 2, 211-234 (2010). <a href="https://zbmath.org/?q=an:1213.68262" rel="nofollow noreferrer">ZBL1213.68262</a>.</p>

CC BY-SA 4.0
2023-02-14T16:34:33.523Z
2023-02-14T16:34:33.523Z
Jake
<p>In</p>
<blockquote>
<p>Ajtai and Ben-Or. A theorem on probabilistic constant depth
Computations. STOC '84, 1984</p>
</blockquote>
<p>Ajtai and Ben-Or show a non-uniform derandomization of BPAC0.</p>
<p>Is there a similar relation known for probabilistic and non-uniform NC0? Or is it an open problem?</p>

<cc.complexity-theory><circuit-complexity><advice-and-nonuniformity><probabilistic-circuits>
NC0 randomnes vs. non-uniformity
user68538
# NC0 randomnes vs. non-uniformity

(Asked by: username_0 on 2023-02-13)

In

> Ajtai and Ben-Or. A theorem on probabilistic constant depth
> Computations. STOC '84, 1984

Ajtai and Ben-Or show a non-uniform derandomization of BPAC0.

Is there a similar relation known for probabilistic and non-uniform NC0? Or is it an open problem?

**Tags:** cc.complexity-theory, circuit-complexity, advice-and-nonuniformity, probabilistic-circuits

---

## 1 answers

### Answer by username_1 on 2023-02-14. Score: 2

Any $NC^0$ circuit family $(C\_n)\_{n \geq 0}$ can only depend on a constant number of bits, whether they're input bits or random bits. Let's say there are $n$ inputs and $r$ random bits, but our circuit $C\_n$ only depends on $n\_0$ inputs and $r\_0$ random bits, which are both fixed independent of $n$. So, create $2^{r\_0}$ copies of $C\_n$ and hardwire each possible combination of the $r\_0$ random bits into each copy of the circuit. Note that $2^{r\_0}$ is still a constant, so we can take the majority of these copies of the circuit and get our answer deterministically. The depth of such a circuit will be the depth of $C\_n$ plus the depth of the MAJ circuit, which is still a constant, so the resulting deterministic computation is still in $NC^0$.

For an example of a constant-depth circuit class that isn't known to be closed under randomness, look at $CC^0$, the class of unbounded-fanin polynomially-sized constant-depth circuits of $MOD\_m$ gates for fixed $m$. It is known that $BPCC^0 = BPACC^0 = ACC^0$ (see Hansen and Koucký below), so derandomizing $CC^0$ is equivalent to showing $CC^0 = ACC^0$.

*Hansen, Kristoffer Arnsfelt; Koucký, Michal*, [**A new characterization of (\text{ACC}^{0}) and probabilistic (\text{CC}^{0})**](https://doi.org/10.1007/s00037-010-0287-z), Comput. Complexity 19, No. 2, 211-234 (2010). [ZBL1213.68262](https://zbmath.org/?q=an:1213.68262).


---

