Towards 3-query locally decodable codes of subexponential length

Journal of the ACM | , Vol 55(1): pp. 1-16

A q 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 xi of the message by querying only q bits of the codeword C(x), even
after some constant fraction of codeword bits has been corrupted.