Lower Bounds for all List-Decodable Deletion Codes
Abstract
A length-n binary k-deletion code is a set of binary strings such that if we delete any k bits of a string, leaving a length-(n−k) binary string, we can uniquely recover the codeword. In this paper, we consider t-list decodable deletion codes, where after k bits of a codeword are deleted, we can identify a list of size at most t such that the original codeword lies in the list. We prove a lower bound of Ωk(2n tlog1/tn/nk+k/t) on the optimal size of a t-list decodable k-deletion code, giving a √(log n) improvement over the previously best known bounds for $2$-list decodable $2$-deletion codes [GH21] and providing the first nontrivial lower bound when t>2 or k>2. Our bound holds for all t≤ nk, showing that t=Ω(log n)−list decodable deletion codes have optimal size Θk(2n t/nk), asymptotically matching the known upper bound. We also prove upper bounds on the number of common subsequences and common supersequences of a given length for any two binary strings.
Related
- Constant-List Insertion--Deletion Codes:New Bounds and an Improvement of Levenshtein's Lower Bound
- Lower Bounds for Adaptive Relaxed Locally Decodable Codes via the Capped Horvitz--Thompson Estimator
- Explicit Capacity-Achieving Quantum LDPC Codes List Decodable in Near-linear Time
- Upper Bounds for CSP Non-redundancy via Locally Decodable Codes
- Bounds and Limitations on Codes Achieving List Recovery Capacity
BibTeX
@misc{lin2026lower,
title = {{Lower Bounds for all List-Decodable Deletion Codes}},
author = {Andrew D. Lin},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.26650},
eprint = {2609.26650},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.26650},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Lower Bounds for all List-Decodable Deletion Codes
AU - Andrew D. Lin
PY - 2026
DA - 2026/09/22
PB - arXiv
DO - 10.48550/arxiv.2609.26650
UR - https://arxiv.org/abs/2609.26650
AB - A length-n binary k-deletion code is a set of binary strings such that if we delete any k bits of a string, leaving a length-(n−k) binary string, we can uniquely recover the codeword. In this paper, we consider t-list decodable deletion codes, where after k bits of a codeword are deleted, we can identify a list of size at most t such that the original codeword lies in the list. We prove a lower bound of Ω_k(2^n tlog^1/tn/n^k+k/t) on the optimal size of a t-list decodable k-deletion code, giving a √(log n) improvement over the previously best known bounds for $2$-list decodable $2$-deletion codes [GH21] and providing the first nontrivial lower bound when t>2 or k>2. Our bound holds for all t≤ n^k, showing that t=Ω(log n)−list decodable deletion codes have optimal size Θ_k(2^n t/n^k), asymptotically matching the known upper bound. We also prove upper bounds on the number of common subsequences and common supersequences of a given length for any two binary strings.
ER -