Limits to List Decoding of Insertions and Deletions

List decoding of insertions and deletions in the Levenshtein metric is considered. In this paper, a Johnson-like upper bound on the maximum list size when 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. For example, list decoding of two insertions/deletions with the well-known Varshamov-Tenengolts (VT) codes is feasible. Further, we also show a lower bound on list decoding VT codes and an efficient list decoding algorithm for two insertions/deletions with VT codes.