^{n}$.  Then $f^{\ast}$ can only be isolated in $S$ by specifying its value at *every* point!

Luckily, this counterexample leads us to a key observation.  Although $f$ is not isolatable in $S$ by a small number of values, each point function $f_{y}$ *can* be isolated (by its value at $y$), and moreover, $f_{y}$ is quite ‘close’ to $f$.  In fact, if we choose any three distinct strings $x,y,z$, then $f^{\ast}=\operatorname*{MAJ}\left(  f_{x},f_{y},f_{z}\right)  $.  (Of course if $f^{\ast}$ were the identically-zero function, it could be easily specified with classical advice!  But $f^{\ast}$ could have been any function in this example.)

This suggests a new, more indirect approach to our general problem: we try to express $f$ as the pointwise majority vote $$f^{\ast}\left(  x\right)  \equiv\operatorname*{MAJ}\left(  f_{1}\left(
x\right)  ,\ldots,f_{m}\left(  x\right)  \right)  ,$$ of a small number ($m=O\left(  n\right)  $, say) of *other* functions $f_{1},\ldots,f_{m}$ in $S$, where each $f_{i}$ is isolatable in $S$ by specifying at most $k=O\left(  \log\left\vert S\right\vert \right)  $ of its values.  Indeed, we will show this can *always* be done.  We call this key result the *majority-certificates lemma*; we will say more about its proof and its relation to earlier work in Section \[MAJCERDISCUSSION\].

With this lemma in hand, we 