タイトル：Coordinate-ordering-free Upper Bounds for Linear Insertion- Deletion Codes 著者名：Hao Chen 雑誌名：IEEE Transactions on Information Theory 号数：- DOI:10.1109/TIT.2022.3167662 Abstract：In this paper we prove several coordinate-ordering-free upper bounds on the insdel distances of linear codes. Our bounds are stronger than some previous known bounds. We apply these upper bounds to AGFC codes from some cyclic codes and one algebraic-geometric code with any rearrangement of coordinate positions. A strong upper bound on the insdel distances of Reed-Muller codes with the special coordinate ordering is also given.
タイトル：Explicit and Efficient Constructions of Linear Codes Against Adversarial Insertions and Deletions 著者名：Roni Con; Amir Shpilka; Itzhak Tamo 雑誌名：IEEE Transactions on Information Theory 号数：- DOI:10.1109/TIT.2022.3173185 Abstract：In this work, we study linear error-correcting codes against adversarial insertion-deletion (insdel) errors, a topic that has recently gained a lot of attention. We construct linear codes over Fq, for q = poly(1/ε), that can efficiently decode from a δ fraction of insdel errors and have rate (1 - 4δ)=8-ε. We also show that by allowing codes over Fq2 that are linear over Fq, we can improve the rate to (1 - δ)/4 - ε while not sacrificing efficiency. Using this latter result, we construct fully linear codes over F2 that can efficiently correct up to δ < 1/54 fraction of deletions and have rate R = (1 - 54 · δ)/1216. Cheng, Guruswami, Haeupler, and Li [4] constructed codes with (extremely small) rates bounded away from zero that can correct up to a δ < 1/400 fraction of insdel errors. They also posed the problem of constructing linear codes that get close to the half-Singleton bound (proved in [4]) over small fields. Thus, our results significantly improve their construction and get much closer to the bound.
