ECCC-Report TR08-069https://eccc.weizmann.ac.il/report/2008/069Comments and Revisions published for TR08-069en-usTue, 05 Aug 2008 16:20:41 +0300
Paper TR08-069
| 3-Query Locally Decodable Codes of Subexponential Length |
Klim Efremenko
https://eccc.weizmann.ac.il/report/2008/069Locally 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.
Tue, 05 Aug 2008 16:20:41 +0300https://eccc.weizmann.ac.il/report/2008/069