Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR12-146 | 7th November 2012 13:57

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 dimension.
By pre-coding the message polynomials into a subspace-evasive set, we get a Monte Carlo construction of a subcode of Reed-Solomon codes that can be list decoded from a fraction $(1-R-\epsilon)$ of errors in polynomial time (for any fixed $\epsilon > 0$) with a list size of $O(1/\epsilon)$. Our methods extend to algebraic-geometric (AG) codes, leading to a similar claim over constant-sized alphabets. This matches parameters of recent results based on folded variants of RS and AG codes, but our construction here gives subcodes of Reed-Solomon and AG codes themselves (albeit with restrictions on the evaluation points).

Further, the underlying algebraic idea also extends nicely to Gabidulin's construction of rank-metric codes based on linearized polynomials. This gives the first construction of positive rate rank-metric codes list decodable beyond half the distance, and in fact gives codes of rate $R$ list decodable up to the optimal $(1-R-\epsilon)$ fraction of rank errors. A similar claim holds for the closely related subspace codes studied by Koetter and Kschischang.

We introduce a new notion called "subspace designs" as another way to pre-code messages and prune the subspace of candidate solutions. Using these, we also get a *deterministic* construction of a polynomial time list decodable subcode of RS codes. By using a cascade of several subspace designs, we extend our approach to AG codes, which gives the first deterministic construction of an algebraic code family of rate $R$ with efficient list decoding from $1-R-\epsilon$ fraction of errors over an alphabet of constant size (that depends only on $\epsilon$). The list size bound is almost a constant (governed by $\log^*$ (block length)), and the code can be constructed in quasi-polynomial time. Finding more efficient constructions of subspace designs is an interesting problem in pseudorandomness arising out of our work.

ISSN 1433-8092 | Imprint