Klim Efremenko

Locally Decodable Codes (LDC) 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 [Yek08] Yekhanin constructs a 3-query LDC with sub-exponential length of size exp(exp(O( log n/log log n ))). 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 sub-exponential codeword length. In addition our construction reduces the codeword length. We give a construction of a 3-query LDC with codeword length exp(exp(O(√log n log log n))). Our construction also can be extended to a higher number of queries. We give a 2^r-query LDC with length of exp(exp(O( r√log n(log log n)^r-1))).