Locally decodable code

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. Note that 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.

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

...
Wikipedia