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.
No comments:
Post a Comment