DocumentCode :
2913531
Title :
Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification
Author :
Impagliazzo, Russell ; Jaiswal, Ragesh ; Kabanets, Valentine
Author_Institution :
California Univ., La Jolla, CA
fYear :
2006
fDate :
Oct. 2006
Firstpage :
187
Lastpage :
196
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 Nk-length string over the alphabet {0, l}k indexed by k-tuples (i1, .. ., ik) isin {1,..., N}k so that the symbol at position (i1, .. ., ik) of the codeword is msg(i 1)...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 > epsivkalpha 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 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 PNP par, the class of languages reducible to NP through one round of parallel oracle queries: If there is a language - in PNP par that cannot be decided by any BPP algorithm on more that 1 $1/nOmega(1) fraction of inputs, then there is another language in PNP par that cannot be decided by any BPP algorithm on more than frac12 + 1/nomega(1) fraction of inputs
Keywords :
Boolean functions; Hadamard codes; computational complexity; product codes; randomised algorithms; Boolean circuits; Boolean functions; Hadamard codes; binary alphabet; direct product lemma; list-decoding direct product codes; randomized algorithm; randomized approximate list-decoding algorithm; uniform hardness amplification; Boolean functions; Circuits; Code standards; Computational complexity; Decoding; Encoding; Error correction; Error correction codes; Polynomials; Product codes;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 2006. FOCS '06. 47th Annual IEEE Symposium on
Conference_Location :
Berkeley, CA
ISSN :
0272-5428
Print_ISBN :
0-7695-2720-5
Type :
conf
DOI :
10.1109/FOCS.2006.13
Filename :
4031355
Link To Document :
بازگشت