Unique Decoding of Reed–Solomon and Related Codes for Semi-Adversarial Errors

We now present the primary error model we study in this paper: the semi-adversarial error model. It particular, it can be viewed as a composition of the channels defined in the adversarial and random error models.

For any number of total errors $e$, when the number $e_0$ of adversarial errors gets larger, the task of unique-decoding (with high success probability) gets more difficult. As our first nontrivial observation about the semi-adversarial error model, we show that in any MDS code the number $e_0$ of adversarial errors must be bounded by

In particular, to uniquely decode $e$ errors in the semi-adversarial model, the maximum number of adversarial errors that could occur $e_0=\min (e,n-k-e)$. Our formal result is as follows.

We should regard $\overrightarrow{y}$ as the real received word by adding $e-e_0$ random errors upon the adversarial received word $\overrightarrow{z}$. From Proposition 11 we can see that if $e_0>(1-R)n-e$, then no matter the content of random errors the unique-decoding is impossible. As a side remark, Proposition 11 is a special case of Proposition 17.

On the other hand, by slightly adapting the proof of Rudra and Uurtamo [47], we can actually get the following positive combinatorial bound that states with high probability it is possible to uniquely decode from any $e_0\le \min (e,(1-R-\epsilon )n-e)$ adversarial errors, which approaches the optimal bound $(1-R)n$ for diminishing constant $\epsilon$. Formally, we have the following combinatorial unique-decodability.

Motivated by these observations, a very natural question to ask is how to design unique-decoding algorithms in semi-adversarial error model that match the combinatorial bound $(1-R-\epsilon )n-e$ from Proposition 12 or even achieve the optimal bound $(1-R)n-e$. In this paper, we provide unique-decoding algorithms from semi-adversarial errors for (a subclass of) Reed–Solomon and related codes that match the counting-based or even the optimal bound. In particular, our algorithm for interleaved Reed–Solomon codes builds upon the approach of Bleichenbacher, Kiayias, and Yung [13] and Alekhnovich [4] and our algorithms for folded Reed–Solomon and multiplicity codes are entirely new.

Interleaving is a common technique in coding theory that was initially used to design codes and decoders with enhanced burst error-correction capabilities. By dispersing these errors, interleaving transforms them into random errors that are easier to correct. An important subfamily of Reed–Solomon codes is that of interleaved Reed–Solomon (IRS) codes (e.g., [36, 19, 13, 49]).

Given polynomials $f_1,\mathrm{\dots },f_s\in {𝔽}_q[x]$, we define the $s$-interleaved encoding map $ℐ(f_1,f_2,\mathrm{\dots },f_s)$ to be $({𝒞}_1^f,{𝒞}_2^f,\mathrm{\dots },{𝒞}_n^f)\in {\left({𝔽}_q^s\right)}^n,$ where ${𝒞}_i^f:=(f_1({\alpha }_i),f_2({\alpha }_i),\mathrm{\dots },f_s({\alpha }_i))$. With this encoder, we define a $[n,k]$ $s$-interleaved RS code for any distinct ${\alpha }_1,\mathrm{\dots }{\alpha }_n\in {𝔽}_q$ as follows.

where $[s]:=\{1,2,\mathrm{\dots },s\}$. Although an IRS code is technically not an RS code, we show in the full version that IRS codes have decoding properties identical to those of a class of subfield Reed–Solomon codes. That is, if we let ${𝔽}_{q^s}$ be the $s$-degree extension of ${𝔽}_q$, then ${\mathrm{𝖱𝖲}}_{n,k,q^s}({\alpha }_1,\mathrm{\dots },{\alpha }_n)\subseteq {𝔽}_{q^s}^n$ has identical decoding properties in the semi-adversarial model.

We now state our main decoding theorem for IRS codes in the semi-adversarial model. See Figure 1 for a visual summary of our result.

