---
title: "SU-CS254B MAY072025"
source: https://www.jemoka.com/posts/kbhsu_cs254b_may072025/
date: 2025-05-07
---

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