Let AC0 be the set of decision problems solvable by a logspace-uniform family of constant-depth, polynomial-width boolean circuits with unbounded fanin. Let BPAC0 be the modification of AC0 allowing it to use 0-ary random-bool gates, such that the probability of giving the wrong answer is less than 1/3. Is it known whether BPAC0 equals AC0? (This seems like an easier version of BPP =?= P)


If not, is it known for the AC0 analogues of ZPP and RP, or are any implications known either to or from it?



Use of randomness in constant parallel time
Not sure what you mean by "0-ary random-bool gates", but I think you mean: take a circuit $C$ with $n$ *real* inputs and $poly(n)$ *extra* inputs. For each input $x$ of length $n$, the "probabilistic" circuit $C$ is said to output $b$ on $x$ iff when we attach $x$ to the real inputs, and put a uniform random input on the extra inputs, the probability $C(x)=b$ is at least $2/3$.


Given that, it is known that $BPAC0 \subset non-uniform-AC0$. This was first proved by Ajtai and Ben-Or in:



> 
> Miklós Ajtai, Michael Ben-Or: A Theorem on Probabilistic Constant Depth Computations STOC 1984: 471-474
> 
> 
> 


A very short and sweet paper. However it only results in non-uniform constant depth circuits. I believe that the best known uniform simulation of $BPAC0$ is with *quasipolynomial* size constant depth circuits, by Klivans:



> 
> Adam Klivans: On the Derandomization of Constant Depth Circuits. RANDOM-APPROX 2001: 249-260
> 
> 
> 


Under some very weak hardness assumptions, $BPAC0 = AC0$, see:



> 
> Emanuele Viola: Hardness vs. Randomness within Alternating Time. IEEE Conference on Computational Complexity 2003
> 
> 
> 


Edit: I should also mention the work of Nisan (1991) "Pseudorandom bits for constant depth circuits" which really made a lot of the later work possible.


