Thumbnail
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

   Open content in new tab
Source: ACM Digital Library