Locally decodable code: Difference between revisions

Revision as of 19:29, 2 June 2016

Revision as of 19:13, 23 August 2016

Line 27:

The rate of a code refers to the ratio between its message length and codeword length: <math>\frac{|x|}{|C(x)|}</math>, and the number of queries required to recover 1 bit of the message is called the query complexity of a code.

The rate of a code is inversely related to the query complexity, but the exact shape of this tradeoff is a major open problem.<ref name=LDC1>{{cite web|url=http://research.microsoft.com/en-us/um/people/yekhanin/Papers/LDC_now.pdf |format=PDF |title=Locally Decodable Codes |author=Sergey Yekhanin}}</ref><ref name=LDC2>{{cite web|url=httphttps://www.iacr.org/workshops/tcc2012/survey_tcc.pdf |format=PDF |title=Locally Decodable Codes |author=Sergey Yekhanin}}</ref> It is known that there are no LDCs that query the codeword in only one position, and that the optimal codeword size for query complexity 2 is exponential in the size of the original message.<ref name=LDC1/> However, there are no known tight lower bounds for codes with query complexity greater than 2. Approaching the tradeoff from the side of codeword length, the only known codes with codeword length proportional to message length have query complexity <math>k^\epsilon</math> for <math>\epsilon > 0</math>.<ref name=LDC1/> There are also codes in between, that have codewords polynomial in the size of the original message and polylogarithmic query complexity.<ref name=LDC1/>

== Applications ==

Line 73:

The main idea behind local decoding of [[Reed-Muller codes]] is [[polynomial interpolation]]. The key concept behind a Reed-Muller code is a multivariate polynomial of degree <math>d</math> on <math>l</math> variables. The message is treated as the evaluation of a polynomial at a set of predefined points. To encode these values, a polynomial is extrapolated from them, and the codeword is the evaluation of that polynomial on all possible points. At a high level, to decode a point of this polynomial, the decoding algorithm chooses a set <math>S</math> of points on a line that passes through the point of interest <math>x</math>. It then queries the codeword for the evaluation of the polynomial on points in <math>S</math> and interpolates that polynomial. Then it is simple to evaluate the polynomial at the point that will yield <math>x</math>. This roundabout way of evaluating <math>x</math> is useful because (a) the algorithm can be repeated using different lines through the same point to improve the probability of correctness, and (b) the queries are uniformly distributed over the codeword.

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>{{harvnb|Arora|Barak|2009|loc=Section 19.4.2}}</ref>