License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2020.16
URN: urn:nbn:de:0030-drops-132577
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13257/
Block, Alexander R. ;
Blocki, Jeremiah ;
Grigorescu, Elena ;
Kulkarni, Shubhang ;
Zhu, Minshen
Locally Decodable/Correctable Codes for Insertions and Deletions
Abstract
Recent efforts in coding theory have focused on building codes for insertions and deletions, called insdel codes, with optimal trade-offs between their redundancy and their error-correction capabilities, as well as efficient encoding and decoding algorithms.
In many applications, polynomial running time may still be prohibitively expensive, which has motivated the study of codes with super-efficient decoding algorithms. These have led to the well-studied notions of Locally Decodable Codes (LDCs) and Locally Correctable Codes (LCCs). Inspired by these notions, Ostrovsky and Paskin-Cherniavsky (Information Theoretic Security, 2015) generalized Hamming LDCs to insertions and deletions. To the best of our knowledge, these are the only known results that study the analogues of Hamming LDCs in channels performing insertions and deletions.
Here we continue the study of insdel codes that admit local algorithms. Specifically, we reprove the results of Ostrovsky and Paskin-Cherniavsky for insdel LDCs using a different set of techniques. We also observe that the techniques extend to constructions of LCCs. Specifically, we obtain insdel LDCs and LCCs from their Hamming LDCs and LCCs analogues, respectively. The rate and error-correction capability blow up only by a constant factor, while the query complexity blows up by a poly log factor in the block length.
Since insdel locally decodable/correctble codes are scarcely studied in the literature, we believe our results and techniques may lead to further research. In particular, we conjecture that constant-query insdel LDCs/LCCs do not exist.
BibTeX - Entry
@InProceedings{block_et_al:LIPIcs:2020:13257,
author = {Alexander R. Block and Jeremiah Blocki and Elena Grigorescu and Shubhang Kulkarni and Minshen Zhu},
title = {{Locally Decodable/Correctable Codes for Insertions and Deletions}},
booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
pages = {16:1--16:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-174-0},
ISSN = {1868-8969},
year = {2020},
volume = {182},
editor = {Nitin Saxena and Sunil Simon},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13257},
URN = {urn:nbn:de:0030-drops-132577},
doi = {10.4230/LIPIcs.FSTTCS.2020.16},
annote = {Keywords: Locally decodable/correctable codes, insert-delete channel}
}
|
Keywords: |
|
Locally decodable/correctable codes, insert-delete channel |
|
Collection: |
|
40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
04.12.2020 |
