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

Rohan Goyal, Prahladh Harsha, Mrinal Kumar +1

We show that the known list-decoding algorithms for univariate multiplicity and folded Reed-Solomon codes can be made to run in $\tilde{O}(n)$ time. Univariate multiplicity codes a…