The Library
On the power of relaxed local decoding algorithms
Tools
Tools
Tools
Gur, Tom and Lachish, Oded (2021) On the power of relaxed local decoding algorithms. SIAM Journal on Computing, 50 (2). pp. 788-813. doi:10.1137/19M1307834
|
PDF
WRAP-on-power-relaxed-local-decoding-algorithms-Gur-2021.pdf - Accepted Version - Requires a PDF viewer. Download (1101Kb) | Preview |
Official URL: https://doi.org/10.1137/19M1307834
Abstract
A locally decodable code (LDC) $C \colon \{0,1\}^k \to \{0,1\}^n$ is an error correcting code wherein individual bits of the message can be recovered by only querying a few bits of a noisy codeword. LDCs found a myriad of applications both in theory and in practice, ranging from probabilistically checkable proofs to distributed storage. However, despite nearly two decades of extensive study, the best known constructions of $O(1)$-query LDCs have superpolynomial blocklength. The notion of relaxed LDCs is a natural relaxation of LDCs, which aims to bypass the foregoing barrier by requiring local decoding of nearly all individual message bits, yet allowing decoding failure (but not error) on the rest. State of the art constructions of $O(1)$-query relaxed LDCs achieve blocklength $n = O\left(k^{1+ \gamma}\right)$ for an arbitrarily small constant $\gamma$. We prove a lower bound which shows that $O(1)$-query relaxed LDCs cannot achieve blocklength $n = k^{1+ o(1)}$. This resolves an open problem raised by Goldreich in 2004.
| Item Type: | Journal Article | ||||||
|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
| Library of Congress Subject Headings (LCSH): | Data encryption (Computer science), Computer networks, Computer algorithms, Algorithms | ||||||
| Journal or Publication Title: | SIAM Journal on Computing | ||||||
| Publisher: | Society for Industrial and Applied Mathematics | ||||||
| ISSN: | 0097-5397 | ||||||
| Official Date: | 18 April 2021 | ||||||
| Dates: |
|
||||||
| Volume: | 50 | ||||||
| Number: | 2 | ||||||
| Page Range: | pp. 788-813 | ||||||
| DOI: | 10.1137/19M1307834 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Reuse Statement (publisher, data, author rights): | First Published in SIAM Journal on Computing in 50(2), published by the Society for Industrial and Applied Mathematics (SIAM). Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. | ||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||
| Copyright Holders: | © 2021, Society for Industrial and Applied Mathematics | ||||||
| RIOXX Funder/Project Grant: |
|
||||||
| Version or Related Resource: | https://dl.acm.org/doi/10.5555/3381089.3381172 | ||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
