论文库

原文摘要

Correcting synchronization errors is one of the oldest problems in coding theory. In the mid-1960s, Levenshtein, and independently Ullman, showed that a single deletion can be corrected with $\log n+O(1)$ bits of redundancy, which is asymptotically optimal. For any fixed $t$, a Gilbert--Varshamov (GV) type argument shows that codes correcting $t$ deletions exist with redundancy $2t\log n+O_t(1)$. Achieving this classical GV-type bound explicitly has proved remarkably difficult. Explicit codes with redundancy $O_t(\log n)$ were first obtained by Brakensiek, Guruswami, and Zbarsky in 2016, half a century after Levenshtein, and Guruswami and Håstad matched the GV-type bound for two deletions only in 2021. For every fixed $t\ge 3$, the best explicit constructions still require roughly twice the GV-type redundancy: $(4t-1)\log n+o(\log n)$ for $t$ deletions and $4t\log n+O_t(\log\log n)$ for $t$ edits (insertions, deletions, and substitutions). We close this factor-of-two gap for every fixed $t$, even in the Damerau--Levenshtein model, which also allows adjacent transpositions. We construct explicit binary codes with deterministic polynomial-time encoding and decoding that correct any combination of at most $t$ such errors using $2t\log n+2t\log\log n+O_t(\log\log\log n)$ bits of redundancy. A single construction thus achieves the leading term of the classical GV-type bound simultaneously for deletions, edits, and Damerau--Levenshtein errors, extending the Guruswami--Håstad result from two deletions to every fixed $t$ and to substantially richer error models.