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. 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. Locally decodable codes are not a subset of locally testable codes, though there is some overlap between the two.

Codewords are generated from the original message using an algorithm that introduces a certain amount of redundancy into the codeword; thus, the codeword is always longer than the original message. 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.

Overview

locations of the codeword have been corrupted.

.). Informally, this means that the set of queries required to decode any given bit are uniformly distributed over the codeword.

Local list decoders are another interesting subset of local decoders. List decoding is the minimum Hamming distance.

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 composition). 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.

Length of codeword and query complexity

. 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. 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. There are also codes in between, that have codewords polynomial in the size of the original message and polylogarithmic query complexity.

Applications

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.

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

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.

Complexity theory

One of the applications of locally decodable codes in complexity theory that is hard to compute on average case inputs.

is hard on worst case inputs.

Private information retrieval schemes

A private information retrieval 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.

-query locally decodable code is as follows:

from the responses. is uniformly distributed over the codeword; thus, no individual server can gain any information about the user's intentions, so the protocol is private as long as the servers do not communicate.

Examples

The Hadamard code

The Hadamard (mod 2). It is easy to see that every codeword has a Hamming distance from every other codeword.

.

works as follows:

denotes bitwise XOR (mod 2).

Correctness: By linearity,

with good probability.

are uniformly distributed (even though they are dependent), the union bound. Note: to amplify the probability of success, one can repeat the procedure with different random vectors and take the majority answer.

The Reed–Muller code

The main idea behind local decoding of Reed-Muller codes is polynomial interpolation 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.

be a finite field.

, the local decoder shoots a random affine to be one of the points that defines the polynomial.

. For other decoding algorithms, see.

See also

• Private information retrieval

• Linear cryptanalysis

References