ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > AMPLIFICATION OF HARDNESS:
Reports tagged with Amplification of Hardness:
TR03-042 | 15th May 2003
Luca Trevisan

List Decoding Using the XOR Lemma

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 ... more >>>



ISSN 1433-8092 | Imprint