|
Abstract : |
Yao showed that the XOR of independent random instances of a somewhat hard Boolean function becomes almost completely unpredictable. In this paper we show that, in non-uniform settings, total independence is not necessary for this result to hold. We give a pseudo-random generator which produces n instances of the function for which the analog of the XOR lemma holds. This is the first derandomization of a "direct product " result. Our generator is a combination of two known ones- the random walks on expander graphs of [1, 9, 19] and the nearly disjoint subsets generator of [23]. The quality of the generator is proved via a new proof of the XOR lemma, which might also be useful for other direct product results. Combining our generator with the approach of [25, 6] and the generator of [16] gives substantially improved results for hardness vs. randomness trade-offs. In particular, we show that if any problem in E = DT IME(2 O(n)) has circuit complexity 2\Omega\Gamma n), then P = BPP., |
