Skip to content
Preprint

Making Every Edit Count: Efficient Binary Edit Correction at the Gilbert-Varshamov Bound

Nov 2026 · 0 citations · 31 references
Computer Science Mathematics

Abstract

We construct binary codes that attain the classical Gilbert-Varshamov redundancy guarantee for a fixed number of edit errors, with deterministic polynomial-time construction, encoding, and decoding. For every fixed integer $t\ge 1$ and all sufficiently large block lengths $n$, our codes correct any combination of at most $t$ insertions, deletions, and substitutions in total, with redundancy at most $2t\log_2 n+O_t(1)$. All algorithms run in polynomial time in $n$ for fixed $t$, and decoding recovers the original information message. This realizes the classical counting guarantee algorithmically without enumerating the exponentially large space of binary words.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.