Locally decodable code: Difference between revisions

Revision as of 21:17, 14 November 2019

Revision as of 02:24, 7 April 2021

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>

Line 7:

More formally, a <math>(q, \delta, \epsilon)</math>-locally decodable code encodes an <math>n</math>-bit message <math>x</math> to an <math>N</math>-bit codeword <math>C(x)</math> such that any bit <math>x_i</math> of the message can be recovered with probability <math>1 - \epsilon</math> by using a randomized decoding algorithm that queries only <math>q</math> bits of the codeword <math>C(x)</math>, even if up to <math>\delta N</math> locations of the codeword have been corrupted.

Furthermore, a perfectly smooth local decoder is a decoder such that, in addition to always generating the correct output given access to an uncorrupted codeword, for every <math>j \in [q]</math> and <math>i \in [n]</math> the <math>j^{th}</math> query to recover the <math>i^{th}</math> bit is uniform over <math>[N]</math>.<ref name=AppCodingTheory>{{cite web|url=http://theory.stanford.edu/~trevisan/pubs/codingsurvey.pdf |format=PDF |title=Some Applications of Coding Theory in Computational Complexity |author=Luca Trevisan}}</ref>

(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.

Line 18:

| year=2009

| isbn=978-0-521-42426-4

| postscript=. |ref=harv

}}</ref>

Line 26 ⟶ 25:

The rate of a code refers to the ratio between its message length and codeword length: <math>\frac{|x|}{|C(x)|}</math>, and the number of queries required to recover 1 bit of the message is called the query complexity of a code.

The rate of a code is inversely related to the query complexity, but the exact shape of this tradeoff is a major open problem.<ref name=LDC1>{{cite web|url=http://research.microsoft.com/en-us/um/people/yekhanin/Papers/LDC_now.pdf |format=PDF |title=Locally Decodable Codes |author=Sergey Yekhanin}}</ref><ref name=LDC2>{{cite web|url=https://www.iacr.org/workshops/tcc2012/survey_tcc.pdf |format=PDF |title=Locally Decodable Codes |author=Sergey Yekhanin}}</ref> It is known that there are no LDCs that query the codeword in only one position, and that the optimal codeword size for query complexity 2 is exponential in the size of the original message.<ref name=LDC1/> However, there are no known tight lower bounds for codes with query complexity greater than 2. Approaching the tradeoff from the side of codeword length, the only known codes with codeword length proportional to message length have query complexity <math>k^\epsilon</math> for <math>\epsilon > 0</math><ref name=LDC1/>{{Update inline|reason=This line is no outdated - there are many results since 2011|date=December 2016}} There are also codes in between, that have codewords polynomial in the size of the original message and polylogarithmic query complexity.<ref name=LDC1/>

== Applications ==

Line 32 ⟶ 31:

=== Data transmission and storage ===

Locally decodable codes are especially useful for data transmission over noisy channels. The Hadamard code (a special case of Reed Muller codes) was used in 1971 by [[Mariner 9]] to transmit pictures of Mars back to Earth. It was chosen over a 5-repeat code (where each bit is repeated 5 times) because, for roughly the same number of bits transmitted per pixel, it had a higher capacity for error correction. (The Hadamard code falls under the general umbrella of [[forward error correction]], and just happens to be locally decodable; the actual algorithm used to decode the transmission from Mars was a generic error-correction scheme.)<ref>{{cite web |title=Combinatorics in Space The Mariner 9 Telemetry System |url=http://www-math.ucdenver.edu/~wcherowi/courses/m7409/mariner9talk.pdf|format=PDF }}</ref>

LDCs are also useful for data storage, where the medium may become partially corrupted over time, or the reading device is subject to errors. In both cases, an LDC will allow for the recovery of information despite errors, provided that there are relatively few. In addition, LDCs do not require that the entire original message be decoded; a user can decode a specific portion of the original message without needing to decode the entire thing.<ref name=PIR>{{cite web|url=http://research.microsoft.com/pubs/141305/cacm_2010.pdf |title=Private Information retrieval |author=Sergey Yekhanin}}</ref>