Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification

We consider the problem of approximately locally list-decoding direct product codes. For a parameter k, the k-wise direct product encoding of an N-bit message msg is an N^k-length string over the alphabet {0, l}^k indexed by k-tuples (i₁, .. ., i_k) isin {1,..., N}^k so that the symbol at position (i₁, .. ., i_k) of the codeword is msg(i ₁)...msg(i_k). Such codes arise naturally in the context of hardness amplification of Boolean functions via the direct product lemma (and the closely related Yao ´s XOR Lemma), where typically k Lt N (e.g., k = poly log N). We describe an efficient randomized algorithm for approximate local list-decoding of direct product codes. Given access to a word which agrees with the k-wise direct product encoding of some message msg in at least an epsiv fraction of positions, our algorithm outputs a list of poly(l/epsiv) Boolean circuits computing N-bit strings (viewed as truth tables of log N-variable Boolean functions) such that at least one of them agrees with msg in at least 1 - delta fraction of positions, for delta = O(k^-0.1), provided that epsiv = Omega(poly(l/k); the running time of the algorithm is polynomial in log N and 1/epsiv. When epsiv > epsiv^kalpha for a certain constant alpha > 0, we get a randomized approximate list-decoding algorithm that runs in time quasi-polynomial in 1/epsiv (i.e., (1/epsiv)^{poly log 1}epsiv/)By concatenating the k-wise direct product codes with Hadamard codes, we obtain locally list-decodable codes over the binary alphabet, which can be efficiently approximately list-decoded from fewer than frac12 - epsiv fraction of corruptions as long as epsiv = Omega(poly(l/k)). As an immediate application, we get uniform hardness amplification for P^NP _par, the class of languages reducible to NP through one round of parallel oracle queries: If there is a language - in P^NP _par that cannot be decided by any BPP algorithm on more that 1 $1/n^Omega(1) fraction of inputs, then there is another language in P^NP _par that cannot be decided by any BPP algorithm on more than frac12 + 1/n^omega(1) fraction of inputs