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

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. Consider L limited to only length t inputs. Then we can see L as a binary string of length 2^t , where each bit is L(x) for each x \in \{ 0, 1\}^t . We can use a polynomial length locally decodable code C with polylogarithmic query complexity that tolerates some constant fraction of errors to encode the string that represents L to create a new string of length 2^{O(t)} = 2^{t'} . We think of this new string as defining a new problem L' on length t' inputs. If L' is easy to solve on average, that is, we can solve L' correctly on a large fraction 1 - \epsilon of inputs, then by the properties of the LDC used to encode it, we can use L' to probabilistically compute L on all inputs. Thus, a solution to L' for most inputs would allow us to solve L on all inputs, contradicting our assumption that L is hard on worst case inputs. The Hadamard (or Walsh-Hadamard) code is an example of a simple locally decodable code that maps a string of length k to a codeword of length 2^k . The codeword for a string x \in \{0, 1\}^k is constructed as follows: for every a_j\in\{0, 1\}^k , the j^{th} bit of the codeword is equal to x \odot a_j , where x \odot y = \sum\limits_{i=1}^{k} x_{i}y_i (mod 2). It is easy to see that every codeword has a Hamming distance of \frac{n}{2} from every other codeword. The local decoding algorithm has query complexity 2, and the entire original message can be decoded with good probability if the codeword is corrupted in less than \frac{1}{4} of its bits. For \rho , if the codeword is corrupted in a \rho fraction of places, a local decoding algorithm can recover the i^{th} bit of the original message with probability 1 - 2\rho . Proof: Given a codeword H and an index i , the algorithm to recover the i^{th} bit of the original message x works as follows: Let e^j refer to the vector in \{0, 1\}^k that has 1 in the j^{th} position and 0s elsewhere. For y \in \{0, 1\}^k , f(y) denotes the single bit in H that corresponds to x \odot y . The algorithm chooses a random vector y \in \{0, 1\}^k and the vector y' = y \oplus e^i (where \oplus denotes bitwise XOR). The algorithm outputs f(y) \oplus f(y') (mod 2). Correctness: By linearity, (x \odot y) \oplus (x \odot y') = (x \odot y) \oplus (x \odot (y \oplus e^i)) = (x \odot y) \oplus (x \odot y) \oplus (x \odot e^i) = x \odot e^i But (x \odot e^i) = x_i , so we just need to show that f(y) = x \odot y and f(y') = x \odot y' with good probability. Since y and y' are uniformly distributed (even though they are dependent), the union bound implies that f(y) = x \odot y and f(y') = x \odot y' with probability at least 1 - 2\rho . Note: to amplify the probability of success, one can repeat the procedure with different random vectors and take the majority answer. P(x_1, \ldots, x_l) = \sum\limits_{i_1+\ldots+i_l\le d}c_{i_1,\ldots,i_l}x_1^{i_1}x_2^{i_2}\cdots x_l^{i_l} specified by the interpolation of the \binom{l+d}{d} values of the predefined points and the output is the sequence \{P(x_1, \ldots, x_l)\} for every x_1, \ldots, x_l \in \mathbb{F} . To recover the value of a degree d polynomial at a point w \in \mathbb{F}^n , the local decoder shoots a random affine line through w . Then it picks d + 1 points on that line, which it uses to interpolate the polynomial and then evaluate it at the point where the result is w . To do so, the algorithm picks a vector v \in \mathbb{F}^n uniformly at random and considers the line L = \{w + \lambda v \mid \lambda \in \mathbb{F}\} through w . The algorithm picks an arbitrary subset S of \mathbb{F} , where |S| = d+1 , and queries coordinates of the codeword that correspond to points w+\lambda v for all \lambda \in S and obtains values \{e_{\lambda}\} . Then it uses polynomial interpolation to recover the unique univariate polynomial h with degree less than or equal to d such that h(\lambda) = e_{\lambda} for all \lambda \in S . Then, to get the value of w , it just evaluates h(0) . To recover a single value of the original message, one chooses w to be one of the points that defines the polynomial. Each individual query is distributed uniformly at random over the codeword. Thus, if the codeword is corrupted in at most a \delta 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 1 - (d+1)\delta . For other decoding algorithms, see.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1362628428 under CC BY-SA 4.0; modifications have been made.