In particular, note that we smoothly interpolate between the algorithms of Berlekamp–Welch for adversarial errors and the algorithm of BKY for random errors. Furthermore, note that as long as $e\le \frac{s}{s+1}(n-k)$, our decoding bound perfectly matches the combinatorial bound of Proposition 11 and Proposition 12. Furthermore, for $e>n-\sqrt{nk}$ we “break” the Johnson bound³³3In this paper “Johnson bound” refers to the error/rate tradeoff of $e\le n-\sqrt{nk}$. We do not improve on Guruswami-Sudan algorithm in the adversarial model. in the sense that our result is not implied by a combination of Guruswami-Sudan with a combinatorial bound on the list size.

Another common variant of RS codes which we study is that of folded Reed–Solomon (FRS) codes [28]. In contrast to IRS codes which bundle the evaluations of the same point $\alpha \in {𝔽}_q$ at $s$ different polynomials, FRS codes bundle $s$ correlated evaluations of the same polynomial. More precisely, let $\gamma$ be a multiplicative generator of ${𝔽}_q$ and consider $s\ge 1$. We say that ${\alpha }_1,\mathrm{\dots },{\alpha }_n\in {𝔽}_q$ are appropriate if the $sn$ values $\{{\gamma }^{j-1}{\alpha }_i:i\in [n],j\in [s]\}$ are distinct [18]. Given $f\in {𝔽}_q[x]$, we define our evaluation map to be $𝒞(f):=({𝒞}_1^f,{𝒞}_2^f,\mathrm{\dots },{𝒞}_n^f)\in {\left({𝔽}_q^s\right)}^n$, with ${𝒞}_i^f:=(f({\alpha }_i),f(\gamma {\alpha }_i),\mathrm{\dots },f({\gamma }^{s-1}{\alpha }_i)).$ Then, for parameters $n,k$ and appropriate evaluation points ${\alpha }_1,\mathrm{\dots },{\alpha }_n\in {𝔽}_q$, we define our $(s,\gamma )$-folded RS code to be

We now state our results which apply to folded Reed–Solomon codes.

Compared to the well-known Guruswami–Wang algorithm [27, 30, 34, 23] , a key advantage of our novel algorithm is that it replaces the less-efficient root-finding step with a straightforward polynomial long division, resulting in a substantial efficiency boost. However, this is in tradeoff to the fact that the Guruswami–Wang algorithm can handle fully adversarial errors, whereas our approach is limited to semi-adversarial errors.

Our final main result is for another popular variant of RS codes known as (univariate) multiplicity codes (e.g., [30, 35, 33]). Again, multiplicity codes are similar to IRS codes except this time instead of evaluating a point $\alpha$ at $s$ different polynomials, multiplicity codes evaluate $s$ Hasse derivatives of the same polynomial at $\alpha$. In particular, given $f\in {𝔽}_q[x]$ and symbolic variable $z$, we define $f^{(i)}(x)$ (the $i$-th Hasse derivative) to be the coefficient of $z^i$ in the expansion of $f(x+z)$. From this, we can define our evaluation function to be $ℳ(f):=({𝒞}_1^f,{𝒞}_2^f,\mathrm{\dots },{𝒞}_n^f)\in {\left({𝔽}_q^s\right)}^n$, with ${𝒞}_i^f:=(f({\alpha }_i),f^{(1)}({\alpha }_i),\mathrm{\dots },f^{(s-1)}({\alpha }_i))$. Then, for parameters $n,k,s$ and distinct evaluation points ${\alpha }_1,\mathrm{\dots },{\alpha }_n\in {𝔽}_q$, our multiplicity code is defined to be

As in Theorem 14, Theorem 16 has the advantage of the work of Guruswami–Wang algorithm [27, 30, 34, 23] of replacing the less-efficient root-finding step with a straightforward polynomial long division, resulting in a substantial efficiency boost.

