Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: 3-Query Locally Decodable Codes of Subexponential Length
event speaker icon
Klim Efremenko, Weizmann Institute
event date icon
Wednesday, 18.03.2009, 18:30
event location icon
Room 337-8 Taub Bld.
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}{\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.