Kiran Kedlaya, Sergey Yekhanin

A k-query Locally Decodable Code (LDC) encodes an n-bit message x as an N-bit codeword C(x), such that one can probabilistically recover any bit x_i of the message by querying only k bits of the codeword C(x), even after some constant fraction of codeword bits has been corrupted. The major ... more >>>

Yeow Meng Chee, Tao Feng, San Ling, Huaxiong Wang, Liang Feng Zhang

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