OpenAlex ·
Exponentially Larger Deletion-Correcting Codes and Constant-List-Decodable Insertion-Deletion Codes
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2609.21395
- Original
- Read it at the publisher
- Topics
Abstract
We establish improved asymptotic rate bounds for adversarial insertion--deletion codes. For binary unique-deletion correction in the linear-deletion regime, we strictly improve Levenshtein's classical lower-bound expression. At deletion fraction $δ=0.1$, our achievable rate increases from $0.162009$ to $0.194890$, a relative gain of approximately $20.30\%$. For list decoding with any prescribed finite list size $L$, we obtain new achievable-rate bounds for binary deletion and insertion codes. Our approach combines the Lovász local lemma with refined counting of common subsequences and supersequences, using generating functions and run-restricted sampling. We also establish a combinatorial reduction that trades $L$ units of insertion budget for one unit of deletion budget without changing the code or increasing the list size. It transfers insertion lower bounds at $γ+Lδ$ and deletion upper bounds at $δ+γ/L$ to mixed errors. We also derive a run-counting Levenshtein-type list-decoding upper bound and a higher-order Elias-type upper bound. The latter recovers Yasunaga's asymptotic unique-decoding bound at $L=1$ and strictly improves the Haeupler--Shahrasbi--Sudan insertion upper bound for every fixed $L$ and $0<γ
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
Semantics Delivery Network: Rethinking Web Retrieval Infrastructure for LLM Agents
Orientation-Aware Control and Trajectory Design for Aerial RIS-Assisted Wireless Communications
User-Level Handover Decision Making Based on Machine Learning Approaches
Replacing Large Language Models with Jev Decision Models for Low-Latency Edge Service Orchestration
Brain API: An Intent-Aware Control Plane for Policy-Governed Agentic Systems
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.