Hardness amplification within NP

In this paper we investigate the following question: if NP is slightly hard on average, is it very hard on average? We give a positive answer: if there is a function in NP which is infinitely often balanced and <f>(1-1/poly(n))</f>-hard for circuits of polynomial size, then there is a function in NP which is infinitely often <f>(1/2+n-1/2+#x03B5;)</f>-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 <f>g( f(x1),…,f(xn))</f> in terms of: (i) the original hardness of <f>f</f>, and (ii) the expected bias of the function <f>g</f> when subjected to random restrictions. The computational result we prove essentially matches an information-theoretic bound. [Copyright &y& Elsevier]