דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Theory Seminar: 3-Query Locally Decodable Codes of Subexponential Length
event speaker icon
קלים אפרמנקו (מכון ויצמן למדע)
event date icon
יום רביעי, 18.3.2009, 18:30
event location icon
חדר 337, בניין טאוב למדעי המחשב
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.
[בחזרה לאינדקס האירועים]