Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR03-042 | 15th May 2003 00:00

List Decoding Using the XOR Lemma


Authors: Luca Trevisan
Publication: 6th June 2003 19:38
Downloads: 1458


We show that Yao's XOR Lemma, and its essentially equivalent
rephrasing as a Direct Product Lemma, can be
re-interpreted as a way of obtaining error-correcting
codes with good list-decoding algorithms from error-correcting
codes having weak unique-decoding algorithms. To get codes
with good rate and efficient list decoding algorithms
one needs a proof of the Direct Product Lemma that, respectively,
is strongly derandomized, and uses very small advice.

We show how to reduce advice in Impagliazzo's proof of the
Direct Product Lemma for pairwise independent inputs, which
leads to error-correcting codes with quadratic encoding length,
quasi-quadratic encoding time, and probabilistic quasi-linear
list-decoding time. (Note that the decoding time is sub-linear
in the length of the encoding.)

Back to complexity theory, our advice-efficient proof of
Impagliazzo's ``hard-core set'' results yields a (weak) uniform
version of O'Donnell results on amplification of hardness in NP.
We show that if there is a problem in NP that cannot be solved by
BPP algorithms on more than a 1-1/(\log n)^c fraction of inputs,
then there is a problem in NP that cannot be solved by BPP
algorithms on more than a 3/4 + 1/(\log n)^c fraction of inputs,
where c>0 is an absolute constant.

ISSN 1433-8092 | Imprint