$x$, and applying a Chernoff bound,$$\Pr_{f_{1},\ldots,f_{m}\sim\pi}\left[  \operatorname*{MAJ}\left(  f_{1}\left(
x\right)  ,\ldots,f_{m}\left(  x\right)  \right)  \neq f^{\ast}(x)\right]
<\frac{1}{2^{n}},$$ provided we choose $m=O\left(  n\right)  $ suitably.  But by the union bound, this means there must be a *fixed* choice of $C_{1},\ldots
,C_{m}$ such that $\operatorname*{MAJ}\left(  f_{1},\ldots,f_{m}\right)
\equiv f^{\ast}(x)$, where each $f_{i}$ is isolated in $S$ by $C_{i}$. This proves Lemma \[majcer\], modulo the Claim.

\[Proof of Claim \[heurpart\]\]By symmetry, we can assume without loss of generality that $f^{\ast}$ is the identically-zero function.  Given the mixed strategy $\mathcal{D}$ of Bob, we construct the certificate $C$ as follows.  Initially $C$ is empty: that is, $C\left(  x\right)  =\ast$ for all $x\in\left\{  0,1\right\}  ^{n}$.  In the first stage, we draw $t=O\left(
\log\left\vert S\right\vert \right)  $ inputs $x_{1},\ldots,x_{t}$ independently from $\mathcal{D}$.  For any $f:\{0,1\}^{n}\rightarrow
\{0,1\}$, let$$w_{f}:=\Pr_{x\sim\mathcal{D}}\left[  f\left(  x\right)  =1\right]  .$$ Now suppose $f$ is such that $w_{f}>0.1$.  Then$$\Pr_{x_{1},\ldots,x_{t}\sim\mathcal{D}}\left[  f\left(  x_{1}\right)
=0\wedge\cdots\wedge f\left(  x_{t}\right)  =0\right]  <0.9^{t}\leq\frac
{1}{\left\vert S\right\vert },$$ provided $t\geq\log_{10/9}\left\vert S\right\vert $.  So by the union bound, there must be a *fixed* choice of $x_{1},\ldots,x_{t}$ that kills off every $f\in S$ such that $w_{f}>0.1$—that is, such that $f\left(
x_{1}\right)  =\cdots=f\left(  x_{t}\right)  =0$ implies $w_{f}\leq0.1$.  Fix that $x_{1},\ldots,x_{t}$, and set $C\left(  x_{i}\right)  :=0$ for all $i\in\left[  t\right]  $.

In the 