Since the 1960s, efficiently decoding Reed–Solomon (RS) codes has become a central subject of study in coding theory, due to its importance in both practical error-correction applications and fundamental theoretical research in algorithms, complexity, and cryptography (e.g., [8, 10, 9, 6]). For an $[n,k]$ Reed–Solomon code, it can uniquely correct up to $(n-k)/2$ adversarial errors. During the past half century, numerous algorithms have been developed to uniquely decode Reed–Solomon codes up to this bound in the adversarial error model (e.g., [42, 22, 55, 12, 39, 20]). Among these many algorithms, two of the most popular are the Berlekamp–Welch algorithm [55] and the Berlekamp–Massey algorithm [39].

The Berlekamp–Welch algorithm, with a running time complexity of $O(n^3)$, employs a clever algebraic technique to decode Reed–Solomon codes, using polynomial interpolation to identify and correct errors. More concretely, [55] approaches the decoding problem by transforming it into a task of finding two polynomials: an error locator polynomial $E(x)$ and a numerator polynomial $Q(x)$. For a received word represented as points $({\alpha }_i,y_i)$, where ${\alpha }_i$ are distinct evaluation points and $y_i$ are the received (corrupted) values, the algorithm sets up a system of linear equations based on the condition $Q({\alpha }_i)=y_{i}E({\alpha }_i)$ for all $i$. Here, $E(x)$ has degree equal to the number of errors $e$, and $Q(x)$ has degree less than $k+e$, where $k$ is the dimension of the code. When the number of errors $e$ is at most $(n-k)/2$, this system has a unique solution up to scaling. Solving it allows the decoder to determine $E(x)$, whose roots indicate the error locations, and subsequently recover the original message polynomial as $Q(x)/E(x)$.

Unlike an interpolation-based framework, the Berlekamp–Massey algorithm [39], with a better running time complexity of $O(n^2)$, takes a different approach by directly processing the syndrome sequence to find the error locator polynomial, taking advantage of shift registers for multiplication. Their method is recognized as a standard syndrome-based decoding framework. By building on these two algorithms, more efficient algorithms have been developed with a running time complexity of $O(n\cdot \mathrm{poly}(\log n))$ (e.g., [44, 38, 54]).

Beyond unique decoding, to correct more than $(n-k)/2$ errors in the adversarial error model, list decoding algorithms are involved (e.g., [53, 29, 46, 4, 56]). In 1997, inspired by the Berlekamp–Welch algorithm, Sudan [53] provided the first list decoding algorithm of Reed–Solomon codes capable of correcting up to $n-\sqrt{2nk}$ errors. Later, by introducing the notion of multiplicity, Guruswami and Sudan [29] designed an improved list decoding algorithm that can correct up to $n-\sqrt{nk}$ errors, matching the Johnson bound [32]. Two follow-up works by Roth–Ruckenstein [46] and Alekhnovich [4] showed some fast implementations of the Guruswami–Sudan algorithm in time $O(n^2)$ and $O(n\cdot \mathrm{poly}(\log n))$ respectively. Most recently, a long line of works [48, 50, 16, 26, 5] have shown that Reed–Solomon codes can achieve list decodability beyond the Johnson bound, reaching up to list decoding capacity. However, it remains an open problem to design a list decoding algorithm for any subclasses of Reed–Solomon codes capable of correcting adversarial errors beyond the Johnson bound. We emphasize that our result on interleaved Reed–Solomon codes (see Theorem 13) addresses this question in the semi-adversarial error model.

Over the past two decades, considerable attention has been devoted to develop (unique) decoder (e.g., [36, 19, 13, 49, 43, 57]) for interleaved RS codes – an important subclass of RS codes – especially under the random error model. In particular, two independent seminal works – one by Coppersmith and Sudan [19] and the other by Bleichenbacher, Kiayias, and Yung [13] – proposed two remarkable (probabilistic) unique decoding algorithms that demonstrate surprisingly large error correction capabilities under the random error model.⁴⁴4Although BKY’s result is only stated in the weaker model in which the errors locations are randomly located, the proof can be adapted to also handle adversarial error locations. This fact was recently observed by [24, 1], where they adapted the BKY algorithm for rational evaluation codes.

