Approximate list-decoding of direct product codes and uniform hardness amplification
Russell Impagliazzo, Ragesh Jaiswal, and Valentine Kabanets
Abstract
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,1}^{k} indexed by k-tuples (i_{1},...,i_{k}) in {1,...,N}^{k} so that the symbol at position (i_{1},...,i_{k}) of the codeword is msg(i_{1}) ... msg(i_{k}). Such codes arise naturally in the context of hardness amplification of Boolean functions via the Direct Product Lemma (and closely related Yao's XOR Lemma), where typically k<< N (e.g., k= polylog 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 ε fraction of positions, our algorithm outputs a list of poly(1/ε) 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-δ fraction of positions, for δ = O(k^{-0.1}), provided that ε= Ω(poly(1/k)); the running time of the algorithm is polynomial in log N and 1/ε. When ε> e^{-kα} for a certain constant α>0, we get a randomized approximate list-decoding algorithm that runs in time quasi-polynomial in 1/ε (i.e., in time (1/ε)^{polylog 1/ε}).
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 1/2- ε fraction of corruptions as long as ε = Ω(poly 1/k). As an immediate application, we get uniform hardness amplification for P^{NP||}, the class of languages reducible to NP through one round of parallel oracle queries: If there is a language in P^{NP||} that cannot be decided by any BPP algorithm on more that 1-1/n^{Ω(1)} fraction of inputs, then there is another language in P^{NP||} that cannot be decided by any BPP algorithm on more than 1/2+1/n^{ω(1)} fraction of inputs.
Versions
- journal version in SIAM Journal on Computing 39(2):564-605, 2009.
- extended abstract in Proceedings of the Forty-Seventh Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pages 187-196, 2006.