3-QUERY LOCALLY DECODABLE CODES OF SUBEXPONENTIAL LENGTH

Locally decodable codes (LDCs) allow one to decode any particular symbol of the input message by making a constant number of queries to a codeword, even if a constant fraction of the codeword is damaged. In a recent work [J. ACM, 55 (2008), article 1], Yekhanin constructs a 3-query LDC with subexponential length. However, this construction requires a conjecture that there are infinitely many Mersenne primes. In this paper, we give the first unconditional constant query LDC construction with subexponential codeword length. In addition, our construction reduces codeword length.