Hardness amplification within NP
Ryan W. O’Donnell · 2002
(MATH) In this paper we investigate the following question: If $ p$ is slightly hard on average, is it very hard on average? We show the answer is yes; if there is a function in $ p$ which is \mbox{$(1-1/\poly(n))$}-hard for circuits of polynomial size, then there is a function in $ p$ which is $(\half + n^{-1/2 + \epsilon})$-hard for circuits of polynomial size. Our proof technique is to generalize the Yao XOR Lemma, allowing us to characterize nearly tightly the hardness of a composite function \linebreak $g(f(x_1), \ldots, f(x_n))$, in terms of: (i) the original hardness of $f$, and (ii) the {\em expected bias} of the function $g$ when subjected to random restrictions. The computational result we prove essentially matches an information-theoretic bound.