Search

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