Under the auspices of the Computational Complexity Foundation (CCF)

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

Revision #2
Authors: Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma
Accepted on: 14th December 2010 19:15
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
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