A Note on Amplifying the Error-Tolerance of Locally Decodable Codes. Academic Article uri icon


  • Abstract Trevisan [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 locally list-decodable codes.

publication date

  • January 1, 2010