Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification
Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets · 2006
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 Nk-length string over the alphabet {0, l}kindexed by k-tuples (i1, .. ., ik) isin {1,..., N}kso that the symbol at position (i1, .. ., ik) of the codeword is msg(i1)...msg(ik). 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 > epsivkalphafor 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 1epsiv/)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 PNPpar, the class of languages reducible to NP through one round of parallel oracle queries: If there is a language in PNPparthat cannot be decided by any BPP algorithm on more that 1 $1/nOmega(1)fraction of inputs, then there is another language in PNPparthat cannot be decided by any BPP algorithm on more than frac12 + 1/nomega(1)fraction of inputs