  We study codes that are list-decodable under insertions and deletions.
Specifically, we consider the setting where a codeword over some finite
alphabet of size $q$ may suffer from $\delta$ fraction of adversarial deletions
and $\gamma$ fraction of adversarial insertions. A code is said to be
$L$-list-decodable if there is an (efficient) algorithm that, given a received
word, reports a list of $L$ codewords that include the original codeword.
  Using the concept of synchronization strings, introduced by the first two
authors [STOC 2017], we show some surprising results. We show that for every
$0\leq\delta<1$, every $0\leq\gamma<\infty$ and every $\epsilon>0$ there exist
efficient codes of rate $1-\delta-\epsilon$ and constant alphabet (so
$q=O_{\delta,\gamma,\epsilon}(1)$) and sub-logarithmic list sizes. We stress
that the fraction of insertions can be arbitrarily large and the rate is
independent of this parameter. Our result sheds light on the remarkable
asymmetry between the impact of insertions and deletions from the point of view
of error-correction: Whereas deletions cost in the rate of the code, insertion
costs are borne by the adversary and not the code!
  We also prove several tight bounds on the parameters of list-decodable insdel
codes. In particular, we show that the alphabet size of insdel codes needs to
be exponentially large in $\epsilon^{-1}$, where $\epsilon$ is the gap to
capacity above. Our result even applies to settings where the unique-decoding
capacity equals the list-decoding capacity and when it does so, it shows that
the alphabet size needs to be exponentially large in the gap to capacity. This
is sharp contrast to the Hamming error model where alphabet size polynomial in
$\epsilon^{-1}$ suffices for unique decoding and also shows that the
exponential dependence on the alphabet size in previous works that constructed
insdel codes is actually necessary!
