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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Aug 11, 2010 at 3:29
  • $\begingroup$ @RyanWilliiams is it known $PAC^0⊈BPAC^0$ and $PAC^0⊈quasiAC^0$ (uniform case)? What is the standard reference for the class $BPAC^0$ where I can find definition of it? $\endgroup$
    – Turbo
    Commented Mar 31 at 15:59

You must log in to answer this question.