### High-rate codes with sublinear-time decodingHigh-rate codes with sublinear-time decoding Access Restriction
Subscribed

 Author Kopparty, Swastik ♦ Saraf, Shubhangi ♦ Yekhanin, Sergey Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2014 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Multiplicity codes ♦ Derivatives ♦ Locally correctable codes ♦ Locally decodable codes ♦ Polynomials ♦ Sublinear-time algorithms Abstract Locally decodable codes are error-correcting codes that admit efficient decoding algorithms; any bit of the original message can be recovered by looking at only a small number of locations of a corrupted codeword. The tradeoff between the rate of a code and the locality/efficiency of its decoding algorithms has been well studied, and it has widely been suspected that nontrivial locality must come at the price of low rate. A particular setting of potential interest in practice is codes of constant rate. For such codes, decoding algorithms with locality $\textit{O}(\textit{k∈})$ were known only for codes of rate $\textit{∈}Ω(1/\textit{∈}),$ where $\textit{k}$ is the length of the message. Furthermore, for codes of rate > 1/2, no nontrivial locality had been achieved. In this article, we construct a new family of locally decodable codes that have very efficient local decoding algorithms, and at the same time have rate approaching 1. We show that for every $\textit{∈}$ > 0 and $\textit{α}$ > 0, for infinitely many $\textit{k},$ there exists a code $\textit{C}$ which encodes messages of length $\textit{k}$ with rate 1 ™ $\textit{α},$ and is locally decodable from a constant fraction of errors using $\textit{O}(\textit{k∈})$ queries and time. These codes, which we call multiplicity codes, are based on evaluating multivariate polynomials and their derivatives. Multiplicity codes extend traditional multivariate polynomial codes; they inherit the local-decodability of these codes, and at the same time achieve better tradeoffs and flexibility in the rate and minimum distance. 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 2014-09-08 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 61 Issue Number 5 Page Count 20 Starting Page 1 Ending Page 20

#### Open content in new tab

Source: ACM Digital Library