17 Efficiently Achieving List Decoding Capacity

In earlier chapters we saw: Reed-Solomon codes of rate \(\)R>0\( can be list-decoded in polynomial time from \)1-R\( fraction of errors (Guruswami-Sudan, Ch.\ 12), and that there exist codes of rate \)R>0\( that are \)(1-R-ε, O(1/ε))\(-list decodable for \)q≥2^Ω(1/ε)\( (Ch.\ 7, Ch.\ 3). There is a gap between the best known algorithmic result and the best possible combinatorial result: are there \emph{explicit} codes of rate \)R>0\( that can be list-decoded in polynomial time from \)1-R-ε\( fraction of errors for \)q≤poly(n)\(? This chapter answers this question in the affirmative, using \emph{Folded Reed-Solomon codes}. \begin{thmenv}[Over-determined homogeneous linear systems have a nonzero solution] \label{lem:c17-linear-system-nonzero-solution} \mathlibok A homogeneous system of linear equations over a field with strictly more variables than equations has a non-zero solution. \end{thmenv} \begin{thmenv}[Degree mantra] \label{lem:c17-degree-mantra} \mathlibok A non-zero polynomial of degree at most \end{thmenv} \)d\( over a field has at most \)d\( roots. Equivalently, if a polynomial of degree at most \)d\( has more than \)d\( roots (counted without multiplicity), it is identically zero. \)

17.1 Folded Reed-Solomon Codes

