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 q -ary list-decodable codes with non-vanishing information rate?”

Authors

• Venkatesan Guruswami
• Bernhard Haeupler
• Amirbehshad Shahrasbi

Keywords

• Coding for Insertions and Deletions
• List Decoding
• Error Resilience