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.ITCS.2019.63
URN: urn:nbn:de:0030-drops-101568
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10156/
Raskhodnikova, Sofya ;
Ron-Zewi, Noga ;
Varma, Nithin
Erasures vs. Errors in Local Decoding and Property Testing
Abstract
We initiate the study of the role of erasures in local decoding and use our understanding to prove a separation between erasure-resilient and tolerant property testing. Local decoding in the presence of errors has been extensively studied, but has not been considered explicitly in the presence of erasures.
Motivated by applications in property testing, we begin our investigation with local list decoding in the presence of erasures. We prove an analog of a famous result of Goldreich and Levin on local list decodability of the Hadamard code. Specifically, we show that the Hadamard code is locally list decodable in the presence of a constant fraction of erasures, arbitrary close to 1, with list sizes and query complexity better than in the Goldreich-Levin theorem. We use this result to exhibit a property which is testable with a number of queries independent of the length of the input in the presence of erasures, but requires a number of queries that depends on the input length, n, for tolerant testing. We further study approximate locally list decodable codes that work against erasures and use them to strengthen our separation by constructing a property which is testable with a constant number of queries in the presence of erasures, but requires n^{Omega(1)} queries for tolerant testing.
Next, we study the general relationship between local decoding in the presence of errors and in the presence of erasures. We observe that every locally (uniquely or list) decodable code that works in the presence of errors also works in the presence of twice as many erasures (with the same parameters up to constant factors). We show that there is also an implication in the other direction for locally decodable codes (with unique decoding): specifically, that the existence of a locally decodable code that works in the presence of erasures implies the existence of a locally decodable code that works in the presence of errors and has related parameters. However, it remains open whether there is an implication in the other direction for locally list decodable codes. We relate this question to other open questions in local decoding.
BibTeX - Entry
@InProceedings{raskhodnikova_et_al:LIPIcs:2018:10156,
author = {Sofya Raskhodnikova and Noga Ron-Zewi and Nithin Varma},
title = {{Erasures vs. Errors in Local Decoding and Property Testing}},
booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
pages = {63:1--63:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-095-8},
ISSN = {1868-8969},
year = {2018},
volume = {124},
editor = {Avrim Blum},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10156},
URN = {urn:nbn:de:0030-drops-101568},
doi = {10.4230/LIPIcs.ITCS.2019.63},
annote = {Keywords: Error-correcting codes, probabilistically checkable proofs (PCPs) of proximity, Hadamard code, local list decoding, tolerant testing}
}
|
Keywords: |
|
Error-correcting codes, probabilistically checkable proofs (PCPs) of proximity, Hadamard code, local list decoding, tolerant testing |
|
Collection: |
|
10th Innovations in Theoretical Computer Science Conference (ITCS 2019) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
08.01.2019 |
