refer directly to a set of Boolean functions on $n$ variables, with the quantification over $n$ being understood.

By a *certificate*, we mean a partial Boolean function $C:\left\{
0,1\right\}  ^{n}\rightarrow\left\{  0,1,\ast\right\}  $.  The *size* of $C$, denoted $\left\vert C\right\vert $, is the number of inputs $x$ such that $C\left(  x\right)  \in\left\{  0,1\right\}  $.  A Boolean function $f:\left\{  0,1\right\}  ^{n}\rightarrow\left\{  0,1\right\}  $ is *consistent* with $C$ if $f\left(  x\right)  =C\left(  x\right)
$ whenever $C\left(  x\right)  \in\left\{  0,1\right\}  $.  Given a set $S$ of Boolean functions and a certificate $C$, let $S\left[  C\right]  $ be the set of all functions $f\in S$ that are consistent with $C$.  Say that a function $f\in S$ is *isolated in* $S$ by the certificate $C$ if $S\left[  C\right]  =\left\{  f\right\}  $.

We now prove a lemma that represents one of the main tools of this paper.

\[Majority-Certificates Lemma\]\[majcer\]Let $S$ be a set of Boolean functions $f:\left\{  0,1\right\}  ^{n}\rightarrow\left\{  0,1\right\}  $, and let $f^{\ast}\in S$.  Then there exist $m=O\left(  n\right)  $ certificates $C_{1},\ldots,C_{m}$, each of size $k=O\left(  \log\left\vert S\right\vert
\right)  $, and functions $f_{1}, \ldots, f_{m} \in S$, such that

1.  $S\left[  C_{i}\right]  = \{f_{i}\}$ all $i\in\left[  m\right]  $;

2.  $\operatorname*{MAJ}\left(  f_{1}\left(  x\right)  ,\ldots
    ,f_{m}\left(  x\right)  \right)  