Locally decodable code: Difference between revisions

Revision as of 09:08, 14 October 2010

Revision as of 09:11, 14 October 2010

Line 1:

A '''locally decodable code''' is an [[error-correcting code]] that allows to decode a single bit of a message with high probability by only looking at a small number of bits of a possibly partially corrupted codeword.<ref> {{cite web|url=http://eprint.iacr.org/2007/025.pdf|title=Private Locally Decodable Codes|author=Rafail Ostrovsky, Omkant Pandey, Amit Sahai}}</ref><ref> Sergey Yekhanin. New locally decodable codes and private information retrieval schemes, [http://www.eccc.hpi-web.de/eccc-reports/2006/TR06-127/index.html Technical Report ECCC TR06-127], 2006.</ref>

Locally decodable codes can be seen as a special case of [[locally testable code]]s, where the requirement is merely to locally detect whether a given message is close to a codeword.