• Calendar

January 14, Wednesday
12:00 – 14:00

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 ~cite{Yekhanin08} Yekhanin constructs a $3$-query LDC with sub-exponential length of size $exp(exp(O(frac{log n}{loglog n})))$. However, this construction requires a conjecture that there are infinitely many Mersenne primes. In this paper we give an unconditional $3$-query LDC construction with a 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 by cite{Grolmusz00} which hold only over composite numbers.