Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR08-069 | 5th August 2008 00:00

3-Query Locally Decodable Codes of Subexponential Length

RSS-Feed




TR08-069
Authors: Klim Efremenko
Publication: 5th August 2008 16:20
Downloads: 1710
Keywords: 


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.



ISSN 1433-8092 | Imprint