Content deleted Content added
m →See also: per MoS |
per MOS:HEAD, headers take ordinary sentence case |
||
Line 24:
Locally decodable codes can also be concatenated, where a message is encoded first using one scheme, and the resulting codeword is encoded again using a different scheme. (Note that, in this context, [[concatenation]] is the term used by scholars to refer to what is usually called [[function composition|composition]]; see <ref name=AppCodingTheory/>). This might be useful if, for example, the first code has some desirable properties with respect to rate, but it has some undesirable property, such as producing a codeword over a non-binary alphabet. The second code can then transform the result of the first encoding over a non-binary alphabet to a binary alphabet. The final encoding is still locally decodable, and requires additional steps to decode both layers of encoding.<ref>{{harvnb|Arora|Barak|2009|loc=Section 19.4.3}}</ref>
== Length of
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.
Line 32:
Locally decodable codes have applications to data transmission and storage, complexity theory, data structures, derandomization, theory of fault tolerant computation, and private information retrieval schemes.<ref name=LDC2/>
=== Data
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>
=== Complexity
One of the applications of locally decodable codes in [[Computational complexity theory|complexity theory]] is hardness amplification. Using LDCs with polynomial codeword length and polylogarithmic query complexity, one can take a function <math>L: \{0,1\}^n \rightarrow \{0,1\}</math> that is hard to solve on worst case inputs and design a function <math>L': \{0,1\}^N \rightarrow \{0,1\}</math> that is hard to compute on average case inputs.
Consider <math>L</math> limited to only length <math>t</math> inputs. Then we can see <math>L</math> as a binary string of length <math>2^t</math>, where each bit is <math>L(x)</math> for each <math>x \in \{ 0, 1\}^t</math>. We can use a polynomial length locally decodable code <math>C</math> with polylogarithmic query complexity that tolerates some constant fraction of errors to encode the string that represents <math>L</math> to create a new string of length <math>2^{O(t)} = 2^{t'}</math>. We think of this new string as defining a new problem <math>L'</math> on length <math>t'</math> inputs. If <math>L'</math> is easy to solve on average, that is, we can solve <math>L'</math> correctly on a large fraction <math>1 - \epsilon</math> of inputs, then by the properties of the LDC used to encode it, we can use <math>L'</math> to probabilistically compute <math>L</math> on all inputs. Thus, a solution to <math>L'</math> for most inputs would allow us to solve <math>L</math> on all inputs, contradicting our assumption that <math>L</math> is hard on worst case inputs.<ref name=AppCodingTheory/><ref name=LDC1/><ref>{{harvnb|Arora|Barak|2009|loc=Section 19.4}}</ref>
=== Private
A [[private information retrieval]] scheme allows a user to retrieve an item from a server in possession of a database without revealing which item is retrieved. One common way of ensuring privacy is to have <math>k</math> separate, non-communicating servers, each with a copy of the database. Given an appropriate scheme, the user can make queries to each server that individually do not reveal which bit the user is looking for, but which together provide enough information that the user can determine the particular bit of interest in the database.<ref name=newLDCPIR/><ref name=PIR/>
| |||