=f^{\ast}\left(  x\right)  $ for all $x\in\left\{  0,1\right\}  ^{n}$.

Our proof of Lemma \[majcer\] relies on the following claim.

\[heurpart\] Let $\mathcal{D}$ be any distribution over inputs $x\in\{0,1\}^{n}$. Then there exists a function $f\in S$ such that

-   $f$ is isolatable in $S$ by a certificate $C$ of size $k=O\left(
    \log\left\vert S\right\vert \right)  $;

-   $\Pr_{x\sim\mathcal{D}}[f(x)\neq f^{\ast}(x)]\leq\frac{1}{10}$.

Lemma \[majcer\] follows from Claim \[heurpart\] by a boosting-type argument, as follows. Consider a two-player game where:

-   Alice chooses a certificate $C$ of size $k$ that isolates some $f\in S$, and

-   Bob simultaneously chooses an input $x\in\left\{  0,1\right\}  ^{n}$.

Alice wins the game if $f\left(  x\right)  =f^{\ast}\left(  x\right)  $. Claim \[heurpart\] tells us that for every mixed strategy of Bob (i.e., distribution $\mathcal{D}$ over inputs), there exists a pure strategy of Alice that succeeds with probability at least $0.9$ against $\mathcal{D}$.  Then by the Minimax Theorem, there exists a mixed strategy for Alice—that is, a probability distribution $\mathcal{C}$ over certificates—that allows her to win with probability at least $0.9$ against *every* pure strategy of Bob.

Now suppose we draw $C_{1},\ldots,C_{m}$ independently from $\mathcal{C}$, isolating functions $f_{1},\ldots,f_{m}$ in $S$. Fix an input $x\in\left\{
0,1\right\}  ^{n}$; then by the success of Alice’s strategy against 