XOR Lemma from Hardcore Lemma

We will show that the Hardcore lemma implies the XOR lemma.

Let \(f\colon\{0,1\}^n\to \{\pm1\}\) be a mildly average-case hard function, i.e., \(\mathbb E_{U_n} f\cdot C\le 1-\delta\) for every function \(C\colon\{0,1\}^n\to\{\pm1\}\) with \(\textrm{size}(C)\le S\).

The Hardcore lemma asserts that there exists a distribution \(H\) with density at least \(\delta\) such that \(\mathbb E_H f\cdot C\le \varepsilon\) for every circuit \(C\colon\{0,1\}^n\to \{\pm1\}\) with \(\textrm{size}(C)\le S':=S\cdot \varepsilon^2/\log(1/\delta)\).

To establish the XOR lemma, we will show that for every circuit \(C\colon\{0,1\}^{k\cdot n}\to \{\pm1\}\) with \(\textrm{size}(C)\le S'\), \[ \mathbb E_{U_{kn}} f^{\otimes k}\cdot C \le (1-\delta)^k + \varepsilon \] (Notice that for \(k=O(\delta^{-1}\log(1/\varepsilon))\), the function \(f^{\otimes k}\) is strongly average-case hard in the sense that \(\mathbb E f^{\otimes k} \cdot C \le 2\varepsilon\) for all \(S'\)-sized circuits \(C\).)

Proof: Since \(H\) has density \(\delta\), we can decompose the uniform distribution \(U_n\) as a mixture \(U_n=\delta\cdot H+(1-\delta)\cdot G\) for some distribution \(G\). (Here, the assertion is that we can “simulate” the uniform distribution by sampling from \(H\) with probability \(\delta\) and sampling from \(G\) with probability \(1-\delta\).)

We can decompose the distribution \(U_{k n}\) in a similar way, because \(U_{k n } = U_n^{\otimes k}\). This decomposition looks as follows, \[ U_{kn}= U_{n}^{\otimes k} = (1-\delta)^k \cdot G^{\otimes k} + \delta(1-\delta)^{k-1}\cdot H \otimes G^{\otimes (k-1)}\ldots \] In words, we express \(U_{kn}\) as a mixture of \(2^k\) distributions (analogous to the binomial expansion). Each of these \(2^k\) distributions is a \(k\)-fold product distribution, with factors either \(G\) or \(H\).

We claim that all product distributions that have at least one factor from \(H\) are hardcore distributions for \(f^{\otimes k}\). For example, consider the distribution \(G^{\otimes (k-1)}\otimes H\). Then, every \(S'\)-circuit \(C\) satisfies \[\mathbb E_{H\otimes G^{\otimes (k-1)}} f^{\otimes k}\cdot C = \mathbb E_{x_1,\ldots,x_{k-1}\sim G} f(x_1)\cdots f(x_{k-1}) \cdot \mathbb E_{x_k \sim H} f(x_k)\cdot C(x_1,x_2,\ldots,x_k)\le \varepsilon\]

How can we now bound \(\mathbb E_{U_{kn}} f^{\otimes k} \cdot C\)? The point is that we can decompose the distribution \(U_{kn}=(1-\delta)^k\cdot G^{\otimes k} + (1-(1-\delta)^k) \cdot H'\), where \(H'\) is a hardcore distribution for \(f^{\otimes k}\) (corresponding to the product distributions with at least one factor from \(H\)). Therefore, \[ \mathbb E_{U_{kn}} f^{\otimes k}\cdot C = (1-\delta)^k\mathbb E_{G^{\otimes k}} f^{\otimes k}\cdot C~+~(1-(1-\delta))^k \cdot \mathbb E_{H'} f^{\otimes k}\cdot C \le (1-\delta)^k + \varepsilon. \]