Locally decodable code: Difference between revisions

Revision as of 15:43, 2 December 2016

Revision as of 03:57, 20 March 2017

Line 59:

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 \otimesoplus e^i</math> (where <math>\otimesoplus</math> denotes [[bitwise XOR]]). The algorithm outputs <math>f(y) \otimesoplus f(y')</math> (mod 2).

Correctness: By linearity,

<math>(x \odot y) \otimesoplus (x \odot y') = (x \odot y) \otimesoplus (x \odot (y \otimesoplus e^i)) = (x \odot y) \otimesoplus (x \odot y) \otimesoplus (x \odot e^i) = x \odot e^i</math>

But <math>(x \odot e^i) = x_i</math>, so we just need to show that <math>f(y) = x \odot y</math> and <math>f(y') = x \odot y'</math> with good probability.