Synchronization Strings: List Decoding for Insertions and Deletions
Synchronization Strings: List Decoding for Insertions and Deletions
复制标题
DOI：
10.4230/lipics.icalp.2018.76
复制
发表时间：
2018-02
期刊：
影响因子：
--
通讯作者：
Bernhard Haeupler;Amirbehshad Shahrasbi;M. Sudan
中科院分区：
文献类型：
--
作者：
Bernhard Haeupler;Amirbehshad Shahrasbi;M. Sudan
我们研究在插入和删除下可列出的代码。具体来说，我们考虑了某些有限字母$ Q $的代码字可能会遭受$ \ delta $的对抗性删除和$ \ gamma $的对抗插入的部分。如果有一种（高效的）算法，则可以将代码定为$ l $ list-cododem，鉴于收到的单词，该算法报告了包含原始代码字的$ l $ codeWords的列表。使用前两个作者提出的同步字符串的概念[Stoc 2017]，我们显示了一些令人惊讶的结果。我们证明，每$ 0 \ leq \ delta 0 $都有有效的费率代码$ 1- \ delta- \ epsilon $和常数字母（因此$ q = o _ {\ delta，\ gamma，\ gamma，\ epsilon}（1）$）和子量表列表的大小。我们强调的是，插入的比例可以任意大，并且速率与该参数无关。我们的结果阐明了从错误校正的角度来看，插入和删除的影响之间的显着不对称性：而删除代码速率的删除成本，插入成本是由对手而不是代码承担的！我们还证明了列表可调INSDEL代码的参数的几个紧密界限。特别是，我们表明，在$ \ epsilon^{ - 1} $中，INSDEL代码的字母大小必须成倍地大，其中$ \ epsilon $是上面容量的差距。我们的结果甚至适用于唯一编码容量等于列表编码容量的设置，并且在这样做时，它表明字母尺寸在容量之间的差距上需要成倍地大。这与锤误差模型形成了鲜明的对比，其中$ \ epsilon^{ - 1} $的字母大小多项式对于唯一解码来说足够了，并且还表明，在先前构建的INSDEL代码的先前作品中，指数级依赖于字母尺寸实际上是必不可少的！
We study codes that are list-decodable under insertions and deletions. Specifically, we consider the setting where a codeword over some finite alphabet of size $q$ may suffer from $\delta$ fraction of adversarial deletions and $\gamma$ fraction of adversarial insertions. A code is said to be $L$-list-decodable if there is an (efficient) algorithm that, given a received word, reports a list of $L$ codewords that include the original codeword. Using the concept of synchronization strings, introduced by the first two authors [STOC 2017], we show some surprising results. We show that for every $0\leq\delta 0$ there exist efficient codes of rate $1-\delta-\epsilon$ and constant alphabet (so $q=O_{\delta,\gamma,\epsilon}(1)$) and sub-logarithmic list sizes. We stress that the fraction of insertions can be arbitrarily large and the rate is independent of this parameter. Our result sheds light on the remarkable asymmetry between the impact of insertions and deletions from the point of view of error-correction: Whereas deletions cost in the rate of the code, insertion costs are borne by the adversary and not the code! We also prove several tight bounds on the parameters of list-decodable insdel codes. In particular, we show that the alphabet size of insdel codes needs to be exponentially large in $\epsilon^{-1}$, where $\epsilon$ is the gap to capacity above. Our result even applies to settings where the unique-decoding capacity equals the list-decoding capacity and when it does so, it shows that the alphabet size needs to be exponentially large in the gap to capacity. This is sharp contrast to the Hamming error model where alphabet size polynomial in $\epsilon^{-1}$ suffices for unique decoding and also shows that the exponential dependence on the alphabet size in previous works that constructed insdel codes is actually necessary!