Content deleted Content added
Fix harvnb thinko |
SJ Defender (talk | contribs) m Disambiguated: affine → affine geometry |
||
Line 77:
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>
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 geometry|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/>
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/>
| |||