{"id":"arxiv/2609.19493","url":"https://arxiv.org/abs/2609.19493","tags":["cs.IT","math.CO"],"score":0,"title":"Polynomially larger deletion codes by linear hashing of substring counts","domain":"cs.IT","source":"arxiv","authors":["Eyal En Gad"],"reviews":0,"subject":"cs.IT","summary":"We reduce the leading redundancy coefficient for binary codes correcting any fixed number $t\\ge2$ of deletions from $2t$ to $2t-1$. This is the first improvement to that coefficient since Levenshtein's 1965 bound. More generally, over every fixed alphabet of size $q\\ge2$, codes of length $n$ correcting any combination of at most $t$ insertions, deletions and substitutions exist with redundancy $(2t-1)\\log_q n+O_t(\\log_q\\log_q n)$. For two deletions, the upper-bound coefficient drops from $4$ to $3$, halving the gap to the lower-bound coefficient $2$. The leading coefficient $2t-1$ also holds…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-16","reactions":{}}