On the List Decodability of Insertions and Deletions
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 …