We introduce a new family of codes, the Folded Reed-Solomon codes. These codes are constructed by combining every \(\)m\( consecutive symbols of a regular Reed-Solomon code into one symbol from a larger alphabet. For a Reed-Solomon code that maps \)F_q^kF_q^n\(, the corresponding Folded Reed-Solomon code maps \)F_q^kF_q^m^n/m\(. We analyze Folded Reed-Solomon codes derived from Reed-Solomon codes with evaluation points \){1,γ,γ^2,…,γ^n-1}\(, where \)γ\( is a generator of \)F_q^*\( and \)n≤q-1\(. \begin{thmenv}[Folded Reed-Solomon Code, Def.\ 17.1.1] \label{def:c17-frs} The \end{thmenv} \)m\(-folded version of an \)[n,k]_q\( Reed-Solomon code \)C\( (with evaluation points \){1,γ,…,γ^n-1}\(), call it \)C’\(, is a code of block length \)N=n/m\( over \)F_q^m\(, where \)n≤q-1\(. The encoding of a message \)f(X)\(, a polynomial over \)F_q\( of degree at most \)k-1\(, has as its \)j\('th symbol, for \)0≤j< n/m\(, the \)m\(-tuple \[ \bigl(f(\gamma ^{jm}), f(\gamma ^{jm+1}),\dots , f(\gamma ^{jm+m-1})\bigr). \] In other words, the codewords of \)C’\( are in one-one correspondence with those of the Reed-Solomon code \)C\( and are obtained by bundling together consecutive \)m\(-tuples of symbols in codewords of \)C\(. \uses{def:c05-reed-solomon, def:c02-finite-field} \)

\(\)C\( denotes the \)[n,k]_q\( Reed-Solomon code of rate \)R=k/n\( with evaluation points \){1,γ,…,γ^n-1}\(, where \)γ\( generates \)F_q^*\( and \)n≤q-1\(; for a folding parameter \)m≥1\( dividing \)n\(, \)FRS=C’\( denotes its \)m\(-folded version (Definition~ \ref{def:c17-frs}), of block length \)N=n/m\(, so \)k=mRN\(. \uses{def:c17-frs} \)

17.1.1 The Intuition Behind Folded Reed-Solomon Codes

The folding trick above cannot decrease the list decodability of the code.

\(\)ρ\( fraction of errors, then the corresponding Folded Reed-Solomon code with folding parameter \)m\( can also be list-decoded from \)ρ\( fraction of errors. \uses{def:c17-frs, assumption:c17-setup, def:c07-list-decoding, def:c01-hamming-distance} \begin{proof} The idea is to “unfold” the received word and then run a list decoding algorithm \end{proof}\)A\( for the Reed-Solomon code on the unfolded received word, returning the resulting set of messages; see Algorithm~ \ref{alg:c17-unfold-decode}. Let \)mF_q^k\( be a message and let \)RS(m)\( and \)FRS(m)\( be the corresponding Reed-Solomon and Folded Reed-Solomon codewords. Let \)y=((y_1,1,…,y_1,m),…, (y_n/m,1,…,y_n/m,m))F_q^m^n/m\( be a received word and \)y’=(y_1,1,…,y_1,m,…,y_n/m,1,…,y_n/m,m)F_q^n\( its unfolding. For every \)i[n/m]\(, if \)FRS(m)_i≠(y_i,1,…,y_i,m)\( then, in the worst case, for every \)j[n/m]\(, \)RS(m)_(i-1)n/m+j≠y_i,j\(: i.e.\ one symbol disagreement over \)F_q^m\( can lead to at most \)m\( disagreements over \)F_q\(. Hence for any \)mF_q^k\(, if \)Δ(y,FRS(m)) ≤ρ·n/m\(, then \)Δ(y’,RS(m))≤m·ρ·n/m = ρ·n\(, which by the list-decoding property of \)A\( implies Step~ 2 of Algorithm~ \ref{alg:c17-unfold-decode} outputs \)m\(, as desired. \uses{alg:c17-unfold-decode} \)

\(\)y=((y_1,1,…,y_1,m),…,(y_n/m,1,…,y_n/m,m)) F_q^m^n/m\(, and a list decoding algorithm \)A\( for the underlying Reed-Solomon code. \textsc{Output}: A list of messages in \)F_q^k\(. \begin{enumerate} \item \end{enumerate}\)y’←(y_1,1,…,y_1,m,…,y_n/m,1,…,y_n/m,m) F_q^n\(. \item \textsc{Return} \)A(y’)\(. \)

17.2 List Decoding Folded Reed-Solomon Codes: I

We begin with an algorithm for list decoding Folded Reed-Solomon codes that works with agreement \(\)t∼mRN\( (a factor \)m\( larger than the \)RN\( agreement we ultimately want). The algorithm is a generalization of the Welch-Berlekamp algorithm which interpolates an \)(m+1)\(-variate polynomial \)Q(X,Y_1,…,Y_m)\( of degree exactly one in each \)Y_i\(, and then shows that all the roots of \)Q\( form an (affine) subspace. \begin{thmenv}[The First List Decoding Algorithm for Folded Reed-Solomon Codes, Algorithm 17.2.1] \label{alg:c17-algo1} \textsc{Input}: An agreement parameter \end{thmenv} \)0≤t≤N\(, a parameter \)D≥1\(, and the received word \[ \mathbf{y}=\begin{pmatrix} y_0 & y_m & \cdots & y_{n-m} \\ \vdots & \vdots & & \vdots \\ y_{m-1} & y_{2m-1} & \cdots & y_{n-1} \end{pmatrix}\in \mathbb {F}_q^{m\times N}, \qquad N=\frac{n}{m}. \] \textsc{Output}: All polynomials \)f(X)F_q[X]\( of degree at most \)k-1\( such that for at least \)t\( values of \)0≤i<N\(, \[ \bigl(f(\gamma ^{mi}),\dots ,f(\gamma ^{m(i+1)-1})\bigr)=(y_{mi},\dots ,y_{m(i+1)-1}). \] \begin{enumerate} \item Compute a non-zero \end{enumerate}\)Q(X,Y_1,…,Y_m)=A_0(X)+A_1(X)Y_1++A_m(X)Y_m\( with \)(A_0)≤D+k-1\( and \)(A_j)≤D\( for \)1≤j≤m\(, such that \[ Q\bigl(\gamma ^{mi}, y_{mi},\dots ,y_{m(i+1)-1}\bigr)=0,\qquad \forall \, 0\le i{\lt}N. \] \item \)L←∅\(. \item For every \)f(X)F_q[X]\( such that \)Q(X,f(X),f(γX),…,f(γ^m-1X))≡0\(: if \)(f)≤k-1\( and \)f(X)\( satisfies the agreement condition above for at least \)t\( values of \)i\(, add \)f(X)\( to \)L\(. \item Return \)L\(. \)

\(\)(m+1)(D+1)+k-1 > N\(, then there exists a non-zero \)Q(X,Y_1,…,Y_m)\( that satisfies the required properties of Step~ 1 of Algorithm~ \ref{alg:c17-algo1}. \uses{alg:c17-algo1, lem:c17-linear-system-nonzero-solution} \begin{proof} Think of the constraints on \end{proof}\)Q\( as linear equations. The variables are the coefficients of \)A_i(X)\( for \)0≤i≤m\(. With the stipulated degree constraints, the number of variables participating is \[ D+k+m(D+1) = (m+1)(D+1)+k-1. \] (\)A_0(X)\( has degree at most \)D+k-1\(, contributing \)D+k\( variables, and each of the \)m\( polynomials \)A_j(X)\( for \)j[m]\( has degree at most \)D\(, contributing \)D+1\( variables each.) The number of equations is \)N\(. Thus the hypothesis \)(m+1)(D+1)+k-1>N\( implies there are strictly more variables than equations, and by Lemma~ \ref{lem:c17-linear-system-nonzero-solution} there exists a non-zero solution \)Q\( with the required properties. \uses{lem:c17-linear-system-nonzero-solution} \)

\(\)t>D+k-1\(, then every polynomial \)f(X)F_q[X]\( of degree at most \)k-1\( that agrees with the received word in at least \)t\( positions is returned by Step~ 3 of Algorithm~ \ref{alg:c17-algo1}. \uses{alg:c17-algo1, lem:c17-degree-mantra} \begin{proof} Define the univariate polynomial \[ R(X)=Q\bigl(X,f(X),f(\gamma X),\dots ,f(\gamma ^{m-1}X)\bigr). \] Since \end{proof}\)(f(γ^i X))=(f(X))\(, the degree constraints on the \)A_i(X)\('s and \)f(X)\( give \)(R)≤D+k-1\(. On the other hand, for every \)0≤i<N\( where \)f(X)\( agrees with the received word in position \)i\(, we have \[ R(\gamma ^{mi}) = Q\bigl(\gamma ^{mi}, y_{mi},\dots ,y_{m(i+1)-1}\bigr)=0, \] where the second equality is the defining property of \)Q\( from Step~ 1. Thus \)R(X)\( has at least \)t\( roots. Since \)t>D+k-1≥(R)\(, by the degree mantra (Lemma~ \ref{lem:c17-degree-mantra}) \)R(X)≡0\(, i.e.\ \)f(X)\( satisfies the condition of Step~ 3 and is added to \)L\(. \uses{lem:c17-degree-mantra} \)

\(\)m≥1\( and rate \)R\( up to \)(1-mR)\( fraction of errors. \uses{lem:c17-claim1721, lem:c17-claim1722, assumption:c17-setup} \begin{proof} The condition of Claim~ \ref{lem:c17-claim1721} is satisfied by choosing \[ D=\left\lfloor \frac{N-k+1}{m+1}\right\rfloor . \] This in turn implies the condition of Claim~ \ref{lem:c17-claim1722} is satisfied if \[ t {\gt} \frac{N-k+1}{m+1}+k-1 = \frac{N+m(k-1)}{m+1}. \] This is satisfied if \[ t\ge \frac{N}{m+1}+\frac{mk}{m+1}=N\left(\frac{1}{m+1}+mR\left(\frac{m}{m+1}\right)\right), \] using \end{proof}\)k=mRN\(. When \)m=1\( this exactly recovers the bound for the Welch-Berlekamp algorithm. Thus the algorithm succeeds whenever the number of agreements \)t\( exceeds \)N+mR·\(, i.e.\ whenever the number of errors is at most \[ N-t = N\left(1-\frac{1}{m+1}-\frac{m^2R}{m+1}\right) = \frac{m}{m+1}N\bigl(1-mR\bigr), \] i.e.\ Algorithm~ \ref{alg:c17-algo1} list decodes from up to \)(1-mR)\( fraction of errors. \uses{lem:c17-claim1721, lem:c17-claim1722} \)

Note that if the factor \(\)mR\( in the bound of Theorem~ \ref{thm:c17-thm1723} could be replaced by just \)R\(, then we would approach the list decoding capacity bound of \)1-R\(. In the next section, we show how to ``knock off'' the extra factor of \)m\(. \)

17.3 List Decoding Folded Reed-Solomon Codes: II

We now present the final version of the algorithm that answers the chapter’s opening question in the affirmative. The new idea allows us to knock off the factor of \(\)m\(: if the folding parameter is \)m\( and \)f(X)\( agrees with the received word in position \)i\(, this single agreement over one \)F_q^m\( symbol can be exploited, by ``sliding a window'' of size \)s≤m\( over the \)m\( symbols from \)F_q\(, into \)m-s+1\( agreements over \)F_q^s\(. This requires the interpolation polynomial \)Q\( to be \)(s+1)\(-variate instead of \)(m+1)\(-variate. \begin{thmenv}[The Second List Decoding Algorithm for Folded Reed-Solomon Codes, Algorithm 17.3.1] \label{alg:c17-algo2} \textsc{Input}: An agreement parameter \end{thmenv} \)0≤t≤N\(, a parameter \)D≥1\(, an integer \)1≤s≤m\(, and the received word \[ \mathbf{y}=\begin{pmatrix} y_0 & y_m & \cdots & y_{n-m} \\ \vdots & \vdots & & \vdots \\ y_{m-1} & y_{2m-1} & \cdots & y_{n-1} \end{pmatrix}\in \mathbb {F}_q^{m\times N}, \qquad N=\frac{n}{m}. \] \textsc{Output}: All polynomials \)f(X)F_q[X]\( of degree at most \)k-1\( such that for at least \)t\( values of \)0≤i<N\(, \[ \bigl(f(\gamma ^{mi}),\dots ,f(\gamma ^{m(i+1)-1})\bigr)=(y_{mi},\dots ,y_{m(i+1)-1}). \] \begin{enumerate} \item Compute a non-zero \end{enumerate}\)Q(X,Y_1,…,Y_s)=A_0(X)+A_1(X)Y_1++A_s(X)Y_s\( with \)(A_0)≤D+k-1\( and \)(A_i)≤D\( for \)1≤i≤s\(, such that for all \)0≤i<N\( and \)0≤j≤m-s\(, \[ Q\bigl(\gamma ^{im+j}, y_{im+j},\dots ,y_{im+j+s-1}\bigr)=0. \] \item \)L←∅\(. \item For every \)f(X)F_q[X]\( such that \)Q(X,f(X),f(γX),…,f(γ^s-1X))≡0\(: if \)(f)≤k-1\( and \)f(X)\( satisfies the agreement condition above for at least \)t\( values of \)i\(, add \)f(X)\( to \)L\(. \item Return \)L\(. \)

\(\)D≥\(, then there exists a non-zero polynomial \)Q(X,Y_1,…,Y_s)\( that satisfies Step~ 1 of Algorithm~ \ref{alg:c17-algo2}. \uses{alg:c17-algo2, lem:c17-linear-system-nonzero-solution} \begin{proof} Consider all coefficients of all polynomials \end{proof}\)A_i\( as variables. Using the same argument as in the proof of Claim~ \ref{lem:c17-claim1721} (with \)s\( instead of \)m\(), the number of variables is \[ D+k+s(D+1)=(s+1)(D+1)+k-1. \] The number of constraints (i.e.\ equations, when all coefficients of all \)A_i\( are considered variables) is \)N(m-s+1)\(, since for each \)0≤i<N\( there are \)m-s+1\( values of \)j\( giving a constraint. If we have more variables than equations, then by Lemma~ \ref{lem:c17-linear-system-nonzero-solution} there exists a non-zero \)Q\( satisfying the required properties. Thus it suffices to have \[ (s+1)(D+1)+k-1 {\gt} N(m-s+1), \] which is equivalent to \[ D {\gt} \frac{N(m-s+1)-k+1}{s+1}-1. \] The choice of \)D\( in the statement of the lemma satisfies this condition, which completes the proof. \uses{lem:c17-linear-system-nonzero-solution} \)

\(\)t> \(, then every polynomial \)f(X)\( that needs to be output (i.e.\ of degree at most \)k-1\( agreeing with the received word in at least \)t\( positions) satisfies \)Q(X,f(X),f(γX),…,f(γ^s-1X))≡0\(. \uses{alg:c17-algo2, lem:c17-degree-mantra} \begin{proof} Consider the polynomial \end{proof}\)R(X)=Q(X,f(X),f(γX),…,f(γ^s-1X))\(. Because the degree of \)f(γ^ℓX)\( (for every \)0≤ℓ≤s-1\() is at most \)k-1\(, \[ \deg (R)\le D+k-1. \] Let \)f(X)\( be one of the polynomials of degree at most \)k-1\( that needs to be output, agreeing with the received word at column \)i\( for some \)0≤i<N\(, that is \)f(γ^mi+ℓ)=y_mi+ℓ\( for \)ℓ=0,…,m-1\(. Then for all \)0≤j≤m-s\(, \[ R(\gamma ^{mi+j}) = Q\bigl(\gamma ^{mi+j}, f(\gamma ^{mi+j}),\dots ,f(\gamma ^{mi+s-1+j})\bigr) = Q\bigl(\gamma ^{mi+j}, y_{mi+j},\dots ,y_{mi+s-1+j}\bigr)=0, \] where the first equality holds because \)f(X)\( agrees with \)y\( in column \)i\(, and the second equality is the defining property of \)Q\( from Step~ 1. Thus, for each of the \)t\( (or more) agreement positions \)i\(, \)R(X)\( acquires \)m-s+1\( distinct roots, so the number of roots of \)R(X)\( is at least \[ t(m-s+1) {\gt} D+k-1 \ge \deg (R), \] where the first inequality follows from the hypothesis and the second from the degree bound above. Hence, by the degree mantra (Lemma~ \ref{lem:c17-degree-mantra}), \)R(X)≡0\(, which shows that \)f(X)\( satisfies the required identity. \uses{lem:c17-degree-mantra} \)

17.3.1 Error Correction Capability

\(\)m≥1\( and rate \)R\( up to \)1-\( fraction of errors, for any \)1≤s≤m\(. \uses{lem:c17-lem1731, lem:c17-lem1732, assumption:c17-setup} \begin{proof} To satisfy the constraint in Lemma~ \ref{lem:c17-lem1731}, we pick \[ D=\left\lfloor \frac{N(m-s+1)-k+1}{s+1}\right\rfloor . \] This, along with the constraint in Lemma~ \ref{lem:c17-lem1732}, implies that the algorithm works as long as \[ t{\gt} \left\lfloor \frac{D+k-1}{m-s+1}\right\rfloor , \] which is satisfied if \[ t{\gt} \frac{\frac{N(m-s+1)-k+1}{s+1}+k-1}{m-s+1} = \frac{N(m-s+1)-k+1+(k-1)(s+1)}{(m-s+1)(s+1)} = \frac{N(m-s+1)+s(k-1)}{(s+1)(m-s+1)}. \] Thus, we would be fine if we pick \[ t{\gt} \frac{N}{s+1}+\frac{s}{s+1}\cdot \frac{k}{m-s+1} = N\left(\frac{1}{s+1}+\left(\frac{s}{s+1}\right)\left(\frac{m}{m-s+1}\right)R\right), \] where the equality follows from \end{proof}\)k=mRN\(. Hence the algorithm succeeds whenever the number of errors \)N-t\( is at most \[ N-t = N\left(1-\frac{1}{s+1}-\frac{s}{s+1}\cdot \frac{m}{m-s+1}R\right) = \frac{s}{s+1}N\left(1-\frac{m}{m-s+1}R\right), \] i.e.\ the algorithm list decodes from up to \)1-\( fraction of errors. \uses{lem:c17-lem1731, lem:c17-lem1732} \)

17.3.2 Bounding the Output List Size

We now bound the output list size in the root finding step of Algorithm 397. We show that there are at most \(\)q^s-1\( possible solutions for the root finding step. Throughout, write the interpolation polynomial as \)Q(X,Y_1,…,Y_s)=A_0(X)+A_1(X)Y_1++A_s(X)Y_s\(, and think of the coefficients \)f_0,…,f_k-1\( of a candidate output polynomial \)f(X)=∑_i=0^k-1f_iX^i\( as unknowns satisfying \[ A_0(X)+A_1(X)f(X)+A_2(X)f(\gamma X)+\cdots +A_s(X)f(\gamma ^{s-1}X)\equiv 0. \] \begin{thmenv}[Claim 17.3.5] \label{lem:c17-claim1735} Write \end{thmenv} \)A_i(X)=∑_j=0^D+k-1a_ijX^j\( for \)0≤i≤s\(, and let \[ B(X)=a_{1,0}+a_{2,0}X+a_{3,0}X^2+\cdots +a_{s,0}X^{s-1} \] be a non-zero polynomial of degree at most \)s-1\(. For every \)0≤j≤k-1\(: \begin{itemize} \item if \end{itemize}\)B(γ^j)≠0\(, then \)f_j\( is uniquely determined by \)f_j-1,f_j-2,…,f_0\(; \item if \)B(γ^j)=0\(, then \)f_j\( is unconstrained, i.e.\ \)f_j\( can take any of the \)q\( values in \)F_q\(. \)

\(\)C(X)=A_0(X)+A_1(X)f(X)++A_s(X)f(γ^s-1X)\(; recall \)C(X)≡0\(. Expanding out each polynomial multiplication, \begin{align*} C(X) & = a_{0,0}+a_{0,1}X+\cdots +a_{0,D+k-1}X^{D+k-1}\\ & \quad + \bigl(a_{1,0}+a_{1,1}X+\cdots +a_{1,D+k-1}X^{D+k-1}\bigr) \bigl(f_0+f_1X+\cdots +f_{k-1}X^{k-1}\bigr)\\ & \quad + \bigl(a_{2,0}+a_{2,1}X+\cdots +a_{2,D+k-1}X^{D+k-1}\bigr) \bigl(f_0+f_1\gamma X+\cdots +f_{k-1}\gamma ^{k-1}X^{k-1}\bigr)\\ & \quad \; \; \vdots \\ & \quad + \bigl(a_{s,0}+a_{s,1}X+\cdots +a_{s,D+k-1}X^{D+k-1}\bigr) \bigl(f_0+f_1\gamma ^{s-1}X+\cdots +f_{k-1}\gamma ^{(k-1)(s-1)}X^{k-1}\bigr). \end{align*} Collecting terms of the same degree, \)C(X)=c_0+c_1X++c_D+k-1X^D+k-1\(, and we seek solutions with \)c_j=0\( for every \)0≤j≤D+k-1\(; we only need the equations for \)0≤j≤k-1\(. These give \)D+k\( linear equations in the variables \)f_0,…,f_k-1\(. For \)j=0\(: \)c_0=0\( gives \)0=a_0,0+f_0∑_l=1^s a_l,0 = a_0,0+f_0 B(1)\(. \begin{itemize} \item If \end{itemize}\)B(1)≠0\(: \)f_0 = -a_0,0/B(1)\( is fixed. \item If \)B(1)=0\(: \)f_0\( is unconstrained. \)

For \(\)j=1\(: \)c_1=0\( gives, after simplification, \)0=a_0,1+f_1 B(γ) + f_0  b_0^(1)\(, where \)b_0^(1)=∑_l=1^s a_l,1\( is a constant. \begin{itemize} \item If \end{itemize}\)B(γ)≠0\(: \)f_1=\( is uniquely determined given \)f_0\(. \item If \)B(γ)=0\(: \)f_1\( is unconstrained. \)

In general, for arbitrary \(\)j\(, \)c_j=0\( gives \[ 0 = a_{0,j} + f_j B(\gamma ^j) + \sum _{l=0}^{j-1} f_l\, b_l^{(j)}, \] where \)b_l^(j)=∑_i=1^s a_i,j-l·γ^l(i-1)\( are constants determined by the coefficients of the \)A_i(X)\('s and \)γ\(. \begin{itemize} \item If \end{itemize}\)B(γ^j)≠0\(: then \[ f_j = \frac{-a_{0,j}-\sum _{l=0}^{j-1} f_l\, b_l^{(j)}}{B(\gamma ^j)} \] is uniquely determined given \)f_0,…,f_j-1\(. \item If \)B(γ^j)=0\(: \)f_j\( is unconstrained. \)

This completes the proof.

\(\)q^s-1\( solutions to \)f_0,f_1,…,f_k-1\( (where \)f(X)=f_0+f_1X++f_k-1X^k-1\() to the equation \[ A_0(X)+A_1(X)f(X)+A_2(X)f(\gamma X)+\cdots +A_s(X)f(\gamma ^{s-1}X)\equiv 0. \] \uses{lem:c17-claim1735, lem:c17-degree-mantra, assumption:c17-setup} \begin{proof} First assume \end{proof}\)X\( does not divide all of the polynomials \)A_0,A_1,…,A_s\(. Then there exists \)i^*>0\( such that the constant term of \)A_i^*(X)\( is non-zero. (Otherwise, since \)X∣A_1(X),…,A_s(X)\(, the defining equation forces \)X∣A_0(X)\( as well, contradicting the assumption that \)X\( does not divide all of the \)A_i(X)\(.) Define \)a_ij\( so that \)A_i(X)=∑_j=0^D+k-1a_ijX^j\( for every \)0≤i≤s\(, and \)B(X)=a_1,0+a_2,0X++a_s,0X^s-1\(. Since \)a_i^*,0≠0\(, \)B(X)\( is a non-zero polynomial of degree at most \)s-1\(, and by the degree mantra (Lemma~ \ref{lem:c17-degree-mantra}), \)B(X)\( has at most \)s-1\( roots. By Claim~ \ref{lem:c17-claim1735}, for every \)0≤j≤k-1\(, \)f_j\( is either uniquely determined by \)f_0,…,f_j-1\( (if \)B(γ^j)≠0\() or unconstrained (if \)B(γ^j)=0\(). Since \)γ\( generates \)F_q^*\( and \)k-1≤q-2\(, the elements \)1,γ,…,γ^k-1\( are distinct, so by the degree mantra at most \)s-1\( of them are roots of \)B(X)\(, i.e.\ at most \)s-1\( of the variables \)f_0,…,f_k-1\( are unconstrained. Building a decision tree with \)f_0\( at the root and \)f_j\( at level \)j\( (where each internal node at level \)j\( has a single child if \)B(γ^j)≠0\(, and \)q\( children if \)B(γ^j)=0\(), the number of solutions to \)f_0,…,f_k-1\( is upper bounded by the number of nodes at level \)k\(, which is at most \)q^s-1\(, since at most \)s-1\( of the levels branch. Finally, we remove the assumption that \)X\( does not divide every \)A_i\(. Let \)ℓ≥0\( be the largest integer such that \)A_i(X)=X^ℓA_i’(X)\( for \)0≤i≤s\(; then \)X\( does not divide all of \)A_0’(X),…,A_s’(X)\(, and \[ X^\ell \bigl(A_0'(X)+A_1'(X)f(X)+\cdots +A_s'(X)f(\gamma ^{s-1}X)\bigr)\equiv 0. \] Since \)X^ℓ≠0\( as a polynomial, \)A_0’(X)+A_1’(X)f(X)++A_s’(X)f(γ^s-1X)≡0\( as well, so the entire argument above applies with \)A_i’(X)\( in place of \)A_i(X)\(, giving the same bound of \)q^s-1\(. \uses{lem:c17-claim1735, lem:c17-degree-mantra} \)

\(\){M·x+z∣xF_q^d}\( for some \)0≤d≤s-1\( and \)MF_q^k×d\(, \)zF_q^k\(. Further, \)M\( and \)z\( can be computed from the polynomials \)A_0(X),…,A_s(X)\( with \)O(ss  k^2)\( operations over \)F_q\(. \uses{lem:c17-lem1734, lem:c17-claim1735} \begin{proof} By Claim~ \ref{lem:c17-claim1735}, computing all tuples \end{proof}\)(f_0,…,f_k-1)\( satisfying the identity amounts to solving, for \)j=0,…,k-1\(, the recursively defined linear equations \[ 0 = a_{0,j} + f_j B(\gamma ^j) + \sum _{l=0}^{j-1} f_l\, b_l^{(j)}. \] This is a \)k×k\( upper-triangular linear system \)C·(f_0,…,f_k-1)^T = (-a_0,0,-a_0,1,…,-a_0,k-1)^T\(, where each entry of \)C\( is either \)0\(, \)B(γ^j)\(, or \)b_l^(j)\(; each such entry can be computed in \)O(ss)\( operations over \)F_q\( (using fast multi-point evaluation of the coefficients of the \)A_i\('s), so the system can be set up in \)O(ss  k^2)\( operations. Let \)0≤d≤s-1\( be the number of roots of \)B(X)\( in \){1,γ,…, γ^k-1}\( (bounded by the degree mantra, Lemma~ \ref{lem:c17-degree-mantra}). There are exactly \)d\( unconstrained variables among \)f_0,…,f_k-1\(, namely those indices \)j\( with \)B(γ^j)=0\(. Since \)C\( is upper triangular, all remaining (constrained) variables are affine-linear functions of the \)d\( unconstrained ones, obtained by back-substitution; hence every solution lies in a set of the form \){M·x+z∣xF_q^d}\( for a suitable \)k×d\( matrix \)M\( and vector \)zF_q^k\(, and since \)C\( is upper triangular, \)M\( and \)z\( can both be computed from the entries of \)C\( with \)O(k^2)\( further operations over \)F_q\(. \uses{lem:c17-lem1734, lem:c17-degree-mantra} \)

17.3.3 Algorithm Implementation and Runtime Analysis

\(\)A_0(X),…,A_s(X)\(. \textsc{Output}: All polynomials \)f(X)\( of degree at most \)k-1\( satisfying \)A_0(X)+A_1(X)f(X)++A_s(X)f(γ^s-1X)≡0\(. \begin{enumerate} \item Compute \end{enumerate}\)ℓ\( such that \)X^ℓ\( is the largest common power of \)X\( among \)A_0(X),…,A_s(X)\(. \item For every \)0≤i≤s\(: \)A_i(X)←A_i(X)/X^ℓ\(. \item Compute \)B(X)=a_1,0+a_2,0X++a_s,0X^s-1\(. \item Compute \)d\(, \)z\( and \)M\( such that the solutions to the \)k\( linear equations of Claim~ \ref{lem:c17-claim1735} lie in \){M·x+z∣xF_q^d}\(. \item \)L←∅\(. \item For every \)xF_q^d\(: set \)(f_0,…,f_k-1)←M·x+z\( and \)f(X)←∑_i=0^k-1f_iX^i\(; if \)f(X)\( satisfies the defining equation, add \)f(X)\( to \)L\(. \item Return \)L\(. \)

\(\)O(ss (Nm)^2)\( operations over \)F_q\(, Algorithm~ \ref{alg:c17-algo3} can return an affine subspace of dimension \)s-1\( that contains all the polynomials of degree at most \)k-1\( that need to be output. Further, the exact set of solutions can be computed with additional \)O(q^s-1·(Nm)^2)\( operations over \)F_q\(. \uses{alg:c17-algo3, cor:c17-cor1736} \begin{proof} Throughout we assume all polynomials are represented in their standard coefficient form. Step~ 1 of Algorithm~ \ref{alg:c17-algo3} involves finding the smallest power of \end{proof}\)X\( with a non-zero coefficient in each \)A_i(X)\(, which can be done with \)O(D+k+s(D+1))=O(Nm)\( operations over \)F_q\( (using \)D=O(N)\( and \)k≤N·m\(). Given \)ℓ\(, Step~ 2 shifts all coefficients in each \)A_i(X)\( by \)ℓ\(, which can also be done with \)O(Nm)\( operations. For the root finding step, if one is satisfied with a succinct description of a set of possible solutions that contains the actual output, then by Corollary~ \ref{cor:c17-cor1736} Steps~ 3–4 (halting after Step~ 4) can be implemented in \)O(ss  k^2)=O(ss (Nm)^2)\( operations over \)F_q\( (using \)k≤Nm\(). If instead one wants the exact set of solutions, then Steps 5--7 check all \)q^s-1\( potential solutions from the affine subspace of Corollary~ \ref{cor:c17-cor1736}, each check costing \)O((Nm)^2)\( operations, for a total additional \)O(q^s-1·(Nm)^2)\( operations over \)F_q\(. \uses{cor:c17-cor1736} \)

17.3.4 Wrapping Up

\(\)R\( that, for large enough block length \)N\(, can be list decoded from \)1-R-ε\( fraction of errors (for any small enough \)ε>0\() in time \)^O(1/ε)\(. The worst-case list size is \)^O(1/ε)\( and the alphabet size is \)^O(1/ε^2)\(. \uses{thm:c17-thm1733, lem:c17-lem1737, def:c05-reed-solomon, def:c07-ld-capacity} \begin{proof} By Theorem~ \ref{thm:c17-thm1733}, we can list decode a Folded Reed-Solomon code with folding parameter \end{proof}\)m≥1\( up to \[ \frac{s}{s+1}\cdot \left(1-\frac{m}{m-s+1}\cdot R\right) \] fraction of errors, for any \)1≤s≤m\(. To obtain the desired bound \)1-R-ε\( fraction of errors, we instantiate the parameters \)s\( and \)m\( so that \[ \frac{s}{s+1}\ge 1-\varepsilon \qquad \text{and}\qquad \frac{m}{m-s+1}\le 1+\varepsilon . \] It is easy to check that one can choose \)s=Θ(1/ε)\( and \)m=Θ(1/ε^2)\( so that both bounds are satisfied. Using these bounds, the algorithm can handle at least \[ (1-\varepsilon )\bigl(1-(1+\varepsilon )R\bigr) = 1-\varepsilon -R+\varepsilon ^2 R {\gt} 1-R-\varepsilon \] fraction of errors, as desired. By Lemma~ \ref{lem:c17-lem1737}, the run time of the algorithm (to output the exact list) is \)q^O(s)·poly(N,m)\(. We choose \)q\( to be the smallest power of \)2\( larger than \)Nm+1\(; then \)q=Θ(Nm)=Θ(N/ε^2)\(. This yields: \begin{itemize} \item run time \end{itemize}\)q^O(s) = (N/ε^2)^O(1/ε) = (N/ε)^O(1/ε)\(; \item worst-case list size \)q^s-1 = (N/ε^2)^O(1/ε) = (N/ε)^O(1/ε)\(; \item alphabet size \)q^m = (N/ε^2)^Θ(1/ε^2) = (N/ε)^O(1/ε^2)\(. \)

Finally, the resulting Folded Reed-Solomon codes are strongly explicit because the underlying Reed-Solomon codes are strongly explicit and folding (Definition 389) is an explicitly computable transformation on codewords.

This answers, for constant \(\)ε\(, the question posed at the start of the chapter: there exist explicit codes of rate \)R>0\( that can be list-decoded in polynomial time from \)1-R-ε\( fraction of errors for \)q≤poly(n)\(. \)