On the Complexity of Hardness Amplification

Abstract

<para xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> For <emphasis><formula formulatype="inline"><tex>$\delta \in (0,1)$</tex> </formula></emphasis> and <emphasis><formula formulatype="inline"><tex>$k,n\in \BBN $</tex></formula></emphasis>, we study the task of transforming a hard function <emphasis><formula formulatype="inline"><tex>$f: \{0,1\}^{n}\to \{0,1\} $</tex></formula></emphasis>, with which any small circuit disagrees on <emphasis><formula formulatype="inline"><tex>$(1-\delta )/2$</tex></formula></emphasis> fraction of the input, into a harder function <emphasis><formula formulatype="inline"> <tex>$f^{\prime}$</tex></formula></emphasis>, with which any small circuit disagrees on <emphasis><formula formulatype="inline"><tex>$(1-\delta ^{k})/2$</tex> </formula></emphasis> 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 <emphasis><formula formulatype="inline"><tex>$d$</tex></formula></emphasis> and size <emphasis><formula formulatype="inline"><tex>$2^{o(k^{1/d})}$</tex></formula></emphasis> or by a nondeterministic circuit of size <emphasis><formula formulatype="inline"> <tex>$o(k/\log k)$</tex></formula></emphasis> (and arbitrary depth) for any <emphasis><formula formulatype="inline"><tex>$\delta \in (0,1)$</tex></formula></emphasis>. This extends the result of Viola, which only works when <emphasis><formula formulatype="inline"> <tex>$(1-\delta )/2$</tex></formula></emphasis> 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 <emphasis><formula formulatype="inline"><tex>$f^{\prime}$</tex></formula></emphasis>, even against uniform machines, one has to start with a function <emphasis><formula formulatype="inline"> <tex>$f$</tex></formula></emphasis>, which is hard against nonuniform algorithms with <emphasis><formula formulatype="inline"><tex>$\Omega (k\log (1/\delta ))$</tex></formula></emphasis> bits of advice. This extends the result of Trevisan and Vadhan, which only addresses the case with <emphasis><formula formulatype="inline"><tex>$(1-\delta )/2=2^{-n}$</tex></formula></emphasis>. 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. </para>