### Towards 3-query locally decodable codes of subexponential lengthTowards 3-query locally decodable codes of subexponential length

Access Restriction
Subscribed

 Author Yekhanin, Sergey Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2008 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Locally decodable codes ♦ Mersenne primes ♦ Private information retrieval Abstract A $\textit{q}-query$ Locally Decodable Code (LDC) encodes an $\textit{n}-bit$ message $\textit{x}$ as an $\textit{N}-bit$ codeword $\textit{C}(\textit{x}),$ such that one can probabilistically recover any bit $x_{i}$ of the message by querying only $\textit{q}$ bits of the codeword $\textit{C}(\textit{x}),$ even after some constant fraction of codeword bits has been corrupted. We give new constructions of three query LDCs of vastly shorter length than that of previous constructions. Specifically, given any Mersenne prime $\textit{p}$ = $2^{t}$ ™ 1, we design three query LDCs of length $\textit{N}$ = $exp(O(n^{1/t})),$ for every $\textit{n}.$ Based on the largest known Mersenne prime, this translates to a length of less than $exp(\textit{O}(\textit{n}10$ ™ 7)) compared to $exp(O(n^{1/2}))$ in the previous constructions. It has often been conjectured that there are infinitely many Mersenne primes. Under this conjecture, our constructions yield three query locally decodable codes of length $\textit{N}$ = $exp(\textit{n}\textit{O}(1/log$ log $\textit{n}))$ for infinitely many $\textit{n}.$ We also obtain analogous improvements for Private Information Retrieval (PIR) schemes. We give 3-server PIR schemes with communication complexity of $\textit{O}(\textit{n}10$ ™ 7) to access an $\textit{n}-bit$ database, compared to the previous best scheme with complexity $O(n^{1/5.25}).$ Assuming again that there are infinitely many Mersenne primes, we get 3-server PIR schemes of communication complexity $\textit{n}\textit{O}(1/log$ $log\textit{n}))$ for infinitely many $\textit{n}.$ Previous families of LDCs and PIR schemes were based on the properties of low-degree multivariate polynomials over finite fields. Our constructions are completely different and are obtained by constructing a large number of vectors in a small dimensional vector space whose inner products are restricted to lie in an algebraically nice set. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2008-02-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 55 Issue Number 1 Page Count 16 Starting Page 1 Ending Page 16

#### Open content in new tab

Source: ACM Digital Library