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
Post-Purchase One-Click Upsell Math for Shopify: Auditing Second Card Fees, 3PL Extra Picks & the 16oz Shipping Cliff
0dev.to Productivity
What I Learned Evaluating AI Image, Video and Audio Models
0dev.to Career
What a small-business website costs in Canada in 2026 and how to estimate yours
0dev.to Beginners
Agentic RAG over Alfresco without another vector database
0dev.to OpenSource
The model proposes, the code decides: automatic diagnosis of dbt failures with draft pull requests
0dev.to OpenSource
Why Top AI Companies Are Replacing Prompt Engineers with Forward Deployed AI Engineers (FDEs)
0dev.to Programming