‘boost’ this fact into the desired majority-representation of $f^{\ast}$.  We note that Nisan used the Minimax Theorem for boosting in a similar way, in his alternative proof of Impagliazzo’s ‘hard-core set theorem’ (see [@imp_hardcore]).

The majority-certificates lemma is also reminiscent of Bshouty et al.’s algorithm [@bshouty], for learning small circuits in the complexity class $\mathsf{ZPP}^{\mathsf{NP}}$.  Our lemma lacks the algorithmic component of this earlier work, but unlike Bshouty et al., we do not require the functions being learned to come with any succinct labels (such as circuit descriptions).

Organization of the Paper
-------------------------

In Section \[MAJCER\], we prove the Boolean majority-certificates-lemma. In Section \[REALMAJ\], we give our real-valued generalization of this lemma, and in Section \[QADV\] we use it to prove Theorem \[mainthm1\], and state some consequences for quantum complexity theory. Theorem \[mainthm0\] is proved in Section \[LOCALHAM\]. Section \[NERD\] contains some further results for quantum complexity, and the Appendices provide some additional applications of and perspectives on the majority-certificates lemma.

The Majority-Certificates Lemma\[MAJCER\]
=========================================

A *Boolean concept class* is a family of sets $\left\{  S_{n}\right\}
_{n\geq1}$, where each $S_{n}$ consists of Boolean functions $f:\left\{
0,1\right\}  ^{n}\rightarrow\left\{  0,1\right\}  $ on $n$ variables.  Abusing notation, we will often use $S$ to 