# NC0 randomnes vs. non-uniformity

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?

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$$.