Optimally Resilient Codes for List-Decoding From Insertions and Deletions
Optimally Resilient Codes for List-Decoding From Insertions and Deletions
We give a complete answer to the following basic question: “What is the maximal fraction of deletions or insertions tolerable by <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$q$ </tex-math></inline-formula> -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 …