Content deleted Content added
Line 155:
==Local decodability ==
A [[locally decodable]] code is a code that allows a single bit of the original message to be recovered with high probability by only looking at a small portion of the received word.
A code is <math>q</math>-query [[locally decodable]] if a message bit, <math>x_i</math>, can be recovered by checking <math>q</math> bits of the received word. More formally, a code, <math>C: \{0,1\}^k \rightarrow \{0,1\}^n</math>, is <math>(q, \delta\geq 0, \epsilon\geq 0)</math>-locally decodable, if there exists a probabilistic decoder, <math>D:\{0,1\}^n \rightarrow \{0,1\}^k</math>, such that ''(Note: <math>\Delta(x,y)</math> represents the [[Hamming distance]] between vectors <math>x</math> and <math>y</math>)'': <math>\forall x \in \{0,1\}^k, \forall y \in \{0,1\}^n</math>, <math>\Delta(y, C(x)) \leq \delta n</math> implies that <math>Pr[D(y)_i = x_i] \geq \frac{1}{2} + \epsilon, \forall i \in [k]</math>
| |||