{"id":"arxiv/2609.26650","url":"https://arxiv.org/abs/2609.26650","tags":["cs.IT","cs.DM","math.CO"],"score":0,"title":"Lower Bounds for all List-Decodable Deletion Codes","domain":"cs.IT","source":"arxiv","authors":["Andrew D. Lin"],"reviews":0,"subject":"cs.IT","summary":"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 t\\log^{1/t}n/n^{k+k/t})$ on the optimal size of a $t$-list decodable $k$-deletion code, giving a $\\sqrt{\\log n}$ improvement over the previously best known bounds for…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-22","reactions":{}}