QUERY-EFFICIENT LOCALLY DECODABLE CODES OF SUBEXPONENTIAL LENGTH

A k-query locally decodable code (LDC) C: Σn → ΓN encodes each message x into a codeword C(x) such that each symbol of x can be probabilistically recovered by querying only k coordinates of C(x), even after a constant fraction of the coordinates has been cor-rupted. Yekhanin (in J ACM 55:1–16, 2008) constructed a 3-query LDC of subexponential length, N = exp(exp(O(logn / log logn))), under the assumption that there are infinitely many Mersenne primes. Efremenko (in Proceedings of the 41st annual ACM symposium on theory of com-puting, ACM, New York, 2009) constructed a 3-query LDC of length N2 = exp(exp(O( log n log logn))) with no assumption, and a 2r-query LDC of length Nr = exp(exp(O ( r logn(log logn)r−1))), for every integer r ≥ 2. Itoh and Suzuki (in IEICE Trans Inform Syst E93-D 2:263– 270, 2010) gave a composition method in Efremenko’s framework an