  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 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 $\epsilon>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-\epsilon)$ 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,\dots,y_m) = \tilde{Q}(x) + \sum_{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{df}{dx}, \dots,\frac{d^m f}{dx^m}\right) \equiv 0$ while
the second solves functional equations of the form $Q\left(x, f(x), f(\gamma
x), \dots,f(\gamma^m x)\right) \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.
