Locally decodable code

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. The related locally testable codes 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.

More formally, a $q$-query locally decodable code encodes an $n$-bit message $x$ by an $N$-bit codeword $C(x)$ such that any bit $x_{i}$ of the message can be probabilistically recovered by querying only $q$ bits of the codeword $C(x)$, even if some constant fraction of the codeword has been corrupted.

Examples

The Walsh–Hadamard code $WH$ is a simple, locally decodable code. It has an optimal $q=2$ queries and a best possible decoding error. However, codewords of $n$-bit messages have exponential length $N=2^{n}$, which is why the Walsh–Hadamard code has a very inefficient rate. If a received signal $y\in \{0,1\}^{N}$ agrees with some codeword $WH(x)$ for some message $x\in \{0,1\}^{n}$ on at least a $1-\delta$ fraction of bits, then $x_{i}$ can be recovered from $y$ with probability $1-2\delta$.

See also

• Private information retrieval
• Linear cryptanalysis