second stage, our goal is just to isolate some *particular* function $f\in S\left[  C\right]  $.  We do this recursively as follows.  If $\left\vert S\left[  C\right]  \right\vert =1$ then we are done.  Otherwise, there exists an input $x$ such that $f\left(  x\right)  =0$ for some $f\in
S\left[  C\right]  $ and $f\left(  x\right)  =1$ for other $f\in S\left[
C\right]  $.  If setting $C\left(  x\right)  :=0$ decreases $\left\vert
S\left[  C\right]  \right\vert $ by at least a factor of $2$, then set $C\left(  x\right)  :=0$; otherwise set $C\left(  x\right)  :=1$.  Since $S\left[  C\right]  $ can halve in size at most $\log_{2}\left\vert
S\right\vert $ times, this procedure terminates after at most $\log
_{2}\left\vert S\right\vert $ steps with $\left\vert S\left[  C\right]
\right\vert =1$.

The end result is a certificate $C$ of size $O\left(  \log\left\vert
S\right\vert \right)  $, which isolates a function $f$ in $S$ for which $w_{f}\leq1/10$.  We have therefore found a pure strategy for Alice that fails with probability at most $1/10$ against $\mathcal{D}$, as desired.

Extension to Real Functions\[REALMAJ\]
======================================

In this section, we extend the majority-certificates lemma from Boolean functions to real-valued functions $f:\left\{  0,1\right\}  ^{n}\rightarrow\left[  0,1\right]  $.  We will need this extension for the application to quantum advice in Section \[QADV\].  In 