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 0">0, Guruswami and Rudra presented an nO(1) time algorithm to list decode appropriate folded RS codes of rate R from a fraction 1?R? of errors. The algorithm is based on multivariate polynomialinterpolation and root-finding over extension fields. It was noted by Vadhan that interpolating a linear polynomial suffices for a statement of the above form. Here we give a simple linear-algebra based analysis of this variant that eliminates the need for the computationally expensive root-finding step over extension fields (and indeed any mention of extension fields). The entire list decoding algorithm is linear-algebraic, solving one linear system for the interpolation step, and another linear system to find a small subspace of candidate solutions. Except for the step of pruning this subspace, the algorithm can be implemented to run in quadratic time. We also consider a closely related family of codes, called (order m) derivative codes and defined over fields of large characteristic, which consist of the evaluations of f as well as its first m?1 formal derivatives at N distinct field elements. We show how our linear-algebraic methods for folded Reed-Solomon codes can be used to show that derivative codes can also achieve the above optimal trade-off.The theoretical drawback of our analysis for folded RS codes and derivative codes is that both the decoding complexity and proven worst-case list-size bound are n(1) . By combining the above idea with a pseudorandom subset of all polynomials as messages, we get a Monte Carlo construction achieving a list size bound of O(12) , which is quite close to the existential O(1) bound (however, the decoding complexity remains n(1) ). Our work highlights that constructing an explicit ``subspace-evasive" subset that has small intersection with low-dimensional subspaces --- an interesting problem in pseudorandomness in its own right --- has applications to constructing explicit codes with better list-decoding guarantees.
展开▼
