<p>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 <em>all</em> $2^n$ inputs of length $n$ simultaneously with nonzero probability, and in particular, there <em>exists</em> such a sequence. We can hardwire it into the circuit.</p>

<p>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}$.</p>

<p>The proof is more complicated for $\mathrm{AC^0}$, because this class does <em>not</em> 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.)</p>

CC BY-SA 3.0
2017-03-14T15:40:11.063Z
2017-03-14T15:40:11.063Z
Emil Jeřábek
<p>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}$.</p>

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

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

<p>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$.</p>

<p>A relevant post on the subject: <a href="https://mathoverflow.net/questions/35184/use-of-randomness-in-constant-parallel-time">https://mathoverflow.net/questions/35184/use-of-randomness-in-constant-parallel-time</a></p>

CC BY-SA 3.0
2017-03-11T10:13:37.260Z
What drives your hunch on connectivity?
Michaël Cadilhac
CC BY-SA 3.0
2017-03-11T10:46:36.467Z
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
CC BY-SA 3.0
2017-03-11T11:28:08.603Z
@MichaëlCadilhac it seems non completly impossible that we can simulate a random walk in BPNC1. A standard randomized algorithm for s,t-con follow. Not sure how to do that though.
C.P.
CC BY-SA 3.0
2017-03-11T11:29:43.410Z
@EmilJeřábek I change the post to clarify that I do talk about non-uniform class. I don't see how it is obvious, the proof of Ajtai and Ben-Or is not long and not very difficult but not obvious to me. Maybe I missing a point somehow ?
C.P.
CC BY-SA 3.0
2017-03-11T11:45:02.723Z
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
CC BY-SA 3.0
2017-03-11T16:34:36.873Z
@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.
CC BY-SA 3.0
2017-03-13T15:18:38.600Z
@EmilJeřábek: Seems you should post that as an answer.
Joshua Grochow
CC BY-SA 3.0
2017-03-13T16:49:45.407Z
@JoshuaGrochow I voted to close as not research-level. Clearly, I shouldn’t simultaneously do that, and post an answer.
Emil Jeřábek
CC BY-SA 3.0
2017-03-13T16:55:35.537Z
@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
CC BY-SA 3.0
2017-03-14T10:19:25.787Z
@EmilJeřábek Given that this has gathered 5 upvotes, it may not be the general consensus that having an answer written down is entirely worthless.  Alternatively, we may move that to Math SE.
Michaël Cadilhac
CC BY-SA 3.0
2017-03-14T15:23:48.713Z
All right, then.
Emil Jeřábek
<circuit-complexity><randomized-algorithms>
Randomness and small circuits complexity classes
C.P.
# Randomness and small circuits complexity classes

(Asked by: username_0 on 2017-03-11)

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>

**Tags:** circuit-complexity, randomized-algorithms

> **Comments:**
> **username_1**: What drives your hunch on connectivity?  
> **username_2**: Are you asking about *uniform* circuit classes? It’s fairly obvious that *nonuniform* classes like $\mathrm{NC^1}$ are closed under the BP operator.  
> **username_0**: @MichaëlCadilhac it seems non completly impossible that we can simulate a random walk in BPNC1. A standard randomized algorithm for s,t-con follow. Not sure how to do that though.  
> **username_0**: @EmilJeřábek I change the post to clarify that I do talk about non-uniform class. I don't see how it is obvious, the proof of Ajtai and Ben-Or is not long and not very difficult but not obvious to me. Maybe I missing a point somehow ?  
> **username_2**: 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}$.)  
> **username_0**: @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.  
> **username_3**: @EmilJeřábek: Seems you should post that as an answer.  
> **username_2**: @JoshuaGrochow I voted to close as not research-level. Clearly, I shouldn’t simultaneously do that, and post an answer.  
> **username_3**: @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.  
> **username_1**: @EmilJeřábek Given that this has gathered 5 upvotes, it may not be the general consensus that having an answer written down is entirely worthless.  Alternatively, we may move that to Math SE.  
> **username_2**: All right, then.  

---

## 1 answers

### Answer by username_2 on 2017-03-14. Score: 10 | Accepted answer

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.)


---

