hardcore lemma Goal: can we find a single set of x \in \left\{\pm 1\right\}^{h} = H where |H| \geq \frac{\delta}{2}, such that for f : \left\{\pm 1 \right\}^{h} \to \left\{\pm 1\right\}, for all circuits of size S, commuting f on inputs in H is hopelessly hard (i.e., the \mathbb{Pr}_{x \in H} \left[f\left(x\right) =c\left(x\right)\right] \leq \frac{1}{2} + \frac{\varepsilon}{2} \implies \mathbb{E}_{x \sim H} \left[f\left(x\right) c\left(x\right)\right] \leq \varepsilon. H, the “hardcore set” of circuit S, exists! If f is such that \text{corr}\left(f,s\right) \leq 1- \delta, a “hardcore set” H \subseteq \left\{\pm 1\right\}^{n} of size \geq \frac{\delta}{2} 2^{n} always exists. This is a certificate for hardness! In particular: \text{corr}_{H}\left(f, S&rsquo;\right) \leq \varepsilon, where S&rsquo; = \frac{\epsilon^{\delta}}{\log \left( ?\right)}S. yao’s xor theorem \begin{equation} \text{cor}\left(f, s\right) < 1-\delta \implies \text{corr}\left(f^{\oplus k}, s’\right) \leq \left(1 - \frac{\delta}{2}\right)^{k} + \varepsilon \end{equation} where S&rsquo; = \frac{\varepsilon}{\log \left(\frac{1}{\delta}\right)} S where corr a,b where ∀ \text{ckts, sizeb},Pr[f(x) ≠ c(x)]$$.