4
$\begingroup$

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?

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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) $\endgroup$
    – user5810
    Aug 11, 2010 at 3:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.