The Library
Relaxed locally correctable codes with nearly-linear block length and constant query complexity
Tools
Tools
Tools
Chiesa, Alessandro, Gur, Tom and Shinkar, Igor (2020) Relaxed locally correctable codes with nearly-linear block length and constant query complexity. In: 31st ACM-SIAM Symposium on Discrete Algorithms (SODA20), Salt Lake City, Utah, U.S., 5-8 Jan 2020. Published in: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA) 1395-1411 . ISBN 9781611975994. doi:10.1137/1.9781611975994.84
|
PDF
WRAP-relaxed-locally-correctable-codes-nearly-linear-block-length-constant-query-Gur-2019.pdf - Accepted Version - Requires a PDF viewer. Download (988Kb) | Preview |
Official URL: https://doi.org/10.1137/1.9781611975994.84
Abstract
Locally correctable codes (LCCs) are codes C: Σk → Σn which admit local algorithms that can correct any individual symbol of a corrupted codeword via a minuscule number of queries. One of the central problems in algorithmic coding theory is to construct O(1)-query LCC with minimal block length. Alas, state-of-the-art of such codes requires exponential block length to admit O(1)-query algorithms for local correction, despite much attention during the last two decades.
This lack of progress prompted the study of relaxed LCCs, which allow the correction algorithm to abort (but not err) on small fraction of the locations. This relaxation turned out to allow constant-query correction algorithms for codes with polynomial block length. Specifically, prior work showed that there exist O(1)-query relaxed LCCs that achieve nearly-quartic block length n = k4+α, for an arbitrarily small constant α > 0.
We construct an O(1)-query relaxed LCC with nearly-linear block length n = k1+α, for an arbitrarily small constant α > 0. This significantly narrows the gap between the lower bound which states that there are no O(1)-query relaxed LCCs with block length n = k1+o(1). In particular, this resolves an open problem raised by Gur, Ramnarayan, and Rothblum (ITCS 2018).
| Item Type: | Conference Item (Paper) | ||||||
|---|---|---|---|---|---|---|---|
| Alternative Title: | |||||||
| 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): | Coding theory, Computer algorithms | ||||||
| Journal or Publication Title: | Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA) | ||||||
| Publisher: | Society for Industrial and Applied Mathematics | ||||||
| ISBN: | 9781611975994 | ||||||
| Official Date: | January 2020 | ||||||
| Dates: |
|
||||||
| Page Range: | 1395-1411 | ||||||
| DOI: | 10.1137/1.9781611975994.84 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Reuse Statement (publisher, data, author rights): | Published in Proceedings of ACM-SIAM Symposium on Discrete Algorithms, published by the Society for Industrial and Applied Mathematics (SIAM) Copyright © 2019 by SIAM. Unauthorized reproduction of this article is prohibited. | ||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||
| Date of first compliant deposit: | 31 October 2019 | ||||||
| Date of first compliant Open Access: | 4 November 2019 | ||||||
| RIOXX Funder/Project Grant: |
|
||||||
| Conference Paper Type: | Paper | ||||||
| Title of Event: | 31st ACM-SIAM Symposium on Discrete Algorithms (SODA20) | ||||||
| Type of Event: | Conference | ||||||
| Location of Event: | Salt Lake City, Utah, U.S. | ||||||
| Date(s) of Event: | 5-8 Jan 2020 | ||||||
| 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
