MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 3 down vote accepted

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.

share|cite|improve this answer
What I mean by "0-ary random-bool gates" is gates with 0 inputs that output a uniform random boolean value independently of each other, so your formulation would be equivalent. (and probably easier to work with) – Ricky Demer Aug 11 '10 at 3:29

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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