Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with zero-rate regime:
TR12-017 | 1st March 2012
Venkatesan Guruswami, Srivatsan Narayanan

Combinatorial limitations of a strong form of list decoding

Revisions: 1

We prove the following results concerning the combinatorics of list decoding, motivated by the exponential gap between the known upper bound (of $O(1/\gamma)$) and lower bound (of $\Omega_p(\log (1/\gamma))$) for the list-size needed to decode up to radius $p$ with rate $\gamma$ away from capacity, i.e., $1-h(p)-\gamma$ (here $p\in (0,1/2)$ ... more >>>

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

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?''

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