Improved Constructions for Query-Efficient Locally Decodable Codes of Subexponential Length

A (k, δ, ε)-locally decodable code C: Fqⁿ \ ightarrow FqN is an error-correcting code that encodes x⃗=(x₁,x₂,…,xₙ) ∈ Fqⁿ to C(x⃗) ∈ FqN and has the following property: For any y⃗ ∈ FqN such that d(y⃗,C(x⃗)) ≤ δ N and each 1 ≤ i ≤ n, the symbol xi of $ of $x⃗$ can be recovered with probability at least 1 - ε by a randomized decoding algorithm looking at only k coordinates of $y⃗$. The efficiency of a (k, δ, ε)-locally decodable code $C:{ F}qⁿ \ ightarrow { F}qN$ is measured by the code length N and the number k of queries. For a k-query locally decodable code $C:{ F}qⁿ \ ightarrow { F}qN$, the code length N was conjectured to be exponential of n, i.e., N = exp(nΩ(1)), however, this was disproved. Yekhanin [In Proc. of STOC, 2007] showed that there exists a 3-query locally decodable code C: F₂ⁿ \ ightarrow F₂N such that N=exp(n1/log log n) assuming that infinitely many Mersenne primes exist. For a 3-query locally decodable code C: Fqⁿ \ ightarrow FqN, Efremenko [ECCC Report No.69, 2008] further reduced the code length to N=exp(n^O((log log n/ log n)1/2)), and in general showed that for any integer r > 1, there exists a 2r-query locally decodable code C: Fqⁿ \ ightarrow FqN such that N=exp(n^O((log log n/ log n)1-1/r)). In this paper, we will present improved constructions for query-efficient locally decodable codes by introducing a technique of “composition of locally decodable codes,” and show that for any integer r > 5, there exists a 9 · 2r-4-query locally decodable code C: Fqⁿ \ ightarrow FqN such that N=exp(n^O((log log n/ log n)1-1/r)).