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 $\delta=0.1$, our achievable rate increases from $0.162009$ to $0.194890$,...
Han Mao Kiah, Heng-Jia Wei, Rui-Xiao Zeng· 2 citations
We study codes correcting adversarial insertions and deletions with list size $L$ fixed independently of the block length. We derive new achievable-rate bounds for binary codes and upper bounds over every fixed alphabet of size $q\ge2$, retaining explicit dependence on $L$. We establish a combinatorial reduction that t...
Han Mao Kiah, Heng-Jia Wei, Rui-Xiao Zeng· arXiv.org· 0 citations
New Delsarte-type linear programming bounds for $q$-ary $(r,\delta)$-locally recoverable codes (LRCs) are derived with three attributes: the variable set is comparable in size to that of the classical Delsarte LP, and the convex-hull LP yields improvements not captured by the previous LP and often sharpens the shorteni...