AI & ML
Seed Recycling: Explicit Codes for Mixed Synchronization Errors Matching the Leading Term of the Gilbert--Varshamov Bound
arXiv math.IT0 views
arXiv:2610.15631v2 Announce Type: replace Abstract: 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\aa 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\aa stad result from two deletions to every fixed $t$ and to substantially richer error models.
Source:https://arxiv.org/abs/2610.15631PreviousConfusion-Erasure Bounds of Error-Bounded Decoders under QAMNextOptimality of the $D_4$ lattice quantizer
Related posts
Moonshot AI's Kimi K3.1 Pro Weights Are Now Open — Explained Honestly
0dev.to AI

Everyone has better models. Why do some teams fly while others don't?
0dev.to AI

"Trace Shape Reveals Model Capability: 3B vs 7B"
0dev.to AI
I've spent a lot of time thinking about how to use technology more effectively
0dev.to WebDev
HackerTube AI: A Human-Curated Video Archive for Curious Learners
0dev.to WebDev
CPCSC for build-to-print shops: does it apply?
0dev.to Security