Asadi, Vahid R. ;
Shinkar, Igor
Relaxed Locally Correctable Codes with Improved Parameters
Abstract
Locally decodable codes (LDCs) are errorcorrecting codes C: Σ^k → Σⁿ that admit a local decoding algorithm that recovers each individual bit of the message by querying only a few bits from a noisy codeword. An important question in this line of research is to understand the optimal tradeoff between the query complexity of LDCs and their block length. Despite importance of these objects, the best known constructions of constant query LDCs have superpolynomial length, and there is a significant gap between the best constructions and the known lower bounds in terms of the block length.
For many applications it suffices to consider the weaker notion of relaxed LDCs (RLDCs), which allows the local decoding algorithm to abort if by querying a few bits it detects that the input is not a codeword. This relaxation turned out to allow decoding algorithms with constant query complexity for codes with almost linear length. Specifically, [{BenSasson} et al., 2006] constructed a qquery RLDC that encodes a message of length k using a codeword of block length n = O_q(k^{1+O(1/√q)}) for any sufficiently large q, where O_q(⋅) hides some constant that depends only on q.
In this work we improve the parameters of [{BenSasson} et al., 2006] by constructing a qquery RLDC that encodes a message of length k using a codeword of block length O_q(k^{1+O(1/{q})}) for any sufficiently large q. This construction matches (up to a multiplicative constant factor) the lower bounds of [Jonathan Katz and Trevisan, 2000; Woodruff, 2007] for constant query LDCs, thus making progress toward understanding the gap between LDCs and RLDCs in the constant query regime.
In fact, our construction extends to the stronger notion of relaxed locally correctable codes (RLCCs), introduced in [Tom Gur et al., 2018], where given a noisy codeword the correcting algorithm either recovers each individual bit of the codeword by only reading a small part of the input, or aborts if the input is detected to be corrupt.
BibTeX  Entry
@InProceedings{asadi_et_al:LIPIcs.ICALP.2021.18,
author = {Asadi, Vahid R. and Shinkar, Igor},
title = {{Relaxed Locally Correctable Codes with Improved Parameters}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {18:118:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771955},
ISSN = {18688969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14087},
URN = {urn:nbn:de:0030drops140878},
doi = {10.4230/LIPIcs.ICALP.2021.18},
annote = {Keywords: Algorithmic coding theory, consistency test using random walk, ReedMuller code, relaxed locally decodable codes, relaxed locally correctable codes}
}
02.07.2021
Keywords: 

Algorithmic coding theory, consistency test using random walk, ReedMuller code, relaxed locally decodable codes, relaxed locally correctable codes 
Seminar: 

48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Issue date: 

2021 
Date of publication: 

02.07.2021 