__
TR08-069 | 5th August 2008 00:00
__

#### 3-Query Locally Decodable Codes of Subexponential Length

**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.