Content deleted Content added
No edit summary |
m survey paper reference |
||
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://research.microsoft.com/en-us/um/people/yekhanin/papers/survey_iwcc.pdf |title=Locally decodable codes: a brief survey |author=Sergey Yekhanin}}</ref><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>
The related [[locally testable code]]s merely require that it can be locally detected whether a given message is close to a codeword, and in this sense locally decodable codes are a special case of locally testable codes.
| |||