On the List Decodability of Insertions and Deletions
share
List decoding of insertions and deletions is studied. A Johnson-type upper bound on the maximum list size is derived. The bound is meaningful only when insertions occur. The result implies that, there are binary codes that are potentially list-decodable from a 0.707-fraction of insertions in polynomial time. For non-binary code, for any constant τ >0, there are codes over constant-sized alphabets that achieve a constant list size for a list-decoding radius that is τ times larger than the code length. Efficient encoding and decoding algorithms are also presented for codes with list-decoding radius approaching the above bound. Based on the Johnson-type bound, a Plotkin-type upper bound on the code size in the Levenshtein metric is derived.
READ FULL TEXT