Coppersmith–Sudan is in some sense the dual of the multivariate interpolation decoding algorithm developed by Parvaresh Vardy [41] (although Coppersmith Sudan predates the Parvaresh Vardy algorithm).

The well-known Guruswami-Sudan algorithm does bivariate interpolation (i.e., a polynomial in $(X,Y)$) on the space of points of the form $\{({\alpha }_i,y_i):i\in [n]\}$, where ${\alpha }_i$ is the $i$-th evaluation point and $y_i$ is the $i$-th received symbol. They use this interpolation to list decode Reed Solomon codes up to an error threshold of $1-\sqrt{R}$. Multivariate interpolation decoding extends this idea to interleaved Reed-Solomon codes where one interpolates a $s+1$ variate polynomial over $(X,Y_1,\mathrm{\dots },Y_s)$, where $(Y_1,\mathrm{\dots },Y_s)$ corresponds to the $s$ components of each received symbol. If the error threshold is $1-R^{s/(s+1)}$ then one can show that the interpolated polynomials will lie in the ideal $⟨Y_1-f_1,\mathrm{\dots },Y_s-f_s⟩$. In general, this is not enough for decoding as $Y_i-f_i(x),i\in [n]$ may have many algebraic dependencies, but experimentally that occurs with negligible probability. Parvaresh and Vardy conjecture that for the setting of random errors multivariate interpolation decoding will succeed up to the error rate $1-R^{s/(s+1)}$ with high probability (around $1-n^{-cn}$). The only theoretical result studying this is a follow up work of, Parvaresh, Taghavi, and Vardy [40] which shows that this algorithm succeeds for $s=2$ with error rate $1-{(6R)}^{2/3}-O(R^{5/3})$ and with failure probability at most $n^{-cn}$.

Interpolating over $X,Y_1,\mathrm{\dots },Y_s$ for $n$ evaluation points ${\alpha }_1,\mathrm{\dots },{\alpha }_n$ without multiplicity can be set up as finding an element in the row-kernel of a matrix where the columns are indexed by $i\in [n]$ and the rows are indexed by monomials $m$ in $X,Y_1,\mathrm{\dots },Y_s$ with the entries being $m$ evaluated at $X={\alpha }_i$ and $(Y_1,\mathrm{\dots },Y_s)$ equals the $i$-th letter in the received word. Coppersmith-Sudan [19] picks an element in the column kernel of this matrix and uses its support (the coordinates $j\in [n]$ which are non-zero in the chosen vector) to help decode the codeword. Using multiplicities, they get further improvements. In the end, they obtain a (unique) decoder capable of correcting $1-R^{\frac{s}{s+1}}-R$ fraction of random errors with a failure probability at most $O(n^s/q)$.

In contrast, Bleichenbacher, Kiayias, and Yung [13] draw inspiration from the original Berlekamp–Welch unique decoder [55], providing a (unique) decoder capable of correcting $\frac{s}{s+1}(1-R)$ fraction of random errors with a failure probability at most $O(n/q).$ The failure probability of [13] was further reduced to $O(1/q)$ by Brown, Minder, and Shokrollahi [17].

Later, inspired by another famous unique decoder of Berlekamp and Massey [11, 39], Schmidt, Sidorenko, and Bossert [49] proposed a faster syndrome-based unique decoder⁵⁵5The IRS codes considered in [49] require a cyclic restriction on their evaluation points. capable of correcting $\frac{s}{s+1}(1-R)$ fraction of random errors with a failure probability at most $O(1/q)$. The running time of their algorithm is $O_s(n^2)$ (i.e., $n^2$ times some function of $s$). More recently, using power decoding techniques, Puchinger and Nielsen [43] proposed an improved algorithm with a conjectured error correction capability that can correct up to $1-R^{\frac{s}{s+1}}$ fraction of random errors. However, although [43] has demonstrated numerous simulations for a wide variety of parameters that support the heuristic correctness of their approach, a formal proof of the theoretical correctness of their proposed algorithm remains open. Therefore, from a theoretical perspective, for $R>1/3$ and $s>2$, the relative decoding radius $\frac{s}{s+1}(1-R)$ for $s$-interleaved RS codes of rate $R$ remains state-of-the-art, as demonstrated in [36, 13, 49].

