Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR10-134 | 14th December 2010 19:15

A Note on Amplifying the Error-Tolerance of Locally Decodable Codes

RSS-Feed




Revision #2
Authors: Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma
Accepted on: 14th December 2010 19:15
Downloads: 2228
Keywords: 


Abstract:

We show a generic, simple way to amplify the error-tolerance of locally decodable codes.
Specifically, we show how to transform a locally decodable code that can tolerate a constant fraction of errors
to a locally decodable code that can recover from a much higher error-rate. We also show how to transform such locally
decodable codes to \emph{locally list-decodable codes


Revision #1 to TR10-134 | 26th August 2010 14:56

A Note on Amplifying the Error-Tolerance of Locally Decodable Codes





Revision #1
Authors: Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma
Accepted on: 26th August 2010 14:56
Downloads: 1718
Keywords: 


Abstract:


Trevisan~\cite{Tre03} suggested a transformation that allows amplifying the error rate a code can handle. We observe that this transformation, that was suggested in the non-local setting, works also in the local setting and thus gives a generic, simple way to amplify the error-tolerance of locally decodable codes.
Specifically, this shows how to transform a locally decodable code that can tolerate a constant fraction of errors
to a locally decodable code that can recover from a much higher error-rate, and how to transform such locally
decodable codes to \emph{locally list-decodable codes}.

The transformation of~\cite{Tre03} involves a simple composition with an \emph{approximately} locally (list) decodable code.
Using a construction of such codes by Impagliazzo et al.~\cite{IJKW10}, the transformation incurs only a negligible
growth in the length of the code and in the query complexity.


Paper:

TR10-134 | 23rd August 2010 18:10

A Note on Amplifying the Error-Tolerance of Locally Decodable Codes





TR10-134
Authors: Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma
Publication: 23rd August 2010 19:43
Downloads: 1869
Keywords: 


Abstract:

We show a generic, simple way to amplify the error-tolerance of locally decodable codes.
Specifically, we show how to transform a locally decodable code that can tolerate a constant fraction of errors
to a locally decodable code that can recover from a much higher error-rate. We also show how to transform such locally
decodable codes to \emph{locally list-decodable codes



ISSN 1433-8092 | Imprint