On the List Decodability of Insertions and Deletions

Abstract

In this work, we study the problem of list decoding of insertions and deletions. We present a Johnson-type upper bound on the maximum list size. The bound is meaningful only when insertions occur. Our bound implies that there are binary codes of rate $\Omega (1)$ that are list-decodable from a $0.707$-fraction of insertions. For any ${\tau }_{\mathsf{I}}\ge 0$ and ${\tau }_{\mathsf{D}}\in [0,1)$, there exist $q$-ary codes of rate $\Omega (1)$ that are list-decodable from a ${\tau }_{\mathsf{I}}$-fraction of insertions and ${\tau }_{\mathsf{D}}$-fraction of deletions, where $q$ depends only on ${\tau }_{\mathsf{I}}$ and ${\tau }_{\mathsf{D}}$. We also provide efficient encoding and decoding algorithms for list-decoding from ${\tau }_{\mathsf{I}}$-fraction of insertions and ${\tau }_{\mathsf{D}}$-fraction of deletions for any ${\tau }_{\mathsf{I}}\ge 0$ and ${\tau }_{\mathsf{D}}\in [0,1)$. Based on the Johnson-type bound, we derive a Plotkin-type upper bound on the code size in the Levenshtein metric.