Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with list-decodable codes:
TR11-087 | 3rd June 2011
Michael Viderman

A Combination of Testability and Decodability by Tensor Products

Revisions: 3

Ben-Sasson and Sudan (RSA 2006) showed that repeated tensor products of linear codes with a very large distance are locally testable. Due to the requirement of a very large distance the associated tensor products could be applied only over sufficiently large fields. Then Meir (SICOMP 2009) used this result (as ... more >>>

TR23-185 | 27th November 2023
Rohan Goyal, Prahladh Harsha, Mrinal Kumar, A. Shankar

Fast list-decoding of univariate multiplicity and folded Reed-Solomon codes

Revisions: 3

We show that the known list-decoding algorithms for univariate multiplicity and folded Reed-Solomon (FRS) codes can be made to run in nearly-linear time. This yields, to the best of our knowledge, the first known family of codes that can be decoded (and encoded) in nearly linear time, even as they ... more >>>

ISSN 1433-8092 | Imprint