{"id":"arxiv/2610.23270","url":"https://arxiv.org/abs/2610.23270","tags":["cs.IT","math.CO"],"score":0,"title":"A Generalized Half-Singleton Bound for List Decoding of Insertion/Deletion Errors","domain":"cs.IT","source":"arxiv","authors":["Neehar Verma","Camilla Hollanti","Razane Tajeddine"],"reviews":0,"subject":"cs.IT","summary":"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 - \\frac{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 \\geq 3$.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-16","reactions":{}}