We wish to compute boolean functions by circuits, or more generally, compositions of simple boolean functions (gates). Suppose we are given a function which is hard to approximate by any small-size circuit. That is, any small-size circuit fails to compute the given function on certain fraction (say 1/10) of the inputs. There could be two possibilities:
- There is a subset of the inputs (say 1/5 fraction of the inputs) such that, when the function is restricted to these inputs, any small-size circuit fails to compute on almost 1/2 of these inputs.
- Different circuits fails to computes the function on different subsets of the inputs.
Impagliazzo Hardcore Lemma says that every hard function has the first case. That is, every hard function has a hardcore subset such that the restricted function becomes extremely hard to compute.
Definition. We say a function \(f\colon\{0,1\}^n\to\{0,1\}\) is \(\delta\)-hard for circuits of size \(s\) if, for any circuit \(C\) of size at most \(s\), it fails to compute \(f\) on at least \(\delta\) fraction of the inputs. That is, for \(x\sim \{0,1\}^n\),
\[
Pr [C(x) \neq f(x)] \geq \delta.
\]
Definition. We say a distribution \(D\) over \(\{0,1\}^n\) is has density \(\delta\) if for every \(x\in \{0,1\}^n\), we have \(Pr[D = x] \leq 1/ \delta 2^{n}\).
For example, a uniform (flat) distribution over a subset of size \(2^n/10\) has density \(1/10\). It is easy to see that, a convex combination of \(\delta\)-density distributions is also a \(\delta\)-density distribution.
Hardcore Lemma (Distribution Format). Let \(f\) be a \(\delta\)-hard function for circuits of size \(s\). Then there exists a \(\delta\)-density distribution such that, for any circuit of size \(s’ \leq \epsilon^2 s/100n\),
\[
Pr [C(x) \neq f(x)] \geq 1/2 – \epsilon.
\]
Proof.
Let \(f\) be a \(\delta\)-hard function. Consider a two-player game where in each round:
- Player A chooses a \(\delta\)-density distributions \(D\).
- Player B chooses a size-\(s’\) circuit \(C\).
The payoff from Player A to Player B is \(Pr [C(x) = f(x)]\) where \(x\sim D\). Player A tries to come up with a distribution that is hard to approximate by size-\(s’\) circuits. Player B tries to maximize the payoff by giving a circuit computing \(f\) well with respect to the distribution from Player A.
For contradiction, we assume that
- for every \(\delta\)-density distribution \(D\) (chosen by Player A),
- there exists a circuit \(C\) (found by Player B), such that
\[
Pr [C(x) \neq f(x)] < 1/2 - \epsilon.
\]
We wish to construct a circuit which computes [latex]f[/latex] well, contradicting the [latex]\delta[/latex]-hardness of [latex]f[/latex].
Since this is a zero-sum game, we can apply von Neumann's Min-Max Theorem and get the following:
- there exists a distribution \(\mathcal{C}\) over \(s’\)-size circuits, such that
- for every distribution \(\mathcal{D}\) over \(\delta\)-density distributions,
\(Pr [C(x) \neq f(x)] < 1/2 - \epsilon[/latex], where [latex]x \sim D \sim \mathcal{D}[/latex] and [latex]C\sim \mathcal{C}[/latex]. Since a distribution over [latex]\delta[/latex]-density distributions also gives a [latex]\delta[/latex]-density distribution, it is equivalent to say that,
- there exists a distribution [latex]\mathcal{C}\) over \(s’\)-size circuits, such that
- for every \(\delta\)-density distribution \(D\),
\(\)Pr [C(x) \neq f(x)] < 1/2 - \epsilon[/latex] where [latex]x \sim D[/latex] and [latex]C\sim \mathcal{C}[/latex]. Note that, the distribution [latex]\mathcal{C}[/latex] works for any [latex]\delta[/latex]-density distribution. To construct a circuit approximating [latex]f[/latex] well, we just need to sample a sequence of circuits from [latex]\mathcal{C}[/latex] independently, and take the majority. ......