\( \def\<#1>{\left<#1\right>} \newcommand{\tens}[1]{\mathsf{#1}} \newcommand{\g}{\tens{C}} \newcommand{\h}{\tens{h}} \newcommand{\C}{\tens{C}} \newcommand{\err}{\epsilon} \newcommand{\maj}{\mathrm{Maj}} \newcommand{\prob}[1]{\mathrm{Pr}\left\{#1\right\}} \newcommand{\euler}{\mathrm{e}} \newcommand{\NN}{\mathbb{N}} \newcommand{\f}{{\cal F}} \newcommand{\pprob}{\mathrm{Pr}} \newcommand{\Z}[2]{Z_{#2}(#1)} \newcommand{\vc}[1]{\mathrm{dim}(#1)} \newcommand{\VC}[1]{\mathrm{VC}(#1)} \)

The BPP vs. P/poly problem and VC-dimension

Let $R$ be a semiring. Recall that a zero-pattern of a sequence $(p_1,\ldots,p_m)$ of $m$ polynomials in $R[x_1,\ldots,x_n]$ is a subset $S\subseteq [m]$ for which there exist $x\in R^n$ and $y\in R$ such that such that $p_i(x)= y$ iff $i\in S$ holds for all $i=1,\ldots,m$. For a set $P\subset R[x_1,\ldots,x_n]$ of polynomials, let $\Z{m}{P}$ denote the maximum possible number of zero-patterns of a sequence of $m$ polynomials from $P$; hence, $1\leq \Z{m}{P}\leq 2^m$. Define the zero-pattern dimension of a set $P$ of polynomials as $\vc{P}=\max\{m\colon \Z{m}{P}=2^m\}$. Let also $\vc{n,d}$ denote the zero-pattern dimension of the set of all polynomials in $R[x_1,\ldots,x_n]$ of degree at most $d$.

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

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$.
Our starting point is the following result of Haussler in statistical learning theory (Corollary 2 on page 114 of this paper).

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$.
Proof: The condition $\prob{p\in P\colon F_x(p)=1}=\prob{p\in P\colon p(x)=f(x)}\geq 2/3$ implies that the expected value $\mu_x:=\mathsf{E}_{p\in P}[F_x(p)]$ is at least $2/3$ for each $x\in X$. Apply Theorem 2 to the family $\f=\f_{f,P}$ with $\err=1/7$ and $\delta=1/2$. The theorem then implies that if we take $m=cD$ for a sufficiently large constant $c$, and if we pick functions $p_1,\ldots,p_m$ independently from $P$, then with probability $\geq 1/2$ we will have \[ \frac{1}{m}\sum_{i=1}^m F_x(p_i) \geq \mu_x-\err\geq 2/3-1/7=11/21 >1/2 \] for all $x\in X$. That is, there must exist $m$ functions $p_1,\ldots,p_m$ in $P$ such that, for every $x\in X$, more than $m/2$ of the values $p_1(x),\ldots,p_m(x)$ will coincide with the correct value $f(x)$. $\Box$

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

Lemma: 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}$.
Thus, we have BPP$\subseteq$ P/poly for circuits over any semiring, where $\vc{n,d}$ is polynomial in $n$ and in $\log d$.

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