标题： 通过列表恢复解码插入/删除 显示英文标题

标题： Decoding Insertions/Deletions via List Recovery

摘要： 在这项工作中，我们考虑了高效解码插入和删除错误编码的问题。大多数已知的高效编码是具有同步字符串的编码，这些字符串可以将解码插入和删除问题简化为解码替换和擦除问题。本文提出的新方法将解码插入和删除问题简化为列表恢复问题。具体来说，任何\((\rho, 2\rho n + 1, L)\)- 列表可恢复的编码都是\((\rho, L)\)- 列表可解码的插入删除编码。作为示例，我们将此技术应用于里德-所罗门（RS）码，已知这些码在约翰逊界内有高效的列表恢复算法。在对抗性插入删除模型中，假设\(t\cdot k = O(n)\)，这提供了从\(t\)插入删除错误中的有效（列表）解码。这是第一个针对\([n, k]\)的\(k>2\)里德-所罗门码的有效插入删除解码器。 此外，我们探索了随机插入删除模型，例如Davey-MacKay信道，并且表明对于某些\(\rho\)的选择，长度为\(n\)的\((\rho, n^{1/2+0.001}, L)\)-列表可恢复码可以以高概率高效地列表解码信道输出，从而确保传输的编码字在输出列表中。 在RS码的背景下，这相对于对抗性情况而言，这些信道具有更好的速率-错误权衡。 我们还改编了Koetter-Vardy算法，这是一种著名的RS码软决策列表解码技术，用于纠正由Davey-MacKay信道引起的插入和删除。 显示英文摘要

摘要： In this work, we consider the problem of efficient decoding of codes from insertions and deletions. Most of the known efficient codes are codes with synchronization strings which allow one to reduce the problem of decoding insertions and deletions to that of decoding substitution and erasures. Our new approach, presented in this paper, reduces the problem of decoding insertions and deletions to that of list recovery. Specifically, any \((\rho, 2\rho n + 1, L)\)-list-recoverable code is a \((\rho, L)\)-list decodable insdel code. As an example, we apply this technique to Reed-Solomon (RS) codes, which are known to have efficient list-recovery algorithms up to the Johnson bound. In the adversarial insdel model, this provides efficient (list) decoding from \(t\) insdel errors, assuming that \(t\cdot k = O(n)\). This is the first efficient insdel decoder for \([n, k]\) RS codes for \(k>2\). Additionally, we explore random insdel models, such as the Davey-MacKay channel, and show that for certain choices of \(\rho\), a \((\rho, n^{1/2+0.001}, L)\)-list-recoverable code of length \(n\) can, with high probability, efficiently list decode the channel output, ensuring that the transmitted codeword is in the output list. In the context of RS codes, this leads to a better rate-error tradeoff for these channels compared to the adversarial case. We also adapt the Koetter-Vardy algorithm, a famous soft-decision list decoding technique for RS codes, to correct insertions and deletions induced by the Davey-MacKay channel.