Title: List Decoding of Insertions and Deletions,
Abstract: List decoding of insertions and deletions in the Levenshtein metric is
considered. The Levenshtein distance between two sequences is the minimum
number of insertions and deletions needed to turn one of the sequences into the
other. In this paper, a Johnson-like upper bound on the maximum list size when
list decoding in the Levenshtein metric is derived. This bound depends only on
the length and minimum Levenshtein distance of the code, the length of the
received word, and the alphabet size. It shows that polynomial-time list
decoding beyond half the Levenshtein distance is possible for many parameters.
Further, we also prove a lower bound on list decoding of deletions with with
the well-known binary Varshamov-Tenengolts (VT) codes which shows that the
maximum list size grows exponentially with the number of deletions. Finally, an
efficient list decoding algorithm for two insertions/deletions with VT codes is
given. This decoder can be modified to a polynomial-time list decoder of any
constant number of insertions/deletions.