Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 10 min ago
PreprintCC BY 4.0arXiv

A Generalized Half-Singleton Bound for List Decoding of Insertion/Deletion Errors

  • Neehar Verma
  • Camilla Hollanti
  • Razane Tajeddine
Open at sourcePDFDOICite

Abstract

We derive an upper bound on the rate of a linear code capable of list decoding from insertion and deletion errors. Subsequently, we show that a linear code can list decode from at most n − L/(L+1)k + 1 insdel errors with fixed list size L, and that this bound is strict when the code does not contain the all-ones vector. We also provide a simple construction of codes achieving the optimal rate for any given list size capable of correcting a single insdel error. All the results hold for linear codes over finite fields of size q ≥ 3.

Related

  1. Insdel Reed-Solomon Decoding Algorithms up to the Half-Singleton Bound
    Bencheng Fan, Margreta Kuijper, Jingge Zhu
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  2. Maximal input entropy for binary two-deletion and two-insertion channels
    Haobo Ma, Wenlin Zhang
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Constant-List Insertion--Deletion Codes:New Bounds and an Improvement of Levenshtein's Lower Bound
    Han Mao Kiah, Hengjia Wei, Ruixiao Zeng
    arXivPreprintCC BY-NC-ND 4.0Full textGeneral mathematicsarXiv
  4. Error-correction Decoding for 2D Convolutional Codes with a Generalized Viterbi Algorithm
    Zita Abreu, Elisa Junghans, Julia Lieb +1
    arXivPreprintCC BY-SA 4.0Full textDynamical systemsarXiv
  5. Vectorized Generalized Nearest Neighbor Decoding for In-block Memory Channel
    Yuhao Liu, Xinwei Li, Shuqin Pang +2
    arXivPreprintCC BY 4.0Full textGeneral mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{verma2026generalized,
  title = {{A Generalized Half-Singleton Bound for List Decoding of Insertion/Deletion Errors}},
  author = {Neehar Verma and Camilla Hollanti and Razane Tajeddine},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.23270},
  eprint = {2610.23270},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.23270},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - A Generalized Half-Singleton Bound for List Decoding of Insertion/Deletion Errors
AU  - Neehar Verma
AU  - Camilla Hollanti
AU  - Razane Tajeddine
PY  - 2026
DA  - 2026/10/16
PB  - arXiv
DO  - 10.48550/arxiv.2610.23270
UR  - https://arxiv.org/abs/2610.23270
AB  - We derive an upper bound on the rate of a linear code capable of list decoding from insertion and deletion errors. Subsequently, we show that a linear code can list decode from at most n − L/(L+1)k + 1 insdel errors with fixed list size L, and that this bound is strict when the code does not contain the all-ones vector. We also provide a simple construction of codes achieving the optimal rate for any given list size capable of correcting a single insdel error. All the results hold for linear codes over finite fields of size q ≥ 3.
ER  -