Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR23-185 | 6th March 2024 10:44

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

RSS-Feed




Revision #3
Authors: Rohan Goyal, Prahladh Harsha, Mrinal Kumar, A. Shankar
Accepted on: 6th March 2024 10:44
Downloads: 182
Keywords: 


Abstract:

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 $\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 (\emph{IEEE Trans.\ Inform.\ Theory} 2013) and Kopparty, Ron-Zewi, Saraf \& Wootters (\emph{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 (\emph{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 (\emph{Computing} 1972) and Kung (\emph{Numer.\ Math.} 1974) for computing the modular inverse of a power series, and might be of independent interest.



Changes to previous version:

Changes in the introduction of the paper.


Revision #2 to TR23-185 | 17th January 2024 06:36

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





Revision #2
Authors: Rohan Goyal, Prahladh Harsha, Mrinal Kumar, A. Shankar
Accepted on: 17th January 2024 06:36
Downloads: 133
Keywords: 


Abstract:

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. This yields, to the best of our knowledge, the first known family of codes that can be decoded (and encoded) in $\tilde{O}(n)$ time, even as they approach the list decoding capacity. 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 (\emph{IEEE Trans.\ Inform.\ Theory} 2013) and Kopparty, Ron-Zewi, Saraf \& Wootters (\emph{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 (\emph{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 (\emph{Computing} 1972) and Kung (\emph{Numer.\ Math.} 1974) for computing the modular inverse of a power series, and might be of independent interest.



Changes to previous version:

Added references to [HRW] and [KRRSW]


Revision #1 to TR23-185 | 29th November 2023 22:12

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





Revision #1
Authors: Rohan Goyal, Prahladh Harsha, Mrinal Kumar, A. Shankar
Accepted on: 29th November 2023 22:12
Downloads: 237
Keywords: 


Abstract:

We show that the known list-decoding algorithms for univariate multiplicity and folded Reed-Solomon (FRS) codes can be made to run in nearly-linear time. This yields, to the best of our knowledge, the first known family of codes that can be decoded (and encoded) in nearly linear time, even as they approach the list decoding capacity. 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 nearly linear time in 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 nearly linear time list-decoding algorithm for Reed-Solomon codes approaching the Johnson radius. As part of the second component, we design nearly-linear 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 nearly-linear 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.



Changes to previous version:

Fixed minor typos


Paper:

TR23-185 | 27th November 2023 21:02

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


Abstract:

We show that the known list-decoding algorithms for univariate multiplicity and folded Reed-Solomon (FRS) codes can be made to run in nearly-linear time. This yields, to the best of our knowledge, the first known family of codes that can be decoded (and encoded) in nearly linear time, even as they approach the list decoding capacity. 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 nearly linear time in 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 nearly linear time list-decoding algorithm for Reed-Solomon codes approaching the Johnson radius. As part of the second component, we design nearly-linear 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 nearly-linear 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.



ISSN 1433-8092 | Imprint