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?


1 Answer 1


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}), Comput. Complexity 19, No. 2, 211-234 (2010). ZBL1213.68262.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.