Content deleted Content added
m Edit for clarity |
m Added links |
||
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 |title=Locally decodable codes: a brief survey |author=Sergey Yekhanin}}</ref><ref name=PrivateLDC>{{cite web|url=http://eprint.iacr.org/2007/025.pdf|title=Private Locally Decodable Codes|author=Rafail Ostrovsky, Omkant Pandey, 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|locally testable codes]], 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 |author=Tali Kaufman, Michael Viderman}}</ref>
Line 11:
(The notation <math>[y]</math> denotes the set <math>\{1,\ldots, y\}</math>). Informally, this means that the set of queries required to decode any given bit are uniformly distributed over the codeword.
Local list decoders are another interesting subset of local decoders. List decoding is useful when a codeword is corrupted in more than <math>\delta/2</math> places, where <math>\delta</math> is the minimum [[Hamming distance]] between two codewords. In this case, it is no longer possible to identify exactly which original message has been encoded, since there could be multiple codewords within <math>\delta</math> distance of the corrupted codeword. However, given a radius <math>\epsilon</math>, it is possible to identify the set of messages that encode to codewords that are within <math>\epsilon</math> of the corrupted codeword. An upper bound on the size of the set of messages can be determined by <math>\delta</math> and <math>\epsilon</math>. <ref>Section 19.5 of {{Cite book
| last1=Arora | first1=Sanjeev | authorlink1=Sanjeev Arora
| last2=Barak | first2=Boaz
| |||