Polynomially larger deletion codes by linear hashing of substring counts
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.19493
curl -X POST /api/v1/records/arxiv/2609.19493/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.19493/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'