A $k$-query locally decodable code (LDC)
$\textbf{C}:\Sigma^{n}\rightarrow \Gamma^{N}$ encodes each message $x$ into
a codeword $\textbf{C}(x)$ such that each symbol of $x$ can be probabilistically
recovered by querying only $k$ coordinates of $\textbf{C}(x)$, even after a
constant fraction of the coordinates have been corrupted.
Yekhanin (2008)
constructed a $3$-query LDC ... more >>>