Binary Codes Correcting Multiple Edits via Polynomial Hashing and Entropy Recycling
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 2tlog n+Ot(1). Achieving this classical GV-type bound explicitly has proved remarkably difficult. Explicit codes with redundancy Ot(log n) were first obtained by Brakensiek, Guruswami, and Zbarsky in 2016, half a century after Levenshtein, and Guruswami and Håstad matched the GV-type bound for two deletions only in 2021. For every fixed t≥ 3, the best explicit constructions still require roughly twice the GV-type redundancy: (4t−1)log n+o(log n) for t deletions and 4tlog n+Ot(loglog 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 2tlog n+2tloglog n+Ot(logloglog 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åstad result from two deletions to every fixed t and to substantially richer error models.
Related
- Binary Multiple-Node-Erasure-Correcting Codes over Complete Graphs: Constructions, q-Ary Metric Balls, and Duality
- Convergence of a Family of Accelerated Schröder-like Methods for the Simultaneous Extraction of Simple and Multiple Polynomial Zeros
- Frobenius Profiles of Polynomial-Multiple MRD Codes
- Multiple representations in difference sets under polynomial density constraints
- Voltage-Increment-Based Low-Rank Representation with Polynomial Chaos Expansions for Probabilistic Voltage Assessment Under Multiple Contingencies
BibTeX
@misc{bui2026binary,
title = {{Binary Codes Correcting Multiple Edits via Polynomial Hashing and Entropy Recycling}},
author = {Quan D. Bui and Shuche Wang and Van Khu Vu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.15631},
eprint = {2610.15631},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.15631},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Binary Codes Correcting Multiple Edits via Polynomial Hashing and Entropy Recycling
AU - Quan D. Bui
AU - Shuche Wang
AU - Van Khu Vu
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2610.15631
UR - https://arxiv.org/abs/2610.15631
AB - 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 2tlog 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åstad matched the GV-type bound for two deletions only in 2021. For every fixed t≥ 3, the best explicit constructions still require roughly twice the GV-type redundancy: (4t−1)log n+o(log n) for t deletions and 4tlog n+O_t(loglog 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 2tlog n+2tloglog n+O_t(logloglog 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åstad result from two deletions to every fixed t and to substantially richer error models.
ER -