# Randomness and small circuits complexity classes

Let $\mathcal{C}$ be a complexity class and $\textrm{BP-}\mathcal{C}$ be the randomized counterpart of $\mathcal{C}$ defined as $\textrm{BPP}$ with respect to $\textrm{P}$. More formally we provide polynomially many random bit and we accept an input iff the probability to accept is over $\frac{2}{3}$.

It is known that for non-uniform circuits class we have $\textrm{BPAC}^0=\textrm{AC}^0$:

Miklós Ajtai, Michael Ben-Or: A Theorem on Probabilistic Constant Depth Computations STOC 1984: 471-474

Are generalizations of this theorem known ? For instance, do we know if $\mathrm{BPNC}^1=\mathrm{NC}^1$ (still in the non-uniform setting)? This last question seems somehow non trivial to me since it seems plausible that for instance $s,t\textrm{-Connectivity}$ is in $\textrm{BPNC}^1$.

A relevant post on the subject: https://mathoverflow.net/questions/35184/use-of-randomness-in-constant-parallel-time

• What drives your hunch on connectivity? – Michaël Cadilhac Mar 11 '17 at 10:13
• Are you asking about uniform circuit classes? It’s fairly obvious that nonuniform classes like $\mathrm{NC^1}$ are closed under the BP operator. – Emil Jeřábek Mar 11 '17 at 10:46
• Just use the same argument as for P/poly. You only need the majority function, which is definable in $\mathrm{TC^0\subseteq NC^1}$. (Ajtai and Ben-Or need more work as majority is not available in $\mathrm{AC^0}$.) – Emil Jeřábek Mar 11 '17 at 11:45
• @EmilJeřábek you are perfectly right. For every non-unifom circuit class above $\textrm{TC}^0$ we have $\textrm{BP}-\mathcal{C}=\mathcal{C}$. Thank you very much. – C.P. Mar 11 '17 at 16:34
• @EmilJeřábek: Ah, I see. I think it's borderline; it's obviously not a research question, but it was clearly asked in earnest by someone with some research experience in complexity, who was simply misled by trying to extend Ajtai-Ben-Or rather than using the more straightforward approach. – Joshua Grochow Mar 13 '17 at 16:55

Most nonuniform complexity classes—$\mathrm{NC^1}$ included—are closed under the $\mathrm{BP}$ operator by the same argument as $\mathrm{BPP\subseteq P/poly}$: using the Chernoff–Hoeffding bound, the probability of error can be reduced below $2^{-n}$ by running $O(n)$ instances of the circuit with independent random bits in parallel, and taking a majority vote; then by the union bound, a sequence of random bits gives the correct result for all $2^n$ inputs of length $n$ simultaneously with nonzero probability, and in particular, there exists such a sequence. We can hardwire it into the circuit.
This argument applies to any class of circuits that is closed under taking majority of $O(n)$ parallel copies of a circuit, and fixing input gates to constants. In practice, this means any decent nonuniform class above $\mathrm{TC^0}$, as majority is computable in $\mathrm{TC^0}$.
The proof is more complicated for $\mathrm{AC^0}$, because this class does not compute the majority function. (While I haven’t seen the Ajtai and Ben-Or paper, I’d guess they use some sort of approximate majority.)