Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with List error-correction:
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 >>>

TR12-036 | 12th April 2012
Venkatesan Guruswami, Chaoping Xing

Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding

We give a new construction of algebraic codes which are efficiently list decodable from a fraction $1-R-\epsilon$ of adversarial errors where $R$ is the rate of the code, for any desired positive constant $\epsilon$. The worst-case list size output by the algorithm is $O(1/\epsilon)$, matching the existential bound for random ... more >>>

TR12-073 | 11th June 2012
Venkatesan Guruswami, Carol Wang

Linear-algebraic list decoding for variants of Reed-Solomon codes

Folded Reed-Solomon codes are an explicit family of codes that achieve the optimal trade-off between rate and list error-correction capability. Specifically, for any $\epsilon > 0$, Guruswami and Rudra presented an $n^{O(1/\epsilon)}$ time algorithm to list decode appropriate folded RS codes of rate $R$ from a fraction $1-R-\epsilon$ of ... more >>>

TR13-060 | 10th April 2013
Venkatesan Guruswami, Swastik Kopparty

Explicit Subspace Designs

A subspace design is a collection $\{H_1,H_2,\dots,H_M\}$ of subspaces of ${\mathbf F}_q^m$ with the property that no low-dimensional subspace $W$ of ${\mathbf F}_q^m$ intersects too many subspaces of the collection. Subspace designs were introduced by Guruswami and Xing (STOC 2013) who used them to give a randomized construction of optimal ... 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