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  -> {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 e, there is an efficient randomized algorithm A with the following property. Given a circuit C that computes f k  on at least e fraction of inputs, the algorithm A outputs with probability at least 3/4 a list of O(1/e) 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/e)/k). Moreover, each output circuit is an AC 0  circuit (of size poly(n,k,log 1/δ,1/e)), 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.
['Russell Impagliazzo', 'Ragesh Jaiswal', 'Valentine Kabanets', 'Avi Wigderson']
Uniform direct product theorems: simplified, optimized, and derandomized