The classical direct product theorem for circuits says that if a Boolean function f : {0, 1}(n) -> {0, 1} is somewhat hard to compute on average by small circuits, then the corresponding k-wise direct product funct...
详细信息
The classical direct product theorem for circuits says that if a Boolean function f : {0, 1}(n) -> {0, 1} is somewhat hard to compute on average by small circuits, then the corresponding k-wise direct product function f(k)(x(1), ..., x(k)) = (f(x(1)), ..., f(x(k))) (where each x(i) is an element of {0, 1}(n)) is significantly harder to compute on average by slightly smaller circuits. We prove a fully uniform version of the direct product theorem with information-theoretically optimal parameters, up to constant factors. Namely, we show that for given k and is an element of, there is an efficient randomized algorithm A with the following property. Given a circuit C that computes f(k) on at least is an element of fraction of inputs, the algorithm A outputs with probability at least 3/4 a list of O(1/is an element of) circuits such that at least one of the circuits on the list computes f on more than 1 -delta fraction of inputs, for delta = O((log 1/is an element of)/ k);moreover, each output circuit is an AC(0) circuit (of size poly(n, k, log 1/delta, 1/is an element of)), with oracle access to the circuit C. Using the Goldreich-Levin decoding algorithm [O. Goldreich and L. A. Levin, A hard-core predicate for all one-way functions, in Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, Seattle, 1989, pp. 25-32], we also get a fully uniform version of Yao's XOR lemma [A. C. Yao, Theory and applications of trapdoor functions, in Proceedings of the Twenty-Third Annual IEEE Symposium on Foundations of Computer Science, Chicago, 1982, pp. 80-91] with optimal parameters, up to constant factors. Our results simplify and improve those in [R. Impagliazzo, R. Jaiswal, and V. Kabanets, Approximately list-decoding direct product codes and uniform hardness amplification, in Proceedings of the Forty-Seventh Annual IEEE Symposium on Foundations of Computer Science, Berkeley, CA, 2006, pp. 187-196]. Our main result may be viewed as an efficient approximate, lo
暂无评论