On the List Decodability of Insertions and Deletions
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 $Ω(1)$ that are list-decodable from a $0.707$-fraction of insertions. For any $τ_\mathsf{I} \geq 0$ and $τ_\mathsf{D} \in [0,1)$, there exist $q$-ary codes of rate $Ω(1)$ that are list-decodable from a $τ_\mathsf{I}$-fraction of insertions and $τ_\mathsf{D}$-fraction of deletions, where $q$ depends only on $τ_\mathsf{I}$ and $τ_\mathsf{D}$. We also provide efficient encoding and decoding algorithms for list-decoding from $τ_\mathsf{I}$-fraction of insertions and $τ_\mathsf{D}$-fraction of deletions for any $τ_\mathsf{I} \geq 0$ and $τ_\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.