Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Rank metric:
TR12-146 | 7th November 2012
Venkatesan Guruswami, Chaoping Xing

List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes up to the Singleton bound

We consider Reed-Solomon (RS) codes whose evaluation points belong to a subfield, and give a linear-algebraic list decoding algorithm that can correct a fraction of errors approaching the code distance, while pinning down the candidate messages to a well-structured affine space of dimension a constant factor smaller than the code ... more >>>

ISSN 1433-8092 | Imprint