3-Query Locally Decodable Codes of Subexponential Length
by Klim Efremenko
Oded's comments
This celebrated work is an obvious choice and requires no introduction.
(I'm happy to add it to my collection of choices,
based on the fact that it was presented today at our formal seminar.)
I wish, however, to emphasize two aspects.
Firstly, that the exposition of the construction,
which does build on Yekhanin's ideas, is quite accessible.
Secondly, that, in contrast to Yekhanin's construction,
the current construction scheme has the pleasing feature
of benefitting from more queries
(i.e., it yields shorter lengths when more queries are allowed).
The original 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 a recent work
Yekhanin constructs a $3$-query LDC with sub-exponential length of size
$\exp(\exp(O({\log n\over \log\log n})))$. However, this construction requires
a conjecture that there are infinitely many Mersenne primes. In this paper we
give the first unconditional constant query LDC construction with
subexponantial codeword length. In addition our construction reduces codeword
length. We give construction of $3$-query LDC with codeword length
$\exp(\exp(O(\sqrt{\log n \log \log n })))$. Our construction also could be
extended to higher number of queries. We give a $2^r$-query LDC with
length of $\exp(\exp(O(\sqrt[r]{\log n (\log \log n)^{r-1} })))$.
Back to
list of Oded's choices.