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 >>>