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.