Efficiently list-decodable insertion and deletion codes via concatenation

In this paper, we consider the list decoding property of codes under insertion and deletion errors (insdel for short). Firstly, we analyse the list decodability of random insdel codes. Our result provides a more complete picture on the list decodability of insdel codes when both insertion and deletion errors happen. Secondly, we construct a family of insdel codes along with their efficient encoding and decoding algorithms through concatenation method which provides a Zyablov-type bound for insdel metric codes.Info-communications Media Development Authority (IMDA)National Research Foundation (NRF)Submitted/Accepted versionThe work of Shu Liu was supported in part by the National Natural Science Foundation of China under Grant 11901077, Grant 2019YFB1803102, and Grant 2020YFB1806805; in part by the National Key Research and Development Program of China under Contract IFN2020203; and in part by the Fundamental Research Funds for the Central Universities of China under Grant ZYGX2018KYQD216. The work of Ivan Tjuawinata was supported by the National Research Foundation, Singapore, under its Strategic Capability Research Centres Funding Initiative. The work of Chaoping Xing was supported in part by the National Natural Science Foundation of China under Grant 12031011 and in part by the National Key Research and Development Project under Grant 2020YFA0712300