We give a complete answer to the following basic question: ``What is the maximal fraction of deletions or insertions tolerable by $q$-ary list-decodable codes with non-vanishing information rate?''

This question has been open even for binary codes, including the restriction to the binary insertion-only setting, where the best known results was that a $\gamma \leq 0.707$ fraction of insertions is tolerable by some binary code family.

For any desired $\epsilon > 0$, we construct a family of binary codes of positive rate which can be efficiently list-decoded from any combination of $\gamma$ fraction of insertions and $\delta$ fraction of deletions as long as $ \gamma + 2\delta \leq 1 -\epsilon$. On the other hand, for any $\gamma, \delta$ with $\gamma + 2\delta = 1$ list-decoding is impossible. Our result thus precisely characterizes the feasibility region of binary list-decodable codes for insertions and deletions.

We further generalize our result to codes over any finite alphabet of size $q$. Surprisingly, our work reveals that the feasibility region for $q>2$ is *not* the natural generalization of the binary bound above. We provide tight upper and lower bounds that precisely pin down the feasibility region, which turns out to have a $(q-1)$-piece-wise linear boundary whose $q$ corner-points lie on a quadratic curve.

The main technical work in our results is proving the existence of code families of sufficiently large *size* with good list-decoding properties for any combination of $\delta,\gamma$ within the claimed feasibility region. We achieve this via an intricate analysis of codes introduced by [Bukh, Ma; SIAM J. Discrete Math; 2014]. Finally we give a simple yet powerful concatenation scheme for list-decodable insertion-deletion codes which transforms any such (non-efficient) code family (with vanishing information rate) into an efficiently decodable code family with constant rate.

The proof of the upper bound on the feasibility region of list-decodability for q-ary alphabets (Theorem 5.2 in revision) is different. The earlier argument was based on a more general convexity claim about the infeasibility region whose proof had a gap.

We give a complete answer to the following basic question: ``What is the maximal fraction of deletions or insertions tolerable by $q$-ary list-decodable codes with non-vanishing information rate?''

This question has been open even for binary codes, including the restriction to the binary insertion-only setting, where the best known results was that a $\gamma \leq 0.707$ fraction of insertions is tolerable by some binary code family.

For any desired $\epsilon > 0$, we construct a family of binary codes of positive rate which can be efficiently list-decoded from any combination of $\gamma$ fraction of insertions and $\delta$ fraction of deletions as long as $ \gamma + 2\delta \leq 1 -\epsilon$. On the other hand, for any $\gamma, \delta$ with $\gamma + 2\delta = 1$ list-decoding is impossible. Our result thus precisely characterizes the feasibility region of binary list-decodable codes for insertions and deletions.

We further generalize our result to codes over any finite alphabet of size $q$. Surprisingly, our work reveals that the feasibility region for $q>2$ is *not* the natural generalization of the binary bound above. We provide tight upper and lower bounds that precisely pin down the feasibility region, which turns out to have a $(q-1)$-piece-wise linear boundary whose $q$ corner-points lie on a quadratic curve.

The main technical work in our results is proving the existence of code families of sufficiently large *size* with good list-decoding properties for any combination of $\delta,\gamma$ within the claimed feasibility region. We achieve this via an intricate analysis of codes introduced by [Bukh, Ma; SIAM J. Discrete Math; 2014]. Finally we give a simple yet powerful concatenation scheme for list-decodable insertion-deletion codes which transforms any such (non-efficient) code family (with vanishing information rate) into an efficiently decodable code family with constant rate.