Use of randomness in constant parallel time 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?
 A: 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.
