Content deleted Content added
harvnb, tweak cites |
Fix harvnb thinko |
||
Line 22:
}}</ref>
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 [[function composition|composition]]; see <ref name=AppCodingTheory/>). 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.<ref
== Length of Codeword and Query Complexity ==
Line 42 ⟶ 40:
One of the applications of locally decodable codes in [[Computational complexity theory|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=AppCodingTheory/><ref name=LDC1/><ref>{{
=== Private Information Retrieval Schemes ===
Line 72 ⟶ 68:
Since <math>y</math> and <math>y'</math> are uniformly distributed (even though they are dependent), the [[union bound]] implies that <math>f(y) = x \odot y</math> and <math>f(y') = x \odot y'</math> with probability at least <math>1 - 2\rho</math>. Note: to amplify the probability of success, one can repeat the procedure with different random vectors and take the majority answer.
<ref>{{
=== The Reed–Muller code ===
Line 81 ⟶ 75:
More formally, let <math>\mathbb{F}</math> be a finite field, and let <math>l, d</math> be numbers with <math>d < |\mathbb{F}|</math>. The Reed-Muller code with parameters <math>\mathbb{F}, l, d</math> is the function RM : <math>\mathbb{F}^{\binom{l+d}{d}} \rightarrow \mathbb{F}^{|\mathbb{F}|^l}</math> that maps every <math>l</math>-variable polynomial <math>P</math> over <math>\mathbb{F}</math> of total degree <math>d</math> to the values of <math>P</math> on all the inputs in <math>\mathbb{F}^l</math>. That is, the input is a polynomial of the form
<math>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}</math>
specified by the interpolation of the <math>\binom{l+d}{d}</math> values of the predefined points and the output is the sequence <math>\{P(x_1, \ldots, x_l)\}</math> for every <math>x_1, \ldots, x_l \in \mathbb{F}</math>.<ref name=AB1942>{{
To recover the value of a degree <math>d</math> polynomial at a point <math>w \in \mathbb{F}^n</math>, the local decoder shoots a random [[affine]] line through <math>w</math>. Then it picks <math>d + 1</math> points on that line, which it uses to interpolate the polynomial and then evaluate it at the point where the result is <math>w</math>. To do so, the algorithm picks a vector <math>v \in \mathbb{F}^n</math> uniformly at random and considers the line <math>L = \{w + \lambda v \mid \lambda \in \mathbb{F}\}</math> through <math>w</math>. The algorithm picks an arbitrary subset <math>S</math> of <math>\mathbb{F}</math>, where <math>|S| = d+1</math>, and queries coordinates of the codeword that correspond to points <math>w+\lambda v</math> for all <math>\lambda \in S</math> and obtains values <math>\{e_{\lambda}\}</math>. Then it uses polynomial interpolation to recover the unique univariate polynomial <math>h</math> with degree less than or equal to <math>d</math> such that <math>h(\lambda) = e_{\lambda}</math> for all <math>\lambda \in S</math>. Then, to get the value of <math>w</math>, it just evaluates <math>h(0)</math>. To recover a single value of the original message, one chooses <math>w</math> to be one of the points that defines the polynomial.<ref name=LDC1/><ref name=AB1942/>
| |||