The Library
Relaxed locally correctable codes
Tools
Gur, Tom, Ramnarayan, Govind and Rothblum, Ron D. (2018) Relaxed locally correctable codes. In: 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Published in: 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), 94 27:1-27:11. ISBN 9783959770606. doi:10.4230/LIPIcs.ITCS.2018.27 ISSN 1868-8969.
|
PDF
WRAP-Relaxed-locally-correctable-codes-Gur-2018.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (537Kb) | Preview |
Official URL: http://drops.dagstuhl.de/opus/volltexte/2018/8315
Abstract
Locally decodable codes (LDCs) and locally correctable codes (LCCs) are error-correcting codes in which individual bits of the message and codeword, respectively, can be recovered by querying only few bits from a noisy codeword. These codes have found numerous applications both in theory and in practice. A natural relaxation of LDCs, introduced by Ben-Sasson et al. (SICOMP, 2006), allows the decoder to reject (i.e., refuse to answer) in case it detects that the codeword is corrupt. They call such a decoder a relaxed decoder and construct a constant-query relaxed LDC with almost-linear blocklength, which is sub-exponentially better than what is known for (full-fledged) LDCs in the constant-query regime. We consider an analogous relaxation for local correction. Thus, a relaxed local corrector reads only few bits from a (possibly) corrupt codeword and either recovers the desired bit of the codeword, or rejects in case it detects a corruption. We give two constructions of relaxed LCCs in two regimes, where the first optimizes the query complexity and the second optimizes the rate: 1. Constant Query Complexity: A relaxed LCC with polynomial blocklength whose corrector only reads a constant number of bits of the codeword. This is a sub-exponential improvement over the best constant query (full-fledged) LCCs that are known. 2. Constant Rate: A relaxed LCC with constant rate (i.e., linear blocklength) with quasi-polylogarithmic query complexity. This is a nearly sub-exponential improvement over the query complexity of a recent (full-fledged) constant-rate LCC of Kopparty et al. (STOC, 2016).
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | ||||||
Journal or Publication Title: | 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) | ||||||
Publisher: | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik | ||||||
Place of Publication: | Dagstuhl, Germany | ||||||
ISBN: | 9783959770606 | ||||||
ISSN: | 1868-8969 | ||||||
Official Date: | 5 January 2018 | ||||||
Dates: |
|
||||||
Volume: | 94 | ||||||
Page Range: | 27:1-27:11 | ||||||
DOI: | 10.4230/LIPIcs.ITCS.2018.27 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||
Date of first compliant deposit: | 11 April 2019 | ||||||
Date of first compliant Open Access: | 11 April 2019 | ||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) | ||||||
Type of Event: | Conference |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year