Content deleted Content added
Link suggestions feature: 3 links added. |
|||
Line 1:
{{Short description|Type of error-correcting 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 [[Code word (communication)|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|author1=Rafail Ostrovsky |author2=Omkant Pandey |author3=Amit Sahai }}</ref><ref name=newLDCPIR>Sergey Yekhanin. New locally decodable codes and private information retrieval schemes, [http://www.eccc.hpi-web.de/eccc-reports/2006/TR06-127/index.html Technical Report ECCC TR06-127], 2006.</ref>
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 code]]s, though there is some overlap between the two.<ref name=LTCvsLDC>{{cite web|url=http://eccc.hpi-web.de/report/2010/130/revision/1/download/ |title=Locally Testable vs. Locally Decodable Codes |first1=Tali|last1=Kaufman|author1-link=Tali Kaufman|first2=Michael|last2= Viderman }}</ref>
Line 26:
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 |title=Locally Decodable Codes |author=Sergey Yekhanin}}</ref><ref name=LDC2>{{cite web|url=https://www.iacr.org/workshops/tcc2012/survey_tcc.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/>{{Update inline|reason=This line is no outdated - there are many results since 2011|date=December 2016}} 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 72:
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>
| |||