On the Complexity of Hardness Amplification

For $\delta \in (0,1)$ and $k,n\in \BBN $, we study the task of transforming a hard function $f: \{0,1\}^{n}\to \{0,1\} $, with which any small circuit disagrees on $(1-\delta )/2$ fraction of the input, into a harder function $f^{\prime}$, with which any small circuit disagrees on $(1-\delta ^{k})/2$ fraction of the input. First, we show that such hardness amplification, when carried out in some black-box way, must require a high complexity. In particular, it cannot be realized by a circuit of depth $d$ and size $2^{o(k^{1/d})}$ or by a nondeterministic circuit of size $o(k/\log k)$ (and arbitrary depth) for any $\delta \in (0,1)$. This extends the result of Viola, which only works when $(1-\delta )/2$ is small enough. Furthermore, we show that even without any restriction on the complexity of the amplification procedure, such a black-box hardness amplification must be inherently nonuniform in the following sense. To guarantee the hardness of the resulting function $f^{\prime}$, even against uniform machines, one has to start with a function $f$, which is hard against nonuniform algorithms with $\Omega (k\log (1/\delta ))$ bits of advice. This extends the result of Trevisan and Vadhan, which only addresses the case with $(1-\delta )/2=2^{-n}$. Finally, we derive similar lower bounds for any black-box construction of a pseudorandom generator (PRG) from a hard function. To prove our results, we link the task of hardness amplifications and PRG constructions, respectively, to some type of error-reduction codes, and then we establish lower bounds for such codes, which we hope could find interest in both coding theory and complexity theory.