Uniform direct product theorems: simplified, optimized, and derandomized
Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, 2008•dl.acm.org
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 fk (x1,..., xk)=(f (x1),..., f (xk))(where each xi->{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 ε, there is an efficient randomized algorithm A …
1} is somewhat hard to compute on average by small circuits, then the corresponding k-wise
direct product function fk (x1,..., xk)=(f (x1),..., f (xk))(where each xi->{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 ε, there is an efficient randomized algorithm A …
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 fk(x1,...,xk)=(f(x1),...,f(xk)) (where each xi -> {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 ε, there is an efficient randomized algorithm A with the following property. Given a circuit C that computes fk on at least ε fraction of inputs, the algorithm A outputs with probability at least 3/4 a list of O(1/ε) circuits such that at least one of the circuits on the list computes f on more than 1-δ fraction of inputs, for δ = O((log 1/ε)/k). Moreover, each output circuit is an AC0 circuit (of size poly(n,k,log 1/δ,1/ε)), with oracle access to the circuit C. Using the Goldreich-Levin decoding algorithm [5], we also get a fully uniform version of Yao's XOR Lemma [18] with optimal parameters, up to constant factors. Our results simplify and improve those in [10]. Our main result may be viewed as an efficient approximate, local, list-decoding algorithm for direct-product codes (encoding a function by its values on all k-tuples) with optimal parameters. We generalize it to a family of "derandomized" direct-product codes, which we call intersection codes, where the encoding provides values of the function only on a subfamily of k-tuples. The quality of the decoding algorithm is then determined by sampling properties of the sets in this family and their intersections. As a direct consequence of this generalization we obtain the first derandomized direct product result in the uniform setting, allowing hardness amplification with only constant (as opposed to a factor of k) increase in the input length. Finally, this general setting naturally allows the decoding of concatenated codes, which further yields nearly optimal derandomized amplification.