Folded Reed–Solomon (RS) codes and multiplicity codes are two prominent variants of RS codes, with list decoders (e.g., [28, 33, 27, 30, 34, 23]) that achieve the list decoding capacity even in the presence of adversarial errors. The first folded RS code list decoder was introduced in the seminal work of Guruswami and Rudra [28], building on the ideas of the Guruswami–Sudan list decoder. The first list decoder for multiplicity codes was introduced independently by Guruswami–Wang [30] and Kopparty [33], and it remains the most widely used framework in this domain.

In fact, Guruswami and Wang [27, 30] proposed a unified linear algebraic list decoding algorithm for folded RS and multiplicity codes capable of correcting adversarial errors up to capacity. However, for codes of rate $R$ and block length $n$, the list size guarantee from [30] is $O\left(n^{1/\epsilon }\right)$ when decoding up to radius $1-R-\epsilon$. A follow-up work by Kopparty, Ron-Zewi, Saraf, and Wootters [34] introduced a randomized algorithm for the root-finding step under the Guruswami–Wang decoding framework, significantly improving its efficiency and reducing the list size guarantee to ${\left(1/\epsilon \right)}^{O(1/\epsilon )}$. Another follow-up work by Goyal, Harsha, Kumar, and Shankar [23] adapted the approach of Alekhnovich [4] into the Guruswami–Wang decoding framework, improving the running time to quasi-linear, which is $\tilde{O}\left(2^{\mathrm{poly}(1/\epsilon )}\cdot n\right)$.

As a side remark, very recently, two concurrent and independent works by Srivastava [52] and Chen–Zhang [18] provided dramatic improvements, reducing the list size from ${\left(1/\epsilon \right)}^{O(1/\epsilon )}$ to $O(1/{\epsilon }^2)$ and $O\left(1/\epsilon \right)$, respectively. Moreover, the Chen–Zhang bound almost matches the generalized Singleton bound [50] up to a constant multiplicative factor. It is worth noting that both proofs of Srivastava and Chen–Zhang are purely combinatorial, and turning them into efficient algorithms remains an open problem. For further details, the reader is referred to the most recent comprehensive survey by Garg, Harsha, Kumar, Saptharishi, and Shankar [21].

Meanwhile, current efficient decoding algorithms for folded Reed–Solomon and multiplicity codes are heavily based on the Guruswami–Wang decoder framework [27, 30]. It is an interesting open problem to design alternative, more efficient decoding algorithms for folded RS and multiplicity codes that do not rely on the Guruswami–Wang framework, and a primary contribution of this paper is making progress toward this exact question.

As previously mentioned, we define folded Reed–Solomon codes in the sense of Guruswami–Rudra [28]. However, the term “folded Reed–Solomon codes” was first coined in a paper by Krachkovsky [37]. The codes defined in both papers are constructed by bundling $s$ classical Reed–Solomon codes, but they choose evaluation points in different ways. Concretely, recall that for the folded Reed–Solomon codes defined in [28], for each $i\in [n]$ and message polynomimal $f$, the $i$-th symbol in the encoding of $f$ is $(f({\alpha }_i),f(\gamma {\alpha }_i)\mathrm{\dots },f({\gamma }^{s-1}{\alpha }_i))\in {𝔽}_q^s$, where ${\alpha }_i\in {𝔽}_q$ and $\gamma$ is a generator of ${𝔽}_q^{\times }$. On the other hand, [37] defined it as $(f({\alpha }^i),f({\alpha }^{i+n})\mathrm{\dots },f({\alpha }^{i+(s-1)n}))\in {𝔽}_q^s$, where $\alpha$ has order exactly $sn$ in ${𝔽}_q^{\times }$. This special choice on evaluation points enables [37] to perform FFT-related algorithms and obtain a syndrome-based decoding algorithm for random “phased burst” errors.

