PreprintarXiv licencearXiv
Making Every Edit Count: Efficient Binary Edit Correction at the Gilbert-Varshamov Bound
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≥ 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 2tlog2 n+Ot(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.
Related
- Random Quantum LDPC Codes Approaching the Gilbert-Varshamov Bound
- Careful Judge: Safe and Efficient Human-AI Collaborative Decision Making
- Win-Ratio Regression for Prioritized Composite Outcomes in Observational Studies: Doubly Robust and Efficient Estimation with Future-Score Correction
- Risk-matched case-control sampling and semiparametric weight calibration for efficient biomarker assessment with binary outcomes
- Asymptotic stability of a Bloch skyrmion for the Landau-Lifshitz-Gilbert equation
BibTeX
@misc{gabrys2026making,
title = {{Making Every Edit Count: Efficient Binary Edit Correction at the Gilbert-Varshamov Bound}},
author = {Ryan Gabrys and Shubhransh Singhvi and Eitan Yaakobi},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.04023},
eprint = {2611.04023},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.04023},
}
RIS
TY - UNPB
TI - Making Every Edit Count: Efficient Binary Edit Correction at the Gilbert-Varshamov Bound
AU - Ryan Gabrys
AU - Shubhransh Singhvi
AU - Eitan Yaakobi
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.04023
UR - https://arxiv.org/abs/2611.04023
AB - 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≥ 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 2tlog_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.
ER -