Locally decodable code: Difference between revisions

Revision as of 02:56, 20 July 2015

Revision as of 19:29, 2 June 2016

Line 1:

A '''locally decodable code''' (LDC) is an [[error-correcting code]] that allows a single bit of the original message to be decoded with high probability by only examining (or querying) a small number of bits of a possibly corrupted [[codeword]].

<ref name=LDCSurvey>{{cite web|url=http://research.microsoft.com/en-us/um/people/yekhanin/papers/survey_iwcc.pdf |format=PDF |title=Locally decodable codes: a brief survey |author=Sergey Yekhanin}}</ref><ref name=PrivateLDC>{{cite web|url=http://eprint.iacr.org/2007/025.pdf|format=PDF |title=Private Locally Decodable Codes|authorauthor1=Rafail Ostrovsky, |author2=Omkant Pandey, |author3=Amit Sahai }}</ref><ref name=newLDCPIR>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>

This property could be useful, say, in a context where information is being transmitted over a noisy channel, and only a small subset of the data is required at a particular time and there is no need to decode the entire message at once. Note that locally decodable codes are not a subset of [[locally testable code]]s, though there is some overlap between the two.<ref name=LTCvsLDC>{{cite web|url=http://eccc.hpi-web.de/report/2010/130/revision/1/download/ |title=Locally Testable vs. Locally Decodable Codes |authorauthor1=Tali Kaufman, |author2=Michael Viderman }}</ref>

Codewords are generated from the original message using an algorithm that introduces a certain amount of redundancy into the codeword; thus, the codeword is always longer than the original message. This redundancy is distributed across the codeword and allows the original message to be recovered with good probability even in the presence of errors. The more redundant the codeword, the more resilient it is against errors, and the fewer queries required to recover a bit of the original message.