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.
[1][2][3] 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.
This redundancy is distributed across the codeword and allows the original message to be recovered with good probability even in the presence of errors.
The more redundant the codeword, the more resilient it is against errors, and the fewer queries required to recover a bit of the original message.
Informally, this means that the set of queries required to decode any given bit are uniformly distributed over the codeword.
In this case, it is no longer possible to identify exactly which original message has been encoded, since there could be multiple codewords within
, it is possible to identify the set of messages that encode to codewords that are within
An upper bound on the size of the set of messages can be determined by
(Note that, in this context, concatenation is the term used by scholars to refer to what is usually called composition; see [5]).
The rate of a code is inversely related to the query complexity, but the exact shape of this tradeoff is a major open problem.
[8] However, there are no known tight lower bounds for codes with query complexity greater than 2.
[8][needs update] There are also codes in between, that have codewords polynomial in the size of the original message and polylogarithmic query complexity.
[8] 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.
[9] Locally decodable codes are especially useful for data transmission over noisy channels.
(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.
)[10] 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.
[11] One of the applications of locally decodable codes in complexity theory is hardness amplification.
Using LDCs with polynomial codeword length and polylogarithmic query complexity, one can take a function
that is hard to solve on worst case inputs and design a function
with polylogarithmic query complexity that tolerates some constant fraction of errors to encode the string that represents
[3][11] One can easily see that locally decodable codes have applications in this setting.
are uniformly distributed (even though they are dependent), the union bound implies that
Note: to amplify the probability of success, one can repeat the procedure with different random vectors and take the majority answer.
[13] The main idea behind local decoding of Reed-Muller codes is polynomial interpolation.
The key concept behind a Reed-Muller code is a multivariate polynomial of degree
The message is treated as the evaluation of a polynomial at a set of predefined points.
is useful because (a) the algorithm can be repeated using different lines through the same point to improve the probability of correctness, and (b) the queries are uniformly distributed over the codeword.
, the local decoder shoots a random affine line through
fraction of locations, by the union bound, the probability that the algorithm samples only uncorrupted coordinates (and thus correctly recovers the bit) is at least