Content deleted Content added
→Length of codeword and query complexity: replace "this is outdated" text with the relevant needs-update-inline template ; frankly it's a bit useless for someone to say "there are many results that contradict this" and then for that person to not cite any of these results. |
→top: no space between punct and ref |
||
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|author1=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 |author1=Tali Kaufman |author2=Michael Viderman }}</ref>
| |||