Decoding Insertions/Deletions via List Recovery
Anisha Banerjee 1 , Roni Con 2 , Antonia Wachter-Zeh 1 , and Eitan Yaakobi 2 · 2025
Read Decoding Insertions/Deletions via List Recovery by Anisha Banerjee 1 , Roni Con 2 , Antonia Wachter-Zeh 1 , and Eitan Yaakobi 2 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-02452.txt.
Description
Anisha Banerjee, Roni Con, Antonia Wachter-Zeh, and Eitan Yaakobi decode messages damaged by insertions and deletions through a new reduction, in a 2025 paper. Such errors scramble stored data, notably in DNA storage. Most known decoders rely on synchronization strings. Those convert the problem into simpler error types. This work instead reduces decoding to list recovery. In list recovery, the decoder outputs a short candidate list.
The authors prove the bridge formally. Any suitably list-recoverable code becomes a list-decodable code for insertions and deletions. They apply the idea to Reed-Solomon codes. Those have fast list recovery up to a known bound. The result gives the first efficient decoder of this kind for most such codes. Random error channels get a better rate trade-off. A classic soft-decision algorithm is adapted to the channel too. The paper is theoretical computer science with storage uses.
Catalog record
| CREATOR | Anisha Banerjee 1 , Roni Con 2 , Antonia Wachter-Zeh 1 , and Eitan Yaakobi 2 |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 36 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-02452