Improved Johnson-type Bounds for Insertion-Deletion Codes

Abstract

We improve upon the Johnson-type bounds of Hayashi--Yasunaga and Liu--Tjuawinata--Xing for insertion--deletion codes by encoding each local list into a binary constant-weight code. The resulting local list-size bound is tight over sufficiently large alphabets. Combining this bound with an averaging argument and the constant-weight McEliece--Rodemich--Rumsey--Welch bound yields an asymptotic rate bound that strictly improves Yasunaga's Elias-type bound throughout the nontrivial range.