Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Amirbehshad Shahrasbi:

TR19-153 | 6th November 2019
Venkatesan Guruswami, Bernhard Haeupler, Amirbehshad Shahrasbi

Optimally Resilient Codes for List-Decoding from Insertions and Deletions

Revisions: 1

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 ... more >>>

ISSN 1433-8092 | Imprint