Subsequent to the first posting of our work, Ashvinkumar, Habib, and Srivastava [7] presented new algorithms for decoding folded Reed-Solomon codes in the adversarial error model.

We begin by discussing our new algorithm for interleaved Reed–Solomon codes (Theorem 13). Our algorithm and analysis builds on the techniques used by Bleichenbacher, Kiayias, and Yung [13], but we deviate from their methods in a few significant ways. In this IRS decoding algorithm, our main technical contribution is that we use a novel monomial-tracking argument to analyze the performance of this algorithm in the new semi-adversarial error setting.

To describe these improvements, we first discuss the interpolation algorithm of [13] (henceforth the “BKY algorithm”). Consider the $s$-interleaved Reed–Solomon code $𝒞:={\mathrm{𝖨𝖱𝖲}}_{n,k,q,s}({\alpha }_1,\mathrm{\dots },{\alpha }_n)$ with distinct ${\alpha }_1,\mathrm{\dots },{\alpha }_n\in {𝔽}_q\setminus \{0\}$. We choose polynomials $f_1(X),\mathrm{\dots },f_s(X)$ of degree at most $k-1$ as our message, encoding them according to $𝒞$ and transmit them across the channel. Assume that our received word $\overrightarrow{y}:=({\overrightarrow{y}}_1,{\overrightarrow{y}}_2,\mathrm{\dots },{\overrightarrow{y}}_n)\in {({𝔽}_q^s)}^n$, where ${\overrightarrow{y}}_i:=(y_{i,1},y_{i,2},\mathrm{\dots },y_{i,s})\in {𝔽}_q^s$.

The BKY algorithm begins by assuming $\overline{e}$ of the $n$ coordinates of $\overrightarrow{y}$ are corrupted. To identify these $\overline{e}$ coordinates, the BKY algorithm adapts the Berlekamp-Welch algorithm by solving the following interpolation problems. Let $E(X)$ be a polynomial of degree at most $\overline{e}$ with unknown coefficients and let $A_1(X),\mathrm{\dots },A_s(X)$ be polynomials of degree at most $k-1+\overline{e}$ with unknown coefficients. We seek to solve the following interpolation equations:

To analyze this system of equations, we consider the block matrix

where $𝐌\in {𝔽}_q^{n\times (k+\overline{e})}$ such that ${𝐌}_{i,j}={\alpha }_i^{j-1}$, and for each $h\in [s]$ we have that ${𝐍}_h\in {𝔽}_q^{n\times \overline{e}}$ with ${({𝐍}_h)}_{i,j}=y_{i,h}{\alpha }_i^j$. For the purposes of this overview, assume for simplicity that $𝐁$ is a square matrix. That is, $s(k+\overline{e})+\overline{e}=sn$. In this scenario, one can prove that the interpolation (1) succeeds if and only if, we have that $det𝐁\ne 0$. That is, it suffices to bound the probability that $det𝐁\ne 0$ over the random errors in the channel. By the Schwartz-Zippel lemma, it suffices to replace the random errors $y_{i,h}$ with corresponding symbolic variables $Y_{i,h}$ to create a symbolic matrix ${𝐁}^{\mathrm{𝖲𝖸𝖬}}$ and argue that $det{𝐁}^{\mathrm{𝖲𝖸𝖬}}\ne 0$.

