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
How to Keep Multiple Browser Profiles Isolated: A Practical Guide to Fingerprints, Cookies and Proxies
0dev.to
AEO vs SEO: the difference nobody's SEO checklist covers yet
0dev.to
What actually gets a business recommended by ChatGPT (it's not a switch you flip)
0dev.to
The Biggest Pro-AI Super PAC Network Didn’t Really Impact the Midterms
0Wired
‘We Have No Shared Reality’: Two Political Influencers on the Future of Politics Online
0Wired
OpenAI is already trying to shape the 2028 election
0TechCrunch