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 errors. The algorithm is based on multivariate polynomial
interpolation 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^{\Omega(1/\epsilon)}$. 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(1/\epsilon^2)$, which is quite close to the existential $O(1/\epsilon)$ bound (however, the decoding complexity remains $n^{\Omega(1/\epsilon)}$).
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.
