Erasures vs. Errors in Local Decoding and Property Testing
Erasures vs. Errors in Local Decoding and Property Testing
复制标题
本地解码和属性测试中的擦除与错误
DOI：
10.4230/lipics.itcs.2019.63
复制
发表时间：
2019
影响因子：
1
通讯作者：
Nithin M. Varma
中科院分区：
文献类型：
--
作者：
Sofya Raskhodnikova;Noga Ron;Nithin M. Varma
我们开始研究擦除在局部解码中的作用，并使用我们的理解来证明擦除弹性测试和容错性能测试之间的区别。存在错误时的局部译码已被广泛研究，但在存在删除的情况下还没有明确地考虑。出于在性质测试中的应用，我们从存在删除的情况下的局部列表解码开始我们的研究。我们证明了Goldreich和Levin关于Hadamard码的局部列表可译码的一个著名结果的模拟。具体地说，我们证明了Hadamard码在任意接近1的恒定擦除分数的情况下是局部列表可译码的，其列表大小和查询复杂度都好于Goldreich-Levin定理。我们使用这一结果来展示一种性质，该性质可以在存在擦除的情况下利用与输入长度无关的多个查询来测试，但是需要依赖于输入长度n的多个查询来进行容错测试。我们进一步研究了抗删除的近似局部列表可译码，并使用它们通过构造一个性质来加强我们的分离，该性质在存在删除的情况下可以用恒定数量的查询来测试，但需要n个Ω(1)查询来进行容错测试。接下来，我们研究了在存在错误和存在删除的情况下局部解码之间的一般关系。我们观察到，在存在错误的情况下工作的每个本地(唯一的或列表的)可译码也在存在两倍的擦除(具有相同的参数直到恒定因子)的情况下工作。我们证明了在另一个方向上对于局部可译码(具有唯一译码)也有一个含义：具体地说，存在在存在删除的情况下工作的局部可译码意味着存在在存在错误且具有相关参数的局部可译码。然而，对于本地列表可解码代码1，是否存在另一方向的隐含仍然是开放的。我们将这个问题与本地解码中的其他未决问题联系起来。2012年ACM主题分类计算理论→流、次线性和近线性时间算法、计算数学→编码理论
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Ω(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 codes1. We relate this question to other open questions in local decoding. 2012 ACM Subject Classification Theory of computation → Streaming, sublinear and near linear time algorithms, Mathematics of computing → Coding theory
本地解码和属性测试中的擦除与错误
影响因子：
1
作者：
Raskhodnikova, Sofya;Ron‐Zewi, Noga;Varma, Nithin
通讯作者：
Varma, Nithin
具有建议的自适应程序的不可区分性以及硬度放大证明的下限
DOI：
10.1109/focs.2018.00094
发表时间：
2018
期刊：
FOCS
影响因子：
--
作者：
Grinberg, Aryeh;Shaltiel, Ronen;Viola, Emanuele
通讯作者：
Viola, Emanuele