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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\tilde{O}(n)$</tex> 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\varepsilon &gt; 0$</tex>, and rate <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$r\in(0,1)$</tex>, there exist explicit families of these codes that have rate <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$r$</tex> and can be list decoded from a <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(1-r-\varepsilon)$</tex> 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\tilde{O}(n)$</tex>, where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex> 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\tilde{O}(n)$</tex> time list-decoding algorithm for Reed-Solomon codes approaching the Johnson radius. As part of the second component, we design <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\tilde{O}(n)$</tex> time algorithms for two natural algebraic problems: given a <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(m+2)$</tex> -variate polynomial <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$Q(x, y_{0}, \ldots, y_{m})=\tilde{Q}(x)+\sum\nolimits_{i=0}^{m} Q_{i}(x) \cdot y_{i}$</tex> the first algorithm solves order-m linear differential equations of the form <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$Q\left(x, f(x), \frac{d f}{d x}, \ldots, \frac{d^{m} f}{d x^{m}}\right) \equiv 0$</tex> while the second solves functional equations of the form <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$Q(x, f(x), f(\gamma x), \ldots, f(\gamma^{m}x))\equiv 0$</tex>, where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$m$</tex> is an arbitrary constant and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\gamma$</tex> is a field element of sufficiently high order. These algorithms can be viewed as generalizations of classical <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\tilde{O}(n)$</tex> 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.