Erasures versus errors in local decoding and property testing
Erasures versus errors in local decoding and property testing
复制标题
本地解码和属性测试中的擦除与错误
DOI：
10.1002/rsa.21031
复制
发表时间：
2021
影响因子：
1
通讯作者：
Varma, Nithin
中科院分区：
文献类型：
--
作者：
Raskhodnikova, Sofya;Ron‐Zewi, Noga;Varma, Nithin
我们开始研究擦除在局部解码中的作用，并利用我们的理解来证明擦除弹性和容忍性能测试之间的分离。我们首先研究了擦除存在下的本地化解码。我们证明了Goldreich和Levin关于Hadamard码的局部表可译码性的一个著名结果的类比。具体来说，我们证明了Hadamard代码在存在常量擦除分数的情况下是局部列表可解码的，任意接近1，列表大小和查询复杂性优于Goldreich-Levin定理。我们进一步研究了近似局部擦除列表可解码代码，并使用它们构建了一个擦除弹性可测试的属性，其查询复杂度与输入长度无关，但需要查询进行容错测试。我们还研究了在存在错误和存在擦除的情况下本地解码之间的一般关系。
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. We first investigate locallist‐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, arbitrarily close to 1, with list sizes and query complexity better than in the Goldreich–Levin theorem. We further studyapproximatelocally erasure list‐decodable codes and use them to construct a property that is erasure‐resiliently testable with query complexity independent of the input length, , but requires queries for tolerant testing. We also investigate the general relationship between local decoding in the presence of errors and in the presence of erasures.
登录
查看更多内容
DOI：
10.4230/lipics.itcs.2021.80
发表时间：
2021
期刊：
ITCS 2021
影响因子：
--
作者：
Levi, Amit;Pallavoor, Ramesh Krishnan;Raskhodnikova, Sofya;Varma, Nithin
通讯作者：
Varma, Nithin
具有次多项式查询复杂度的高速本地可校正和本地可测试代码
DOI：
10.1145/3051093
发表时间：
2017
期刊：
Journal of the ACM (JACM)
影响因子：
--
作者：
Swastik Kopparty;Or Meir;Noga Ron;Shubhangi Saraf
通讯作者：
Shubhangi Saraf
DOI：
10.1109/focs.2017.27
发表时间：
2017
期刊：
58th Annual IEEE Symposium on Foundations of Computer Science
影响因子：
--
作者：
Hemenway, Brett;Ron-Zewi, Noga;Wootters, Mary
通讯作者：
Wootters, Mary
影响因子：
1
作者：
Funda Ergün;Ravi Kumar;R. Rubinfeld
通讯作者：
R. Rubinfeld
宽容的本地可测试代码
DOI：
--
发表时间：
2005
期刊：
International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
影响因子：
--
作者：
V. Guruswami;A. Rudra
通讯作者：
A. Rudra