Our goal is to prove the following theorem (where we assume that deterministic circuits are allowed to use majority vote to output their values).

Our starting point is the following result of Haussler in statistical learning theory (Corollary 2 on page 114 of this paper).Theorem 1:$\mathbf{BPP}\subseteq \mathbf{P}/\mathrm{poly}$ holds for circuits over any semiring $R$, where $\vc{n,d}$ is polynomial in $n$ and $\log d$.

The *Vapnik-Chervonenkis dimension* $\VC{\f}$ of a family $\f$ of $0$-$1$ valued functions $F:A\to\{0,1\}$ is the maximum cardinality $|B|$ of a subset $B\subseteq A$ such that
for every function $H:B\to\{0,1\}$, there is a function $F\in\f$ whose restriction onto $B$ coincides with $H$, that is, $F(a)=H(a)$ for all $a\in B$.

Theorem 2[Haussler]: Let $\f$ be a family of functions $F:A\to\{0,1\}$. Assume that $\f$ has finite VC dimension $D$. Then for any probability distribution $\pprob:A\to[0,1]$ and any $\err,\delta >0$, and any \[ m\geq \frac{64}{\err^2}\left(2D\ln\frac{16\euler}{\err} +\ln\frac{8}{\delta}\right) \] the following holds: if $m$ points $a_1,\ldots,a_m$ are independently drawn from $A$, then \[ \prob{\forall F\in \f:\ \left|\frac{1}{m}\sum_{i=1}^m F(a_i)-\mu_F\right|\leq \err}\geq 1-\delta\,, \] where $\mu_F:=\sum_{a\in A} F(a)\cdot \prob{a}$ is the expected value.

Important in the context of the **BPP** vs. **P**/poly problem is the following consequence of Haussler's theorem (observed by Cucker et al., Theorem 4 in
this paper), which extends the majority rule to functions over *infinite* domains.

Let $f:X\to Y$ be a function, and $P$ some set of functions $p:X\to Y$. Associate with every $x\in X$ the $0$-$1$ function $F_{x}:P\to\{0,1\}$ defined by $F_{x}(p)=1$ iff $p(x)=f(x)$, and let $\f_{f,P}$ be the family of all such functions.

Corollary 1:Let $\pprob:P\to[0,1]$ be a probability distribution such that $ \prob{p\in P\colon p(x)=f(x)}\geq 2/3 $ holds for every $x\in X$. Suppose that the family $\f_{f,P}$ has finite VC dimension $D$. Then there exist $m=O(D)$ functions $p_1,\ldots,p_m$ in $P$ such that $\maj(p_1(x),\ldots,p_m(x))=f(x)$ holds for all $x\in X$.

Theorem 1 is now a direct consequence of the following lemma.

Thus, we haveLemma:Let $R$ be a semiring, and $f\in R[x_1,\ldots,x_n]$. If $f$ can be computed by a probabilistic circuit of size $t$, then $f$ can be also computed by a deterministic majority-output circuit of size $O(tm)$, where $m=\vc{n,2^t}$.

**Proof:**
Let $\C$ be a probabilistic circuit of size $t$ computing $f$ with two sided error $1/3$, and let $D=\vc{n,2^t}$. Hence, $D=\vc{P}$, where
$P\subseteq R[x_1,\ldots,x_n]$ is the family of all polynomials of degree at most $2^t$.
Let $p\in R[x_1,\ldots,x_n]$ be the (random) polynomial computed by $\C$. Since no circuit of size $t$ can compute a polynomial of degree larger than $2^t$, all realizations of $p$ must be polynomials from $P$.
Associate with every $x\in R^n$ a $0$-$1$ function $F_{x}:P\to\{0,1\}$ defined by $F_{x}(p)=1$ iff $p(x)=f(x)$, and let $\f_{f,P}$ be the family of all such functions. It is easy to see that
\[
\VC{\f_{f,P}}\leq \vc{P}
\]
holds. Indeed, if
$m=\VC{\f_{f,P}}$, then there is sequence $(p_1,\ldots,p_m)$ of polynomials in $P$ such that for every subset $S\subseteq [m]$ there is an $x\in R^n$ such that $F_x(p_i)=1$ (and, hence, also $p_i(x)=f(x)$) holds iff $i\in S$. By taking $y:=f(x)$, we have that $p_i(x)=y$ holds iff $i\in S$. Thus, the sequence $(p_1,\ldots,p_m)$ contains all $2^m$ zero-patterns, implying that $\vc{n,2^t}=\vc{P}\geq m$, as desired.

Since the (probabilistic) circuit $\C$ computes $f$ with two-sided error $1/3$, $\prob{p\in P\colon p(x)=f(x)}\geq 2/3$ holds for every $x\in R^n$. So, Corollary 1 gives us $m=O(D)$ realizations $p_1,\ldots,p_m$ of the random polynomial $p$ such that $\maj(p_1(x),\ldots,p_m(x))=f(x)$ holds for all $x\in R^n$. Since each $p_i$ is computed by a realization $C_i$ of the probabilistic circuit $\C$ of size $t$, the obtained deterministic circuit $C(x)=\maj(C_1(x),\ldots,C_m(x))$ (with a majority output gate) has size at most $tm+1=O(tD)$ and computes our polynomial $f$, as desired. $\Box$

S. Jukna, March 21, 2017