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
A log file is input too
0dev.to
I built a tiny GPT from scratch to show my kids how chatbots really work
0dev.to Machine Learning
What 'Premium Grade' on a Supplement Label Legally Means
0dev.to Tutorial
How to Separate Accounts in Multi-Store E-commerce Operations
0dev.to Tutorial
WARN Act and Government Contractors: What Happens When a Federal Contract Ends
0dev.to Career
标题全角 变了空格、占位符丢了尖括号:dev.to 发文前核对的 4 处
0dev.to OpenSource