Locally decodable code: Difference between revisions

Revision as of 18:14, 5 November 2010

Revision as of 09:52, 6 November 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>

LocallyThe decodable codes can be seen as a generalization ofrelated [[locally testable code]]s, wheremerely therequire requirementthat isit merelycan tobe locally detectdetected whether a given message is close to a codeword, and in this sense locally decodable codes are a special case of locally testable codes.

More formally, a <math>q</math>-query locally decodable code encodes an <math>n</math>-bit message <math>x</math> by an <math>N</math>-bit codeword <math>C(x)</math> such that any bit <math>x_i</math> of the message can be probabilistically recovered by querying only <math>q</math> bits of the codeword <math>C(x)</math>, even if some constant fraction of the codeword has been corrupted.