Abstract:
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 recent work ~\cite{Yekhanin08} Yekhanin constructs a $3$-query LDC with sub-exponential length of size $\exp(\exp(O(\frac{\log n}{\log\log n})))$. However, this construction requires a conjecture that there are infinity many Mersenne primes. In this paper we give an unconditional $3$-query LDC construction with shorter codeword length of $\exp(\exp(O(\sqrt{\log n \log \log n })))$. We also give a $2^r$-query LDC with length of $\exp(\exp(O(\sqrt[r]{\log n \log \log^{r-1} n })))$. The main ingredient in our construction is the existence of super-polynomial size set-systems with restricted intersections \cite{Grolmusz00} which holds only over composite numbers.