On the Average List Size of VT Codes under Two Insertions or Two Deletions
Abstract
Levenshtein's classical theorem shows that any code that can uniquely decode from t deletions can also uniquely decode from t insertions. This symmetry, however, does not generally hold in the list-decoding regime. Several prior results on the capacity and radii of list-decoding from insertions and deletions suggest that insertions are easier to handle than deletions. In an effort to better understand this asymmetry between insertions and deletions under list-decoding, we study an analogous version of McEliece's \emph{average list size problem}. More precisely, given a binary code 𝒞 of length n that uniquely corrects t' insertions (or deletions), we are interested in the average number of codewords returned by a t-insertion (or deletion) list decoder, where t' < t. Focusing on the case of t'=1 and t=2, we find that under two insertions, this quantity is at most (n+12)/4 for any VT code of length n, whereas under two deletions it is at least n/2 − 10 when averaged over all length-n VT codes. The nearly factor-of-two gap between these upper and lower bounds serves to confirm the relative ease of list-decoding of insertions compared to deletions from an average-case perspective.
Related
- List Size of Random Linear Codes: Optimality and the Limits of Average-Radius List Decoding
- Random Algebraic Geometry Codes Approach the Half-Singleton Bound for Insertions and Deletions
- Average-Radius List-Decodability of Random Linear Codes
- The list size of random linear and LDPC codes at capacity
- Easy detection of CRISPR/Cas9-Induced Insertions, Deletions, and Substitutions in Rice Genes OsMADS26, OsRAC1 and OsNRT1.1b using SYBR Green qPCR and Robust HRM analysis in R software
BibTeX
@misc{banerjee2026average,
title = {{On the Average List Size of VT Codes under Two Insertions or Two Deletions}},
author = {Anisha Banerjee and Roni Con and Antonia Wachter-Zeh and Eitan Yaakobi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.15767},
eprint = {2610.15767},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.15767},
}
RIS
TY - UNPB
TI - On the Average List Size of VT Codes under Two Insertions or Two Deletions
AU - Anisha Banerjee
AU - Roni Con
AU - Antonia Wachter-Zeh
AU - Eitan Yaakobi
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2610.15767
UR - https://arxiv.org/abs/2610.15767
AB - Levenshtein's classical theorem shows that any code that can uniquely decode from t deletions can also uniquely decode from t insertions. This symmetry, however, does not generally hold in the list-decoding regime. Several prior results on the capacity and radii of list-decoding from insertions and deletions suggest that insertions are easier to handle than deletions. In an effort to better understand this asymmetry between insertions and deletions under list-decoding, we study an analogous version of McEliece's \emph{average list size problem}. More precisely, given a binary code 𝒞 of length n that uniquely corrects t' insertions (or deletions), we are interested in the average number of codewords returned by a t-insertion (or deletion) list decoder, where t' < t. Focusing on the case of t'=1 and t=2, we find that under two insertions, this quantity is at most (n+12)/4 for any VT code of length n, whereas under two deletions it is at least n/2 − 10 when averaged over all length-n VT codes. The nearly factor-of-two gap between these upper and lower bounds serves to confirm the relative ease of list-decoding of insertions compared to deletions from an average-case perspective.
ER -