Locally decodable code: Difference between revisions

Revision as of 11:18, 30 September 2009

Revision as of 14:48, 13 October 2010

Line 1:

A '''locally decodable''' [[error-correcting code]] is one in which a single bit of a message can be decoded with high probability from only a small number of bits from a 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 a codeword.

== References ==