Bleichenbacher, Kiayias, and Yung [13] proceeded to argue this by substituting fixed values for some of the $Y_{i,h}$’s and then using an ad-hoc analysis of the determinant to argue that it is nonzero. We improve on the BKY algorithm and analysis in two significant ways. First, we improve the runtime of the algorithm from roughly $O(n^4)$ time to near-linear time by using the interpolation framework of Alekhnovich [4] to solve (1) efficiently.⁶⁶6After the initial posting of our work, we also learned that the use of Alekhnovich [4] and similar techniques for fast polynomial interpolation have appeared in related works [58, 25]. In particular, the interpolation framework automatically finds the optimal choice of $\overline{e}$ rather than doing a brute-force search like in the BKY algorithm.

Second, we streamline the analysis of the determinant of (2). By applying a series of column operations to $𝐁$, we can transform the rightmost blocks ${𝐍}_1,\mathrm{\dots },{𝐍}_s$ into diagonal matrices ${𝐃}_1,\mathrm{\dots },{𝐃}_s$, where each ${𝐃}_h$ corresponds precisely to the errors which occur in the transmission of the codeword. The exact sequence of column operations needed to reveal these errors depends on the original polynomials $f_1,\mathrm{\dots },f_s$, but we can assume polynomials are known for the purposes of analyzing the rank of $𝐁$.

By having the errors be presented transparently as diagonal matrices, arguing that $det{𝐁}^{\mathrm{𝖲𝖸𝖬}}\ne 0$ can be done in a much more straightforward manner. In particular, it suffices to identify an explicit monomial $Y_{i_1,h_1}\mathrm{\cdots }{Y}_{i_{\mathrm{\ell }},h_{\mathrm{\ell }}}$ with the following properties:

P1.

There is exactly one expansion of the last $\overline{e}$ columns of ${𝐁}^{\mathrm{𝖲𝖸𝖬}}$ which produces that monomial.

P2.

The minor induced by that monomial choice has nonzero determinant.

In the purely random error model, finding such a choice of monomials is straightforward–any choice of monomials from distinct columns for which an equal number of variables appear in each row block will work. However, the true power of this perspective is that it gives us a foothold for analyzing a mixture of adversarial and random errors, i.e., the semi-adversarial error model. More precisely, depending on the exact choices for the adversarial errors, the set of monomials which satisfy both P1 and P2 can change significantly. In particular, there is no “oblivious” choice for the monomial. Instead, we give a procedure which constructs a monomial based on the pattern of the adversarial errors–which we may assume we know for the purposes of the analysis. At a high level this procedure is a greedy algorithm, we iterated through the row blocks of $𝐁$ and in each block we pick the maximal number of monomials possible such that P1 and P2 can still hold.

Next, we describe the algorithm and analysis leading to Theorem 14. The new decoding algorithm is inspired by the previous IRS algorithm plus the Guruswami-Wang [30] interpolation. The analysis for semi-adversarial errors follows the similar framework as in the IRS case. However, the monomial-tracking is more difficult for FRS codes and we therefore use a new “greedy algorithm” to find the special monomial. This is the main challenge of extending the analysis for IRS to FRS.

Let $𝒞:={\mathrm{𝖥𝖱𝖲}}_{n,k,q}^{s,\gamma }({\alpha }_1,{\alpha }_2,\mathrm{\dots },{\alpha }_n)\subseteq {({𝔽}_q^s)}^n$ and consider a polynomial $f(X)$ of degree at most $k-1$. After encoding $f$ according to $𝒞$ and transmitting it through the $(e_0,\overline{e})$-semi-adversarial channel, let $\overrightarrow{y}:=({\overrightarrow{y}}_1,{\overrightarrow{y}}_2,\mathrm{\dots },{\overrightarrow{y}}_n)\in {({𝔽}_q^s)}^n$, where ${\overrightarrow{y}}_i:=(y_{i,1},y_{i,2},\mathrm{\dots },y_{i,s})\in {𝔽}_q^s$ is the received message. Pick parameters $\overline{e}\in [n]$ and $L\in [s]$ and consider the following $L$-length interpolation equations:

