The zero-rate threshold for adversarial bit-deletions is less than 1/2
The zero-rate threshold for adversarial bit-deletions is less than 1/2
复制标题
对抗性位删除的零率阈值小于 1/2
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Ray Li
中科院分区：
文献类型：
--
作者：
V. Guruswami;Xiaoyu He;Ray Li
证明了存在一个绝对常数δ> 0，使得任何容许（1/2 - δ）N$敌对删除的二进制码<tex>$C$</tex>N ${0，1} <sup>N</sup><tex></tex>必须满足|C| ≤ 2 <sup>polylog</sup><tex>$N$</tex>，因此速率渐近接近0。这是第一个常数分数改进的平凡的界限，代码容忍<tex>$N$</tex>/2敌对删除必须有率渐近为0。等价地，我们证明了存在绝对常数<tex>$A$</tex>和δ> 0，使得任何2<sup>log</sup><sup>A</sup> N二进制串的集合<tex>$C$</tex>n {0，1}必须包含两个串<tex>$c$</tex>和c'，它们的最长公共子序列的长度至少为（1/2 + δ）N.作为直接的推论，我们表明，容忍对抗性缺失分数1 -（1 + 2δ）/<tex>$q$的</tex>q元代码也必须具有接近0的速率。我们的技术包括字符串正则参数和结构引理，分类二进制字符串的振荡模式。利用这些工具，我们可以在任何大型代码中找到具有相似振荡模式的两个字符串，并利用它们来找到一个长的公共子序列。
We prove that there exists an absolute constant 6 > 0 such any binary code <tex>$C$</tex> ⊂ {0, 1}<sup>N</sup> tolerating (1/2 - δ) <tex>$N$</tex> adversarial deletions must satisfy| C| ≤ 2<sup>polylog</sup><tex>$N$</tex> and thus have rate asymptotically approaching 0. This is the first constant fraction improvement over the trivial bound that codes tolerating <tex>$N$</tex> /2 adversarial deletions must have rate going to 0 asymptotically. Equivalently, we show that there exists absolute constants <tex>$A$</tex> and 6 > 0 such that any set <tex>$C$</tex> ⊂ {0, 1} of 2<sup>log</sup><sup>A</sup> N binary strings must contain two strings <tex>$c$</tex> and c’ whose longest common subsequence has length at least (1/2 + δ) N. As an immediate corollary, we show that q-ary codes tolerating a fraction 1 - (1 + 2δ) / <tex>$q$</tex> of adversarial deletions must also have rate approaching 0. Our techniques include string regularity arguments and a structural lemma that classifies binary strings by their oscillation patterns. Leveraging these tools, we find in any large code two strings with similar oscillation patterns, which is exploited to find a long common subsequence.
登录
查看更多内容
在遗忘模型和在线模型中针对删除进行编码
影响因子：
2.5
作者：
Guruswami, Venkatesan;Li, Ray
通讯作者：
Li, Ray
同步字符串：显式构造、本地解码和应用
DOI：
10.1145/3188745.3188940
发表时间：
2018
期刊：
and applications
影响因子：
--
作者：
Haeupler, Bernhard;Shahrasbi, Amirbehshad
通讯作者：
Shahrasbi, Amirbehshad
最佳文档交换以及插入和删除的新代码
DOI：
10.1109/focs.2019.00029
发表时间：
2019
期刊：
IEEE Symposium on Foundations of Computer Science
影响因子：
--
作者：
Haeupler, Bernhard
通讯作者：
Haeupler, Bernhard
DOI：
10.1109/isit44484.2020.9174009
发表时间：
2020
期刊：
International Symposium on Information Theory and its Applications
影响因子：
--
作者：
Sima, J.;Gabrys, R.;Bruck, J.
通讯作者：
Bruck, J.
影响因子：
2.5
作者：
Cheraghchi, Mahdi;Ribeiro, Joao
通讯作者：
Ribeiro, Joao