Content deleted Content added
m Added links |
m Checkwiki 61 + General Fixes using AWB |
||
Line 1:
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]].
<ref name=LDCSurvey>{{cite web|url=http://research.microsoft.com/en-us/um/people/yekhanin/papers/survey_iwcc.pdf |title=Locally decodable codes: a brief survey |author=Sergey Yekhanin}}</ref><ref name=PrivateLDC>{{cite web|url=http://eprint.iacr.org/2007/025.pdf|title=Private Locally Decodable Codes|author=Rafail Ostrovsky, Omkant Pandey, Amit Sahai}}</ref><ref name=newLDCPIR>
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 code
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.
Line 11:
(The notation <math>[y]</math> denotes the set <math>\{1,\ldots, y\}</math>). 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 useful when a codeword is corrupted in more than <math>\delta/2</math> places, where <math>\delta</math> is the minimum [[Hamming distance]] between two codewords. In this case, it is no longer possible to identify exactly which original message has been encoded, since there could be multiple codewords within <math>\delta</math> distance of the corrupted codeword. However, given a radius <math>\epsilon</math>, it is possible to identify the set of messages that encode to codewords that are within <math>\epsilon</math> of the corrupted codeword. An upper bound on the size of the set of messages can be determined by <math>\delta</math> and <math>\epsilon</math>.
| last1=Arora | first1=Sanjeev | authorlink1=Sanjeev Arora
| last2=Barak | first2=Boaz
Line 49:
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 <math>L: \{0,1\}^n \rightarrow \{0,1\}</math> that is hard to solve on worst case inputs and design a function <math>L': \{0,1\}^N \rightarrow \{0,1\}</math> that is hard to compute on average case inputs.
Consider <math>L</math> limited to only length <math>t</math> inputs. Then we can see <math>L</math> as a binary string of length <math>2^t</math>, where each bit is <math>L(x)</math> for each <math>x \in \{ 0, 1\}^t</math>. We can use a polynomial length locally decodable code <math>C</math> with polylogarithmic query complexity that tolerates some constant fraction of errors to encode the string that represents <math>L</math> to create a new string of length <math>2^{O(t)} = 2^{t'}</math>. We think of this new string as defining a new problem <math>L'</math> on length <math>t'</math> inputs. If <math>L'</math> is easy to solve on average, that is, we can solve <math>L'</math> correctly on a large fraction <math>1 - \epsilon</math> of inputs, then by the properties of the LDC used to encode it, we can use <math>L'</math> to probabilistically compute <math>L</math> on all inputs. Thus, a solution to <math>L'</math> for most inputs would allow us to solve <math>L</math> on all inputs, contradicting our assumption that <math>L</math> is hard on worst case inputs.<ref name=
| last1=Arora | first1=Sanjeev | authorlink1=Sanjeev Arora
| last2=Barak | first2=Boaz
Line 67:
Let <math>C</math> be a perfectly smooth LDC that encodes <math>n</math>-bit messages to <math>N</math>-bit codewords. As a preprocessing step, each of the <math>k</math> servers <math>S_1,\ldots ,S_k</math> encodes the <math>n</math>-bit database <math>x</math> with the code <math>C</math>, so each server now stores the <math>N</math>-bit codeword <math>C(x)</math>. A user interested in obtaining the <math>i^{th}</math> bit of <math>x</math> randomly generates a set of <math>k</math> queries <math>q_1,\ldots q_k</math> such that <math>x_i</math> can be computed from <math>C(x)_{q_1}, \ldots C(x)_{q_k}</math> using the local decoding algorithm <math>A</math> for <math>C</math>. The user sends each query to a different server, and each server responds with the bit requested. The user then uses <math>A</math> to compute <math>x_i</math> from the responses.<ref name=LDC1/><ref name=PIR/>
Because the decoding algorithm is perfectly smooth, each query <math>q_j</math> 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.<ref name=PIR/>
== Examples ==
=== The Hadamard code ===
The [[Hadamard]] (or Walsh-Hadamard) code is an example of a simple locally decodable code that maps a string of length <math>k</math> to a codeword of length <math>2^k</math>. The codeword for a string <math>x \in \{0, 1\}^k</math> is constructed as follows: for every <math>a_j\in\{0, 1\}^k</math>, the <math>j^{th}</math> bit of the codeword is equal to <math>x \odot a_j</math>, where <math>x \odot y = \sum\limits_{i=1}^{k} x_{i}y_i</math> (mod 2). It is easy to see that every codeword has a [[Hamming distance]] of <math>\frac{n}{2}</math> from every other codeword.
Line 75:
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 <math>\frac{1}{4}</math> of its bits. For <math>\rho < \frac{1}{4}</math>, if the codeword is corrupted in a <math>\rho</math> fraction of places, a local decoding algorithm can recover the <math>i^{th}</math> bit of the original message with probability <math>1 - 2\rho</math>.
Proof: Given a codeword <math>H</math> and an index <math>i</math>, the algorithm to recover the <math>i^{th}</math> bit of the original message <math>x</math> works as follows:
Let <math>e^j</math> refer to the vector in <math>\{0, 1\}^k</math> that has 1 in the <math>j^{th}</math> position and 0s elsewhere. For <math>y \in \{0, 1\}^k</math>, <math>f(y)</math> denotes the single bit in <math>H</math> that corresponds to <math>x \odot y</math>. The algorithm chooses a random vector <math>y \in \{0, 1\}^k</math> and the vector <math>y' = y \otimes e^i</math> (where <math>\otimes</math> denotes [[bitwise XOR]]). The algorithm outputs <math>f(y) \otimes f(y')</math> (mod 2).
Line 116:
Each individual query is distributed uniformly at random over the codeword. Thus, if the codeword is corrupted in at most a <math>\delta</math> 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 <math>1 - (d+1)\delta</math>.<ref name=LDC1/>
For other decoding algorithms, see
== References ==
| |||