Like for BKY interpolation, these interpolation equations can be solved in near-linear time using the techniques of Alekhnovich [4]. To the best of our knowledge, our interpolation is novel, blending characteristics of both BKY and Guruswami–Wang [30] interpolation. In particular, compared to other list-decoding algortihms for folded Reed–Solomon codes (such as Guruswami–Wang), the lower-order terms in the runtime for our approach are much smaller. More concretely, our running time is $\tilde{O}(\mathrm{poly}(s)n)$, while the current best implementation of the Guruswami–Wang algorithm takes time $\tilde{O}(2^{\mathrm{poly}(s)}n)$ [23]. A key advantage of our algorithm is that it eliminates the need for the root-finding step required in the Guruswami–Wang algorithm. Instead, after our new interpolation, only a simple polynomial long division is necessary.

To analyze these interpolation equations, we construct a block matrix similar to that of (2). Now, the number of rows in each block is $(s-L+1)n$, which we index by a pair $(i,j)\in [s-L+1]\times [n]$. Then, $𝐌\in {𝔽}_q^{(s-L+1)n\times (k+\overline{e})}$ has the structure ${𝐌}_{(i,j),\mathrm{\ell }}={({\gamma }^{i-1}{\alpha }_j)}^{\mathrm{\ell }-1}$ and for each $h\in [s]$, we have that ${({𝐍}_h)}_{(i,j),\mathrm{\ell }}=y_{j,i+h-1}{({\gamma }^{i-1}{\alpha }_j)}^{\mathrm{\ell }}$.

Using the techniques of Bleichenbacher, Kiayias, and Yung [13], this matrix would be very difficult to analyze directly, but by applying analogous simplifications to the ones we used for interleaved Reed–Solomon codes, we can again transform the last block-column of $𝐁$ to consist only of diagonal matrices. However, since our interpolation is $L$-length, we now have the extra challenge that each error can appear in up to $L$ diagonal matrices (since each $y_{j,i+h-1}$ can appear up to $L$ times).

Like in the IRS case, we transform $𝐁$ into a symbolic matrix ${𝐁}^{\mathrm{𝖲𝖸𝖬}}$ with symbolic variables as substitutes for the random variables. We then seek to find a monomial in ${𝐁}^{\mathrm{𝖲𝖸𝖬}}$ satisfying the aforementioned properties P1 and P2. With the combination of repeated symbolic variables as well as the presence of adversarial errors in the semi-adversarial model, the procedure of identifying a valid monomial becomes significantly more complex. It is still fundamentally a greedy algorithm like in the IRS case, but much more bookkeeping is needed to ensure that P1 and P2 remain satisfied.

Next, we describe the adaptations of Theorem 14 which led to Theorem 16. Fundamentally, the interpolation is similar to that of (3), except we now replace multiplication by $\gamma$ with taking a derivative of the message polynomial $f$. That is, our length-$L$ interpolation equations are of the form,

where $E$ again has degree at most $\overline{e}$. Again, this interpolation can be done in near-linear time by using the interpolation algorithm of Alekhnovich [4]. Note that due to the chain rule for derivatives, the error term in (4) turns into a sum. As a result, if we build an interpolation matrix $𝐁$ similar to that of (2) to analyze (4), we cannot use column operations to simplify the final column block to only consist of diagonal matrices. Instead, we will have block-diagonal matrices for which each block is a lower triangular matrix. The corresponding symbolic matrix ${𝐁}^{\mathrm{𝖲𝖸𝖬}}$ will have each variable appear numerous times, with repetition coming both from the “length-$L$” of the interpolation as well as the repeated terms arising from the chain rule.

Again, we seek to identify a symbolic monomial in the expansion of $det{𝐁}^{\mathrm{𝖲𝖸𝖬}}$ which satisfies properties P1 and P2. The key observation is that within one of these lower triangular matrices, variable appearing in the lower left corner appears exactly once. Thus, by using a greedy algorithm which starts by taking monomials from these lower left corners, we have much more control over the uniqueness of the monomial selected.