Fast List Decoding of Univariate Multiplicity and Folded Reed-Solomon Codes

We show that the known list-decoding algorithms for univariate multiplicity and folded Reed-Solomon (FRS) codes can be made to run in$\tilde{O}(n)$time. Univariate multiplicity codes and FRS codes are natural variants of Reed-Solomon codes that were discovered and studied for their applications to list decoding. It is known that for every$\varepsilon > 0$, and rate$r\in(0,1)$, there exist explicit families of these codes that have rate$r$and can be list decoded from a$(1-r-\varepsilon)$fraction of errors with constant list size in polynomial time (Guruswami & Wang (IEEE Trans. Inform. Theory 2013) and Kopparty, Ron-Zewi, Saraf & Wootters (SIAM J. Comput. 2023)). In this work, we present randomized algorithms that perform the above list-decoding tasks in$\tilde{O}(n)$, where$n$is the block-length of the code. Our algorithms have two main components. The first component builds upon the lattice-based approach of Alekhnovich (IEEE Trans. Inf. Theory 2005), who designed a$\tilde{O}(n)$time list-decoding algorithm for Reed-Solomon codes approaching the Johnson radius. As part of the second component, we design$\tilde{O}(n)$time algorithms for two natural algebraic problems: given a$(m+2)$-variate polynomial$Q(x, y_{0}, \ldots, y_{m})=\tilde{Q}(x)+\sum\nolimits_{i=0}^{m} Q_{i}(x) \cdot y_{i}$the first algorithm solves order-m linear differential equations of the form$Q\left(x, f(x), \frac{d f}{d x}, \ldots, \frac{d^{m} f}{d x^{m}}\right) \equiv 0$while the second solves functional equations of the form$Q(x, f(x), f(\gamma x), \ldots, f(\gamma^{m}x))\equiv 0$, where$m$is an arbitrary constant and$\gamma$is a field element of sufficiently high order. These algorithms can be viewed as generalizations of classical$\tilde{O}(n)$time algorithms of Sieveking (Computing 1972) and Kung (Numer. Math. 1974) for computing the modular inverse of a power series, and might be of independent interest.