Authors John Y. Kim, Swastik Kopparty,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38
www.theoryofcomputing.org
S PECIAL ISSUE : CCC 2016
Decoding Reed–Muller Codes
over Product Sets
John Y. Kim∗ Swastik Kopparty†
Received June 22, 2016; Revised November 21, 2017; Published December 31, 2017
Abstract: We give a polynomial-time algorithm to decode multivariate polynomial codes
of degree d up to half their minimum distance, when the evaluation points are an arbitrary
product set Sm , for every d < |S|. Previously known algorithms could achieve this only
if the set S had some very special algebraic structure, or if the degree d was significantly
smaller than |S|. We also give a near-linear-time randomized algorithm, based on tools from
list-decoding, to decode these codes from nearly half their minimum distance, provided
d < (1 − ε)|S| for constant ε > 0.
Our result gives an m-dimensional generalization of the well-known decoding algorithms
for Reed–Solomon codes, and can be viewed as giving an algorithmic version of the Schwartz–
Zippel lemma.
ACM Classification: E.4, I.1.2
AMS Classification: 11T71, 94B35, 68W30
Key words and phrases: error-correcting codes, Reed–Muller codes, algebraic algorithms, Schwartz–
Zippel lemma
1 Introduction
Error-correcting codes based on polynomials have played an important role throughout the history
of coding theory. The mathematical phenomenon underlying these codes is that distinct low-degree
A conference version of this paper appeared in the Proceedings of the 31st Conference on Computational Complexity,
2016 [9].
∗ Research supported by the National Science Foundation Graduate Research Fellowship under Grant No. DGE-1433187.
† Research supported in part by a Sloan Fellowship and NSF grants CCF-1253886 and CCF-1540634.
© 2017 John Y. Kim and Swastik Kopparty
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2017.v011a021
J OHN Y. K IM AND S WASTIK KOPPARTY
polynomials have different evaluations at many points. More recently, polynomial-based error-correcting
codes have had a big impact on complexity theory, exploiting the intimate relation between polynomials
and computation. Notable applications include PCPs, interactive proofs, polynomial identity testing and
property testing.
Our main result is a decoding algorithm for multivariate polynomial codes over product sets. Let F
be a field, S ⊆ F, d < |S| and m ≥ 1. Let F[X1 , . . . , Xm ] denote the ring of m-variate polynomials with
coefficients in F. Let deg(P) denote the total degree of the polynomial P. Consider the code of all
m-variate polynomials of total degree at most d, evaluated at all points of Sm :
C = {hP(a)ia∈Sm | P(X1 , . . . , Xm ) ∈ F[X1 , . . . , Xm ], deg(P) ≤ d}.
When m = 1, this code is known as the Reed–Solomon code [18], and for m > 1 this code is a Reed–
Muller code [14, 17]. The family of Reed–Muller codes also includes polynomial evaluation codes where
the total degree d is larger than |S|, and the individual degree is capped to be at most |S| − 1. We do not
consider the d ≥ |S| case in this paper.
m
The code C above is a subset of FS , which we view as the space of functions from Sm to F. Given
two functions f , g : Sm → F, we define their (Hamming) distance ∆( f , g) = |{a ∈ Sm | f (a) 6= g(a)}|. To
understand the error-correcting properties of C, we recall the following well-known lemma, often called
the Schwartz–Zippel lemma.
Lemma 1.1. Let F be a field, and let P(X1 , . . . , Xm ) be a nonzero polynomial over F with degree at most
d. Then for every S ⊆ F,
d
Prm [P(a) = 0] ≤ .
a∈S |S|
This lemma implies that for any two polynomials P, Q of degree at most d,
d
∆(P, Q) ≥ 1 − |S|m .
|S|
In other words the minimum distance of C is at least (1 − d/|S|)|S|m . It turns out that the minimum
distance of C is in fact exactly (1 − d/|S|)|S|m , and we let ∆C denote this quantity.
For error-correcting purposes, if we are given a “received word” r : Sm → F such that there exists a
polynomial P of degree at most d with ∆(r, P) ≤ ∆C /2, then we know that there is a unique such P. The
problem that we consider in this paper, “decoding C up to half its minimum distance,” is the algorithmic
task of finding this P.
1.1 Our results
There is a rich history with several deep algebraic ideas surrounding the problem of decoding multivariate
polynomial codes. We first state our main results, and then discuss their relationship to various other
known results.
Theorem 1.2 (Efficient decoding of multivariate polynomial codes up to half their minimum distance).
Let F be a finite field, let S, d, m be as above. Let N = nm be the length of the corresponding Reed–Muller
code, and let ∆C = (1 − d/|S|)N be its minimum distance.
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 2
D ECODING R EED –M ULLER C ODES OVER P RODUCT S ETS
There is an algorithm, which when given as input a function r : Sm → F, runs in time poly(N, log |F|)
and finds the polynomial P(X1 , . . . , Xm ) ∈ F[X1 , . . . , Xm ] of degree at most d (if any) such that:
∆(r, P) < ∆C /2 .
As we will discuss below, previously known efficient decoding algorithms for these codes only
worked for either (1) very algebraically special sets S, or (2) very low degrees d, or (3) decoded from a
much smaller number of errors (≈ (1/(m + 1))∆C instead of (1/2)∆C ).
Using several further ideas, we also show how to implement the above algorithm in near-linear time
to decode up to almost half the minimum distance, provided d is not (1 − o(1))|S|.
Theorem 1.3 (Near-linear-time decoding). Let F be a finite field, let S, d, m be as above. Let N = nm be
the length of the corresponding Reed–Muller code, and let
d
∆C = 1 − N
|S|
be its minimum distance. Let δC = (1 − d/|S|). Assume δC > 0, and m are constants.
There is a randomized algorithm, which when given as input a function r : Sm → F, runs in time
N · poly(log(N), log(|F|)) and finds the polynomial P(X1 , . . . , Xm ) ∈ F[X1 , . . . , Xm ] of degree at most d (if
any) with:
1
∆(r, P) < 1 − Θ √ · ∆C /2 .
n
Over the rational numbers, we get a version of Theorem 1.2 where the running time is poly(|S|m ,t),
where t is the maximum bit-complexity of any point in S or in the image of r. This enables us to decode
multivariate polynomial codes up to half the minimum distance in the natural special case where the
evaluation set S equals {1, 2, . . . , n}.
We also mention that decoding Reed–Muller codes over an arbitrary product set Sm appears as a
subroutine in the local decoding algorithm for multiplicity codes [11] (see Section 4 on “Solving the noisy
system”). Our results allow the local decoding algorithms there to run efficiently over all fields ([11]
could only do this over fields of small characteristic, where algebraically special sets S are available).
1.2 Related work
There have been many works studying the decoding of multivariate polynomial codes, which prove (and
improve) various special cases of our main theorem.
Reed–Solomon codes (m = 1). When m = 1, our problem is also known as the problem of decoding
Reed–Solomon codes up to half their minimum distance. That this problem can be solved efficiently (and
further, in near-linear time) is very classical, and a number of algorithms are known for this (Peterson [16],
Berlekamp-Massey [13], Berlekamp-Welch [21], see also [12]). The underlying algorithmic ideas have
subsequently had a tremendous impact on algebraic algorithms.
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 3
J OHN Y. K IM AND S WASTIK KOPPARTY
For Reed–Solomon codes, it is in fact known how to list-decode beyond half the minimum distance,
up to the “Johnson radius” r !
∆C
1− 1− N,
N
by the important Guruswami-Sudan [5] algorithm. This has had numerous further applications in coding
theory, complexity theory and pseudorandomness.
Special sets. For very special sets S, it turns out that there are some algebraic ways to reduce the
decoding of multivariate polynomial codes over Sm to the decoding of univariate polynomial codes. This
kind of reduction is possible when F is a finite field Fq and S equals the whole field Fq , or more generally
when S equals an affine subspace over the prime subfield of Fq .
When S = Fq , then Sm = Fm m
q and S can then be identified with the large field Fqm in a natural Fq -linear
way (this understanding of Reed–Muller codes was discovered by [8]). This converts the multivariate
setting into univariate setting, identifies the multivariate polynomial code as a subcode of the univariate
polynomial code, and (somewhat miraculously), the minimum distance of the univariate polynomial code
equals the minimum distance of the multivariate polynomial code. Thus the classical Reed–Solomon
decoding algorithms can then be used, and this leads to an algorithm for the multivariate setting decoding
up to half the minimum distance. In fact, Pellikaan-Wu [15] observed that this connection allows one to
decode multivariate polynomial codes beyond half the minimum distance too, provided S is special in the
above sense.
Another approach which works in the case of S = Fq is based on local decoding [2]. Here we use
the fact that Sm = Fmq contains many lines (not just the axis-parallel ones), and then use the univariate
decoding algorithms to decode on those lines from
1 − dq
N
2
errors. This approach manages to decode multivariate polynomial codes with S = Fq from (1/2 − o(1))
of the minimum distance. Again, this approach does not work for general S, since a general Sm usually
contains only axis-parallel lines (while Fm
q has many more lines).
Low degree. When the degree d of the multivariate polynomial code is significantly smaller than |S|,
then a number of other list-decoding based methods come into play.
The powerful Reed–Muller list-decoding algorithm of Sudan [20] and its multiplicity-based general-
ization, based on (m + 1)-variate interpolation and root-finding, can decode from
m+1 1 !
d
1− N
|S|
errors. With small degree d = o(|S|) and m = O(1), this decoding radius equals (1 − o(1))N! However
when d is much larger (say 0.9 · |S|), then the number of errors decodable by this algorithm is around
1 d 1
· 1− N= · ∆C .
m+1 |S| m+1
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 4
D ECODING R EED –M ULLER C ODES OVER P RODUCT S ETS
Another approach comes from the list-decoding of tensor codes [4]. While the multivariate polynomial
codes we are interested in are not tensor codes, they are subcodes of the code of polynomials with
individual degree at most d. Using the algorithm of [4] for decoding tensor codes, we get an algorithm
that can decode from a (1 − o(1))N errors when d = o(|S|), but fails to approach a constant fraction of
the minimum distance when d approaches |S|.
In light of all the above, to the best of our knowledge, for multivariate polynomial codes with
d > 0.9 · |S| (i. e., with ∆C < (0.1)N), and S generic, the largest number of errors which could be corrected
efficiently was about (1/(m + 1))∆C . In particular, the correctable number of errors is a vanishing fraction
of the minimum distance, as the number of variables m grows.
We thus believe it is worthwhile to investigate this problem, not only because of its basic nature, but
also because of the many different powerful algebraic ideas that only give partial results towards it.
1.3 Overview of the decoding algorithm
We now give a brief overview of our decoding algorithms. Let us first discuss the bivariate (m = 2) case.
Here we are given a received word r : S2 → F such that there exists a codeword P(X,Y ) ∈ F[X,Y ] of
degree at most d = (1 − δC )|S| with
δC
∆(P, r) < · |S|2 .
2
Our goal is to find P(X,Y ).
First some high-level strategy. An important role in our algorithm is played by the following
observation: the restriction of a degree ≤ d bivariate polynomial P(X,Y ) to a vertical line (fixing X = α)
or a horizontal line (fixing Y = β ) gives a degree ≤ d univariate polynomial. Perhaps an even more
important role is played by the following disclaimer: the previous observation does not characterize
bivariate polynomials of degree d! The set of functions f : S2 → F for which the horizontal restrictions
and vertical restrictions are polynomials of degree ≤ d is the code of polynomials with individual degree
at most d (this is the tensor Reed–Solomon code, with much smaller distance than the Reed–Muller code).
For such a function f to be in the Reed–Muller code, the different univariate polynomials that appear as
horizontal and vertical restrictions must be related in some way. The crux of our algorithm is to exploit
these relations.
It will also help to recap the standard algorithm to decode tensor Reed–Solomon codes up to half their
minimum distance. (This scheme, known as Forney’s Generalized Minimum Distance (GMD) decoding
algorithm [7], actually works for general tensor codes.) Suppose we are given a received word r : S2 → F,
and we want to find a polynomial P(X,Y ) with individual degrees at most d which is close to r. One
first decodes, for every α ∈ S, the row r(α, ·) to the nearest univariate polynomial of degree ≤ d. One
then takes the columns of this new received word (after having corrected the rows) and decodes each
of them to the nearest degree ≤ d polynomial. As stated, this strategy only allows one to decode from
1/4 the minimum distance. To go up to 1/2 the minimum distance, the key point is to pass some “soft
information” from the row decodings to the column decodings; the rows which were decoded from more
errors are treated with lower confidence. This decodes the tensor Reed–Solomon code from 1/2 the
minimum distance fraction errors. Several ingredients from this algorithm will appear in our Reed–Muller
decoding algorithm.
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 5
J OHN Y. K IM AND S WASTIK KOPPARTY
Now we return to the problem of decoding Reed–Muller codes. Let us write P(X,Y ) as a single
variable polynomial in Y with coefficients in F[X]:
d
P(X,Y ) = ∑ Pi (X)Y d−i ,
i=0
where deg(Pi ) ≤ i. For each α ∈ S, consider the restricted univariate polynomial P(α,Y ). Since deg(P0 ) =
0, P0 (α) must be the same for each α. Thus all the polynomials hP(α,Y )iα∈S have the same coefficient
for Y d . Similarly, the coefficients of Y d−i in the polynomials hP(α,Y )iα∈S fit a degree i polynomial.
As in the tensor Reed–Solomon case, our algorithm begins by decoding each row r(α, ·) to the nearest
degree ≤ d univariate polynomial. Now, instead of trying to use these decoded row polynomials to
recover P(X,Y ) in one shot, we aim lower and just try to recover P0 (X). The advantage is that P0 (X) is
only a degree 0 polynomial, and is thus resilient to many more errors than a degree d polynomial. Armed
with P0 (X), we then proceed to find P1 (X). The knowledge of P0 (X) allows us to decode the rows r(α, ·)
to a slightly larger radius; in turn this improved radius allows us to recover the degree 1 polynomial
P1 (X). At the ith stage, we have already recovered P0 (X), P1 (X), . . . , Pi−1 (X). Consider, for each α ∈ S,
the function
i−1
fα (Y ) = r(α,Y ) − ∑ Pj (α)Y d− j .
j=0
Our algorithm decodes fα (Y ) to the nearest degree d − i polynomial: note that as i increases, we are
decoding to a lower degree polynomial, and hence we are able to handle a larger fraction of errors. Define
h(α) to be the coefficient of Y d−i in the polynomial so obtained; this “should” equal the evaluation of
the degree i polynomial Pi (α). So we next decode h(α) to the nearest degree i polynomial (using the
appropriate soft information), and it turns out that this decoded polynomial must equal Pi (X). By the time
i reaches d, we would have recovered P0 (X), P1 (X), . . . , Pd (X), and hence all of P(X,Y ). Summarizing,
the algorithm repeatedly decodes the rows r(α, ·), and at each stage it uses the relationship between the
different univariate polynomial P(α,Y ) to: (1) learn a little bit more about the polynomial P(X,Y ), and
(2) increase the radius to which we can decode r(α, ·) in the next stage. This completes the description of
the algorithm in the m = 2 case.
The case of general m is very similar, with only a small augmentation needed. Decoding m-variate
polynomials turns out to reduce to decoding m − 1-variate polynomials with soft information; thus in
order to make a sustainable recursive algorithm, we aim a little higher and instead solve the more general
problem of decoding multivariate polynomial codes with uncertainties (where each coordinate of the
received word has an associated “confidence” level).
To implement the above algorithms in near-linear time, we use some tools from list-decoding. The
main bottleneck in the running time is the requirement of having to decode the same row r(α, ·) multiple
times to larger and larger radii (to lower and lower degree polynomials). To save on these decodings,
we instead list-decode r(α, ·) to a large radius using a near-linear-time list-decoder for Reed–Solomon
codes; this reduces the number of required decodings of the same row from d to O(1) (provided
d < (1 − Ω(1))|S|). For the m = 2 case this works fine, but for m > 2 case this faces a serious obstacle;
in general it is impossible to efficiently list-decode Reed–Solomon codes with uncertainties beyond half
the minimum distance of the code (the list size can be superpolynomial). We get around this using some
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 6
D ECODING R EED –M ULLER C ODES OVER P RODUCT S ETS
technical ideas, based on speeding-up the decoding of Reed–Muller codes with uncertainties when the
fraction of errors is significantly smaller than half the minimum distance. For details, see Section 6.
1.4 Organization of this paper
In Section 2, we cover the notion of weighted distance, which will be used in handling Reed–Solomon
and Reed–Muller decoding with soft information on the reliability of the symbols in the encoding. In
Section 3, we give a polynomial-time algorithm for decoding bivariate Reed–Muller codes to half the
minimum distance. We then generalize the algorithm to decode multivariate Reed–Muller codes in
Section 4. In Section 5 and Section 6, we show that decoding Reed–Muller codes to almost half the
minimum distance can be done in near-linear time by improving on the algorithms in Section 3 and
Section 4. We conclude with some open problems.
2 Preliminaries
2.1 Weighted functions
At various stages of the decoding algorithm, we will need to deal with symbols and received words in
which we have varying amounts of confidence. We now introduce some language to deal with such
notions.
Let Σ denote an alphabet. A weighted symbol of Σ is simply an element of Σ × [0, 1]. In the weighted
symbol (σ , u), we will be thinking of u ∈ [0, 1] as our uncertainty that σ is the symbol we should be
talking about. Thus u = 0 represents absolute certainty about σ , while u = 1 represents having no
confidence at all in the symbol σ .
For a weighted symbol (σ , u) and a symbol σ 0 , we define their distance ∆((σ , u), σ 0 ) by
(
0 1 − u/2 if σ 6= σ 0 ,
∆((σ , u), σ ) =
u/2 if σ = σ 0 .
For a weighted function w : T → Σ × [0, 1], and a (conventional) function f : T → Σ, we define their
Hamming distance by
∆(w, f ) = ∑ ∆(w(t), f (t)) .
t∈T
The key inequality here is the triangle inequality.
Lemma 2.1 (Triangle inequality for weighted functions). Let f , g : T → Σ be functions, and let w : T →
Σ × [0, 1] be a weighted function. Then:
∆(w, f ) + ∆(w, g) ≥ ∆( f , g) .
Proof. We will show that if t ∈ T is such that f (t) 6= g(t), then ∆(w(t), f (t)) + ∆(w(t), g(t)) ≥ 1. This
will clearly suffice to prove the lemma.
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 7
J OHN Y. K IM AND S WASTIK KOPPARTY
Let w(t) = (σ , u). Suppose f (t) = σ1 and g(t) = σ2 . Then either σ 6= σ1 or σ 6= σ2 , or both. Thus
either we have
∆(w(t), f (t)) + ∆(w(t), g(t)) = (1 − u/2) + u/2 ,
or we have
∆(w(t), f (t)) + ∆(w(t), g(t)) = u/2 + (1 − u/2) ,
or we have
∆(w(t), f (t)) + ∆(w(t), g(t)) = (1 − u/2) + (1 − u/2) .
In all cases, we have ∆(w(t), f (t)) + ∆(w(t), g(t)) ≥ 1, as desired.
The crucial property that this implies is the unique decodability up to half the minimum distance of a
code for weighted received words.
Lemma 2.2. Let C ⊆ ΣT be a code with minimum distance ∆. Let w : T → Σ × [0, 1] be a weighted
function. Then there is at most one f ∈ C satisfying
∆(w, f ) < ∆/2 .
2.2 Algorithms for decoding Reed–Solomon codes
We will need to use several known algorithms for decoding Reed–Solomon codes. We list these below:
• Fast Reed–Solomon decoding FastRSDecoder: Given a received word r : S → Fq and an integer
d < |S|, the algorithm FastRSDecoder runs in time O(|S| poly(log |S|, log q)) and finds the unique
polynomial P(X) (if any) of degree at most d such that ∆(P, r) < (|S| − d)/2.
There are many classical algorithms known for this, see [12].
• Weighted Reed–Solomon decoding WeightedRSDecoder: Given a weighted received word
w : S → Fq × [0, 1] and an integer d < |S|, the algorithm WeightedRSDecoder runs in time
O(|S|2 poly(log |S|, log q)) and finds the unique polynomial P(X) (if any) of degree at most d
such that ∆(P, w) < (|S| − d)/2.
This algorithm, due to Forney [7], is via a reduction to standard Reed–Solomon decoding, and is an
important part of Forney’s Generalized Minimum Distance decoding algorithm. For completeness,
we describe it in the appendix.
• Fast weighted Reed–Solomon decoding FastWeightedRSDecoder: Given a weighted received
word w : S → Fq ×[0, 1] and an integer d < |S|, the randomized algorithm FastWeightedRSDecoder
runs in time O(|S| poly(log |S|, log q, log 1/γ)) and finds (with probability at least 1 − γ) the unique
polynomial P(X) (if any) of degree at most d such that
10
∆(P, w) < (|S| − d)/2 − p .
|S|
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 8
D ECODING R EED –M ULLER C ODES OVER P RODUCT S ETS
This algorithm is a randomized variant of Forney’s algorithm WeightedRSDecoder. The above
performance guarantee is folklore, and follows from a simple second moment analysis. For
completeness, we describe it in the appendix.
• Fast Reed–Solomon list-decoding FastRSListDecoder: Given a received word r : S → Fq , an
integer d < |S|, and a distance parameter Λ satisfying:
p
Λ < |S| − d|S| + ε|S| ,
the algorithm FastRSListDecoder runs in time O(|S| poly(log |S|, log q, 1/ε)) and finds all polyno-
mials P(X) of degree at most d such that ∆(P, r) < Λ. The Johnson bound further guarantees that
there are at most poly(1/ε) such P(X).
This algorithm, which is a fast implementation of the fundamental Guruswami-Sudan algorithm [20,
5] for list-decoding Reed–Solomon codes, is due to Alekhnovich [1] (building on Roth and
Ruckenstein [19]).
For the first three algorithms mentioned above, we assume that if no such polynomial exists, then the
algorithm returns a special error symbol ⊥.
3 Bivariate Reed–Muller decoding
In this section, we give an algorithm for decoding bivariate Reed–Muller codes to half their minimum
distance. Let F be a finite field, S ⊆ F with |S| = n, and let d < n. We are given a received word
r : S2 → F. Suppose that there is a codeword C ∈ F[X,Y ] with deg(C) ≤ d, whose distance ∆(r,C) from
the received word is at most half the minimum distance n(n − d)/2. The following result says that there
is a polynomial-time algorithm to find C.
Theorem 3.1. Let F be a finite field and let S ⊆ F be a nonempty subset of size |S| = n.
There is a O(n3 polylog(n, |F|))-time algorithm, which given a received word r : S2 → F, finds the
unique polynomial (if any) C ∈ F[X,Y ] with deg(C) ≤ d such that
1 d
∆(r,C) < 1− n2 .
2 n
The algorithm is given in Algorithm 1.
3.1 Outline of algorithm
The general idea of the algorithm is to write
d
C(X,Y ) = ∑ Pi (X)Y d−i ∈ F[X][Y ]
i=0
as a polynomial in Y with coefficients as polynomials in F[X], and attempt to uncover the coefficients
Pi (X) one at a time.
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 9
J OHN Y. K IM AND S WASTIK KOPPARTY
We outline the first iteration of the algorithm, which uncovers the coefficient P0 (X) of degree 0. View
the encoded message as a matrix on S × S, where the rows are indexed by x ∈ S and the columns by
y ∈ S. We first Reed–Solomon decode the rows r(x,Y ), x ∈ S to half the minimum distance (n − d)/2
and get the polynomial Gx (Y ). We then extract the coefficient, CoeffY d (Gx ), of Y d from the polynomial
Gx (Y ). This gives us guesses for what P0 (x) is for x ∈ S. However, this isn’t quite enough to determine
P0 (X). So we will also include some soft information which tells us how uncertain we are that the
coefficient is correct. The uncertainty is a number in [0, 1] that is based on how far the decoded codeword
Gx (Y ) is from the received word r(x,Y ). The farther apart, the higher the uncertainty. A natural choice
for the uncertainty is simply the ratio of the distance ∆(Gx (Y ), r(x,Y )) to half the minimum distance
(n − d)/2. Let f : S → F × [0, 1] be the function of guesses for P0 (x) and their uncertainties. We then use
a Reed–Solomon decoder with uncertainties to find the degree 0 polynomial that is closest to f (X). This
will give us P0 (X). Finally, subtract P0 (X)Y d from r(X,Y ) and repeat to get the subsequent coefficients.
Algorithm 1 Decoding bivariate Reed–Muller codes
1: Input: r : S2 → F.
2: for i = 0, 1, . . . , d do
3: Define ri : S × S → F by
i−1
ri (X,Y ) = r(X,Y ) − ∑ Q j (X)Y d− j .
j=0
4: for x ∈ S do
5: Define ri,x : S → F by ri,x (Y ) = ri (x,Y ).
6: Define Gx (Y ) ∈ F[Y ] by Gx (Y ) = FastRSDecoder(ri,x (Y ), d − i).
7: if Gx 6= ⊥ then
8: σx = CoeffY d−i (Gx ).
9: δx = ∆(ri,x , Gx ).
10: else
11: σx = 0.
12: δx = n.
13: end if
14: end for
15: Define the weighted function fi : S → F × [0, 1] by
δx
fi (x) = σx , min 1, .
(n − d + i)/2
16: Define Qi : S → F by Qi (X) = WeightedRSDecoder( fi (X), i).
17: end for
18: Output: ∑di=0 Qi (X)Y d−i .
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 10
D ECODING R EED –M ULLER C ODES OVER P RODUCT S ETS
3.2 Proof of Theorem 3.1
Correctness of Algorithm. It suffices to show that Qi (X) = Pi (X) for i = 0, 1, . . . , d, which we prove
by induction. For this proof, the base case and inductive step can be handled by a single proof. We
assume the inductive hypothesis that we have Q j (X) = Pj (X) for j < i. Note that the base case is i = 0
and in this case, we assume nothing.
It is enough to show
n i
∆( fi (X), Pi (X)) < 1− .
2 n
Then Pi (x) is the unique polynomial within weighted distance
n i
1−
2 n
of fi (X). So WeightedRSDecoder( fi (X), i) will output Qi (X) = Pi (X).
We first show that ri (X,Y ) is close to Ci (X,Y ) = ∑dj=i Pj (X)Y d− j . Observe the following.
i−1 i−1
ri (X,Y ) −Ci (X,Y ) = (ri (X,Y ) + ∑ Pj (X)Y d− j ) − (Ci (X,Y ) + ∑ Pj (X)Y d− j ))
j=0 j=1
i−1
= (ri (X,Y ) + ∑ Q j (X)Y d− j ) −C(X,Y )
j=0
= r(X,Y ) −C(X,Y ) .
Hence,
n2
d
∆(ri (X,Y ),Ci (X,Y )) = ∆(r(X,Y ),C(X,Y )) < 1− .
2 n
For each x ∈ S, define Ci,x (Y ) = Ci (x,Y ). Define ∆x = ∆(ri,x (Y ),Ci,x (Y )). Let
A = {x ∈ S | Gx (Y ) = Ci,x (Y )}
be the set of choices of x such that Gx (Y ) = FastRSDecoder(ri,x (Y ), d − i) produces Ci,x (Y ). Then, for
x ∈ A, we have
δx = ∆(ri,x (Y ), Gx (Y )) = ∆(ri,x (Y ),Ci,x (Y )) = ∆x .
And for x ∈
/ A, we have that the degree d − i polynomials Gx 6= Ci,x , and so
δx = ∆(ri,x (Y ), Gx (Y )) ≥ n − d + i − ∆(ri,x (Y ),Ci,x (Y )) = n − d + i − ∆x .
Note that this inequality holds even when Gx = ⊥, because the algorithm explicitly sets δx = n.
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 11
J OHN Y. K IM AND S WASTIK KOPPARTY
We now we give an upper bound on ∆( fi (X), Pi (X)).
1 δx 1 δx
∆( fi (X), Pi (X)) ≤ ∑ + ∑ 1−
x∈A 2 (n − d + i)/2 x∈A
/
2 (n − d + i)/2
∆x n − d + i − ∆x
≤∑ + ∑ 1−
x∈A n − d + i x∈A
/
n−d +i
∆x ∆x
=∑ +∑
x∈A n − d + i x∈A
/
n−d +i
∆x
=∑
x∈S n − d + i
∆(ri (X,Y ),Ci (X,Y ))
=
n−d +i
n2
d 1
< 1−
2 n n−d +i
n n−d
= ·
2 n−d +i
n n−i
≤ · since i ≤ d
2 n
n i
= 1− . (3.1)
2 n
Running time of Algorithm. We claim that the running time of our algorithm is
O(n3 poly(log(n), log(|F|)) .
The algorithm has d + 1 iterations. In each iteration, we update ri , apply FastRSDecoder to n rows
and apply WeightedRSDecoder a single time to get the leading coefficient. Since field operations
take polylog(|F|)) time, at the cost of a polylog(|F|) factor, we can count field operations as run-
ning in unit time. As updating takes O(n2 ) time, FastRSDecoder takes O(n polylog(n)) time, and
WeightedRSDecodertakes O(n2 polylog(n)) time, we get O(n2 polylog(n)) for each iteration. d + 1
iterations gives a total running time of O(dn2 polylog(n)) < O(n3 polylog(n)).
4 Reed–Muller decoding for general m
We now generalize the algorithm for decoding bivariate Reed–Muller codes to handle Reed–Muller codes
of any number of variables. As before, we write the codeword as a polynomial in one of the variables and
attempt to uncover its coefficients one at a time. Interestingly, this leads us to a Reed–Muller decoding
on one fewer variable, but with uncertainties. This lends itself nicely to an inductive approach on the
number of variables. However, the generalization requires us to be able to decode Reed–Muller codes
with uncertainties. This leads us to our main theorem.
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 12
D ECODING R EED –M ULLER C ODES OVER P RODUCT S ETS
Theorem 4.1. Let F be a finite field and let S ⊆ F be a nonempty subset of size |S| = n.
There is a O(nm+2 polylog(n, |F|))-time algorithm, which given a weighted received word w : Sm →
F × [0, 1], finds the unique polynomial (if any) C ∈ F[X1 , . . . , Xm ] with deg(C) ≤ d such that
1 d
∆(w,C) < 1− nm .
2 n
To decode a pure received word (without uncertainties), we may just set all the initial uncertainties to
0.
Note that in the bivariate case, the algorithm given by the above theorem is slower than the one given
by Theorem 3.1. This is because the above theorem can also handle uncertainties.
Proof. The algorithm is given in Algorithm 2.
The proof is by induction on the number of variables, and closely mirrors the proof of the bivariate
case.
Base case. We are given a received word with uncertainties w : S → F × [0, 1] and asked to find the
unique polynomial C ∈ F[X] with deg(C) ≤ d within weighted distance (n − d)/2 of w. This is just
Reed–Solomon decoding with uncertainty, which can be done in time O(n2 polylog(n)) via algorithm
WeightedRSDecoder.
Inductive step. Assume that the result holds for (m − 1)-variable Reed–Muller codes. That is, assume
we have access to an algorithm WeightedRMDecoder(w, d) which takes as input a received word with
uncertainties w : Sm−1 → F × [0, 1], and outputs the unique polynomial of degree at most d (if any) within
weighted distance (nm−1 /2)(1 − d/n) from w. We want to produce an algorithm for m variables.
We are given w : Sm → F × [0, 1]. View w as a map from Sm−1 × S → F × [0, 1], and write
X ,Y ) = (r(X
w(X X ,Y ), u(X
X ,Y )) ,
where X1 , . . . , Xm−1 ,Y are the m-variables, and X = (X1 , . . . , Xm−1 ). Suppose that there exists a polynomial
C ∈ F[X
X ,Y ] with deg(C) ≤ d such that
nm
d
∆(w,C) < 1− .
2 n
View C as a polynomial in Y with coefficients in F[X X ,Y ) = ∑di=0 Pi (X
X ], C(X X )Y d−i .
The general strategy of the algorithm is to determine the Pi ’s inductively by performing d + 1 iterations
from i = 0 to i = d, and recovering Pi (XX ) at the i-th iteration. We give an informal overview next, and
then give the algorithm itself.
For the i-th iteration, consider the word wi : Sm → F × [0, 1] given by:
!
i−1
X ,Y ) =
wi (X r(X X )Y d− j , u(X
X ,Y ) − ∑ Pj (X X ,Y ) .
j=0
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 13
J OHN Y. K IM AND S WASTIK KOPPARTY
X )Y d− j , wi will be close to Ci = ∑dj=i Pj (X
Since w is close to ∑dj=0 Pj (X X )Y d− j . Our goal is to find Pi (X
X ),
the coefficient of Y d−i when Ci when viewed as a polynomial in Y . For each x ∈ Sm−1 , we decode the
Reed–Solomon code with uncertainties given by wi (xx,Y ) and extract the coefficient of Y d−i along with
how uncertain we are about the correctness of this coefficient. This gives us a guess for the value Pi (xx)
and our uncertainty for this guess. We construct the function fi : Sm−1 → F × [0, 1] of guesses for Pi with
their uncertainties. We then apply the algorithm given by induction hypothesis to fi , and this gives us Pi .
Algorithm 2 WeightedRMDecoder: Decoding general Reed–Muller codes with uncertainties
1: Input: w : Sm → F × [0, 1].
2: Define r : Sm → F and u : Sm → [0, 1] by: w(X
X ,Y ) = (r(X
X ,Y ), u(X
X ,Y )).
3: for i = 0, 1, . . . , d do !
i−1
4: Define wi : Sm × S → F × [0, 1] by wi (X
X ,Y ) = r(X X )Y d− j , u(X
X ,Y ) − ∑ Q j (X X ,Y ) .
j=0
5: for x ∈ Sm−1 do
6: Define wi,xx : S → F × [0, 1] by wi,xx (Y ) = wi (xx,Y ).
7: Define Gx (Y ) ∈ F[Y ] by Gx (Y ) = WeightedRSDecoder(wi,xx (Y ), d − i).
8: if Gx 6= ⊥ then
9: σx = CoeffY d−i (Gx ).
10: δx = ∆(wi,xx , Gx ).
11: else
12: σx = 0.
13: δx = n.
14: end if
15: end for
16: Define the weighted function fi : Sm → F × [0, 1] by
δx
fi (xx) = σx , min 1, .
(n − d + i)/2
17: X ) ∈ F[X1 , . . . , Xm−1 ] by Qi (X
Construct the polynomial Qi (X X ) = WeightedRMDecoder( fi (X
X ), i).
18: end for
19: Output: ∑di=0 Qi (X
X )Y d−i .
X ,Y ) = ∑di=0 Pi (X
Correctness of Algorithm. Suppose there is a polynomial C(X X )Y d−i such that
nm
d
∆(w,C) < 1− .
2 n
X ) = Pi (X
We will show by induction that the i-th iteration of the algorithm produces Qi (X X ). For this proof,
the base case and inductive step can be handled by a single proof. We assume the inductive hypothesis
X ) = Pj (X
that we have Q j (X X ) for j < i. Note that the base case is i = 0 and in this case, we assume
nothing.
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 14
D ECODING R EED –M ULLER C ODES OVER P RODUCT S ETS
It is enough to show
nm−1
i
X ), Pi (X
∆( fi (X X )) < 1− .
2 n
X ) is the unique polynomial within weighted distance (nm−1 /2)(1 − i/n) of fi (X
Then Pi (X X ). So by the
induction hypothesis for (m − 1)-variate Reed–Muller codes, WeightedRMDecoder( fi (X X ), m, i) will
X ) = Pi (X
output Qi (X X ).
X ,Y ) = ∑dj=i Pj (X
We first show that wi is close to Ci (X X )Y d− j . Define ri : Sm → F and ui : Sm → [0, 1]
by:
wi (xx, y) = (ri (xx, y), ui (xx, y)) .
Observe the following.
i−1 i−1
X ,Y ) −Ci (X
ri (X X ,Y ) = ri (X X )Y d− j − Ci (X
X ,Y ) + ∑ Pj (X X )Y d− j )
X ,Y ) + ∑ Pj (X
j=0 j=0
i−1
= ri (X X )Y d− j −C(X
X ,Y ) + ∑ Q j (X X ,Y )
j=0
X ,Y ) −C(X
= r(X X ,Y ) .
Also observe that ui (xx, y) = u(xx, y). Hence,
nm
d
∆(wi ,Ci ) = ∆(w,C) < 1− .
2 n
For each x ∈ Sm−1 , define Ci,xx (Y ) = Ci (xx,Y ). Define ∆x = ∆(wi,xx (Y ),Ci,xx (Y )). Let
A = {xx ∈ Sm−1 | Gx (Y ) = Ci,xx (Y )}
be the set of choices of x such that Gx (Y ) = FastRSDecoder(wi,xx (Y ), d − i) produces Ci,xx (Y ).
Then, for x ∈ A, we have
δx = ∆(wi,xx (Y ), Gx (Y )) = ∆(wi,xx (Y ),Ci,xx (Y )) = ∆x .
And for x ∈ / A, we have Gx 6= Ci,xx and both are low-degree polynomials, so ∆(Gx ,Ci,xx ) ≥ n − d + i.
By the triangle inequality, we have:
δx = ∆(wi,xx (Y ), Gx (Y )) ≥ n − d + i − ∆(wi,xx (Y ),Ci,xx (Y )) = n − d + i − ∆x .
Note that this inequality holds even when Gx = ⊥, because the algorithm explicitly sets δx = n.
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 15
J OHN Y. K IM AND S WASTIK KOPPARTY
X ), Pi (X
We now give an upper bound on ∆( fi (X X )).
1 δx 1 δx
X )) ≤ ∑
X ), Pi (X
∆( fi (X + ∑ 1− (4.1)
x ∈A 2 (n − d + i)/2 x ∈A
/
2 (n − d + i)/2
∆x n − d + i − ∆x
≤∑ + ∑ 1− (4.2)
x∈A n − d + i x ∈A
/
n−d +i
∆x ∆x
=∑ +∑ (4.3)
x∈A n − d + i x ∈A
/
n−d +i
∆x
= ∑ n−d +i (4.4)
x ∈Sm−1
X ,Y ),Ci (X
∆(wi (X X ,Y ))
= (4.5)
n − d+ i
nm d 1
< 1− (4.6)
2 n n−d +i
n m−1 n−d
= · (4.7)
2 n−d +i
nm−1 n − i
≤ · (4.8)
2 n
nm−1 i
= 1− . (4.9)
2 n
This implies that Pi = Qi , as desired.
Running time of Algorithm. We now show that the running time of our m-variate Reed–Muller
decoder is O(nm+2 polylog(n) polylog(|F|)). We again proceed by induction on m. In the base case of
m = 1, we simply run the Reed–Solomon decoder with uncertainties, which runs in O(n2 polylog(n))
time (which is even a factor n better than what we need to show). Now suppose the (m − 1)-variate
Reed–Muller decoder runs in time O(nm+1 polylog(n)). We need to show that the m-variate Reed–Muller
decoder runs in time O(nm+2 polylog(n)).
The algorithm makes d + 1 iterations. In each iteration, we first (1) perform nm−1 Reed–Solomon
decodings with uncertainties and extract the leading coefficient along with its uncertainty for each one,
and then (2) do an (m − 1)-variate Reed–Muller decoding with uncertainties. Each Reed–Solomon
decoding takes O(n2 polylog(n)) time, while computing an uncertainty of a leading coefficient takes
O(n polylog(n)). So in this step, we have cumulative running time
O(nm−1 · n2 · polylog(n)) = O(nm+1 polylog(n)) .
The (m − 1)-variate Reed–Muller decoding with uncertainties takes O(nm+1 polylog(n)) time by our
induction hypothesis.
This makes the total running time for all iterations O(dnm+1 polylog(n)) ≤ O(nm+2 polylog(n)), as
desired.
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 16
D ECODING R EED –M ULLER C ODES OVER P RODUCT S ETS
5 Near-linear-time decoding in the bivariate case
In this section, we present our near-linear-time, randomized decoding algorithm for bivariate Reed–Muller
codes.
Theorem 5.1. Let α ∈ (0, 1) be a constant. Let F be a finite field and let S ⊆ F be a nonempty subset of
size |S| = n. Let d = αn.
There is a O(n2 polylog(n, |F|))-time randomized algorithm which, given a received word r : S2 → F,
finds the unique polynomial (if any) C ∈ F[X,Y ] with deg(C) ≤ d such that
1 10
∆(r,C) < 1 − α − √ n2 .
2 n
5.1 Outline of improved algorithm
Recall that the decoding algorithm we presented in the previous sections make d + 1 iterations, revealing a
single coefficient of the nearest codeword during one iteration. In a given iteration, the bivariate algorithm
decodes each row of ri (X,Y ) to the nearest polynomial of degree d − i, extracting the coefficient of Y d−i
and its uncertainty. Then the algorithm Reed–Solomon decodes (with uncertainties) to get the leading
coefficient of C(X,Y ), when viewed as a polynomial in Y .
The running time of this algorithm is O(n3 polylog(n)). Each iteration has n Reed–Solomon de-
codings and a single Reed–Solomon decoding with uncertainties. As Reed–Solomon decoding takes
O(n polylog(n)) time and Reed–Solomon decoding with uncertainties takes O(n2 polylog(n)) time, we
get a running time of O(n3 polylog(n)) with d + 1 iterations. To achieve near-linear time, we need to shave
off a factor of n on both the number of Reed–Solomon decodings and the running time of Reed–Solomon
decoding with uncertainties.
To save on the number of Reed–Solomon decodings, we will instead list decode beyond half the
minimum distance (using the near-linear time Reed–Solomon list-decoder FastRSListDecoder), and
show that the list we get is both small and essentially contains all of the decoded polynomials we require
for Ω(n) iterations of i (thus we can reduce the number of decodings by a factor Ω(n)). So we will do
O(n) Reed–Solomon list-decodings total instead of O(n2 ) Reed–Solomon unique decodings to half the
minimum distance.
To save on the running time of Reed–Solomon decoding with uncertainties, we will use the faster
probabilistic variant FastWeightedRSDecoder of Forney’s generalized minimum distance decoding
algorithm, which runs in near-linear time, but reduces the decoding radius from 1/2 the minimum
distance to 1/2 − o(1) of the minimum distance.
5.2 Ingredients of the algorithm
Reducing the number of decodings. To reduce the number of decodings, we will list decode past half
the minimum distance. Let ri,x : S → F be a received word for a Reed–Solomon code Ci of degree at
most di = d − i. Let t be the radius to which we list decode, and let Li,x = {C ∈ Ci | ∆(C, ri,x ) < t} be
the list of codewords within distance t of ri,x . The radius to which we can decode while maintaining a
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 17
J OHN Y. K IM AND S WASTIK KOPPARTY
polynomial-size list is given by the Johnson bound:
p
n 1 − 1 − δi ,
where
d −i d
δi = 1 − > 1− = 1−α
n n
is the relative distance of the code. By Taylor approximating the square root, we see that the Johnson
bound exceeds half the minimum distance by Ω(n):
p
n(1 − 1 − δi ) > n(1 − (1 − (δi /2 + δi2 /8 + 3δi3 /16)))
= n(δi /2 + (1 − α)2 /8 + 3(1 − α)3 /16)
= (n − d + i)/2 + ((1 − α)2 /8)n + εn,
where ε = 3(1 − α)3 /16 is a positive constant. By the quantitative version of the Johnson bound (such as
the one by Cassuto and Bruck [3]), we see that if we set the list decoding radius
t = (n − d + i)/2 + ((1 − α)2 /8)n ,
then the size of the list |Li,x | < 1/ε is constant. So the list decoding radius exceeds half the minimum
distance by Ω(n), and the list size is constant. The algorithm FastRSListDecoder (due to Alekhnovich [1])
can find this list Li,x in time (1/α)O(1) n log2 n log log(n) = O(n polylog(n)). More precisely, we will let
FastRSListDecoder(r, d, Λ) denote this algorithm, that outputs a list of all polynomials P of degree at
most d within distance Λ of the received word r.
Faster Reed–Solomon decoding with uncertainties. We will use a faster randomized algo-
rithm for decoding Reed–Solomon codes with uncertainties. We will refer to this algorithm as
FastWeightedRSDecoder( f , d), where f : S → F × [0, 1] is a received word with uncertainties, and
d is the degree of the code. More precisely, FastWeightedRSDecoder( f , d, γ) will run in time
√
n poly(log(n), log 1/γ) and output the codeword within distance (n − d − 10 n)/2 (if any) with proba-
bility at least 1 − γ. In our Reed–Muller decoding algorithms, we will invoke FastWeightedRSDecoder
with γ set to n−c for some large c. This will allow us to say, by a union bound, that the probability that
any of the invocations return a wrong answer is at most o(1). We may thus assume (for the sake of
analysis of the correctness of the algorithms) that FastWeightedRSDecoder always correctly decodes
√
Reed–Solomon codes (with uncertainties) up to radius (n − d − 10 n)/2.
Proof of Theorem 5.1. The algorithm is given in Algorithm 3. We claim that it has the required properties.
We first analyze correctness, and then we analyze the running time.
Correctness of Algorithm. Let r : S × S → F be a received word, and let C(X,Y ) be a polynomial of
degree at most d such that
1 10
∆(r,C) < 1 − α − √ n2 .
2 n
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 18
D ECODING R EED –M ULLER C ODES OVER P RODUCT S ETS
Algorithm 3 Fast decoding of bivariate Reed–Muller codes
1: Input: r : S2 → F.
2: Let c = ((1 − α)2 /8).
3: Let e = b2cnc.
4: for i = 0, 1, . . . , d do
5: Define ri : S × S → F by
i−1
ri (X,Y ) = r(X,Y ) − ∑ Q` (X)Y d−` .
`=0
6: for x ∈ S do
7: Define ri,x : S → F by ri,x (Y ) = ri (x,Y ).
8: if (e + 1) | i then
i
9: Let j = e+1 .
n−d+i
10: Let t j = 2 + cn.
11: Define Li,x = FastRSListDecoder(ri,x , d − i,t j ).
12: else
13: Define Li,x = {R(Y ) − Qi−1 (x)Y d−i+1 | R(Y ) ∈ Li−1,x , CoeffY d−i+1 (R) = Qi−1 (x)}.
14: end if
15: Define Gx (Y ) to be the unique element (if any) of the list Li,x with degree at most d − i and:
n−d +i
∆(Gx , ri,x ) <
2
16: if Gx 6= ⊥: then
17: σx = CoeffY d−i (Gx ).
18: δx = ∆(Gx , ri,x ).
19: else
20: σx = 0
21: δx = n
22: end if
23: end for
24: Define the weighted function fi : S → F × [0, 1] by
δx
fi (x) = σx , min{1, } .
(n − d + i)/2
25: Define Qi : S → F by
Qi (X) = FastWeightedRSDecoder( fi (X), i, n−5 ) .
26: end for
27: Output: ∑di=0 Qi (X
X )Y d−i .
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 19
J OHN Y. K IM AND S WASTIK KOPPARTY
Let C(X,Y ) = ∑di=0 Pi (X)Y d−i . We will show that the Qi produced by the algorithm satisfy Qi (X) = Pi (X)
for i = 0, . . . , d (with high probability over the randomness of FastWeightedRSDecoder).
As commented earlier, we will assume that every invocation of FastWeightedRSDecoder is success-
ful: this is allowed since we have tuned the parameter γ to be a suitably small polynomial function of
n.
By induction on i, we will show that all the following statements hold for each i ≤ d.
1. ri,x in Algorithm 1 and Algorithm 3 are the same for all x ∈ S,
i
2. For j = b e+1 c, Li,x contains all polynomials R0 (Y ) of degree at most d − i such that
∆(R0 , ri,x ) ≤ t j .
3. Qi (X) = Pi (X).
The analysis will follow the analysis of Algorithm 1 very closely.
For i = 0, Item 1 is trivial (since in both Algorithm 1 and Algorithm 3, r0,x (y) = r(x, y) ). For other i,
Item 1 follows immediately from the definition of ri,x and from Item 3 of the induction hypothesis for
i − 1.
For every i with (e + 1) | i (and in particular for i = 0), Item 2 follows from Step 11. For other i, Li,x
is obtained from Li−1,x in Step 13 of the algorithm. Suppose R0 (Y ) is a polynomial of degree at most d − i
such that ∆(R0 , ri,x ) ≤ t j . Consider the polynomial R(Y ) = R0 (Y ) − Qi−1 (x)Y d−i+1 which is of degree at
most d − i + 1. We will show that R(Y ) ∈ Li−1,x , and then Step 13 of the algorithm will put R0 (Y ) into
Li,x . By construction,
∆(R, ri−1,x ) = ∆(R0 (Y ) − Qi−1 (x)Y d−i+1 , ri−1,x )
= ∆(R0 (Y ), ri−1,x + Qi−1 (x)Y d−i+1 )
= ∆(R0 , ri,x )
≤ tj .
This, along with the induction hypothesis for i − 1, implies that R(Y ) ∈ Li−1,x ), as desired.
Now we discuss Item 3. Let j = bi/(e + 1)c. If Item 2 holds for some i, then using the fact that
n − d + j · (e + 1) n − d + j · (e + 1) + 2cn n − d + j · (e + 1) + e n − d + i
tj = + cn = > ≥ ,
2 2 2 2
we conclude that Gx (Y ) is the unique polynomial in F[Y ] (if any) of degree at most d − i with
n−d +i
∆(Gx , rx,i ) < .
2
Thus the Gx produced in Step 15 of Algorithm 3 is the same as the corresponding Gx in Algorithm 1.
This implies that the function fi in Algorithm 1 and Algorithm 3 are the same.
We will now show that √
n − i − 10 n
∆( fi , Pi ) < . (5.1)
2
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 20
D ECODING R EED –M ULLER C ODES OVER P RODUCT S ETS
By induction, we may assume that we have already shown that P` = Q` for each ` ∈ {0, 1, . . . , i − 1}.
Letting:
d
Ci (X,Y ) = ∑ Pj (X)Y d− j ,
j=i
we get that ∆(ri ,Ci ) = ∆(r,C). Following the same calculation as in (3.1), we have the following.
∆(ri ,Ci )
∆( fi , Pi ) <
n−d +i
∆(r,C)
=
n−d +i
1 10 2
2 (1 − α − n )n
√
≤
n(1 − α) + i
10
1 1 − α − √n
≤ ·n
2 1 − α + ni
1 i 10
≤ 1− − √ ·n
2 n n
1 √
= (n − i − 10 n) ,
2
as required.1
Now, Inequality (5.1) implies that the invocation of FastWeightedRSDecoder in Step 25 will return
Pi , and thus Qi = Pi . This completes the proof of the inductive step.
Now that we have shown that for all i we have Qi = Pi , we can conclude that the output of the
algorithm is indeed C(X,Y ), as desired.
Analysis of running time of bivariate Reed–Muller decoder. Algorithm 3 invokes the algorithm
FastRSListDecoder
d α 4α
n≤ n≤ n
e+1 2c (1 − α)2
times, and invokes FastWeightedRSDecoder d = αn times. As both of these algorithms run in
O(n · polylog(n)) time, the total running time of Algorithm 3 is O(n2 polylog(n, |F|)) (after account-
ing for the remaining operations), as desired.
1 In the penultimate step, we used the inequality:
u
≤ 1−γ ,
u+γ
which holds for nonnegative reals u, γ with u + γ ≤ 1. For our application, we set
10 i 10
u = 1−α − √ and γ= +√ .
n n n
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 21
J OHN Y. K IM AND S WASTIK KOPPARTY
6 Near-linear-time decoding in the general case
In this section, we give a more involved variation of the previous algorithm to get a near-linear time,
randomized algorithm for decoding Reed–Muller codes up to half the minimum distance over any
number of variables. It is worth noting that we do not know how to decode Reed–Muller codes with
uncertainties up to half the minimum distance in near-linear time. Nevertheless, our algorithm for
decoding Reed–Muller codes in near-linear time is based on a subroutine which decodes Reed–Muller
codes with uncertainties from (1/2 − ε) of the minimum distance in near-linear time.
Below we state the main theorem of this section.
Theorem 6.1. Let α ∈ (0, 1) be a constant. Let F be a finite field and let S ⊆ F be a nonempty subset of
size |S| = n. Let d = αn.
There is a O (nm · polylog(n, |F|))-time randomized algorithm FastRMDecoder, which given a re-
ceived word r : Sm → F, finds with probability 2/3, the unique (if any) polynomial C ∈ F[X1 , . . . , Xm ] with
deg(C) ≤ d such that √
1 10(m − 1) n m
∆(r,C) < 1−α − n .
2 n
As part of this algorithm for near-linear-time Reed–Muller decoding to a radius nearly half the
minimum distance, we will need to quickly decode Reed–Muller codes with uncertainties to various radii
significantly less than half the minimum distance. Such an algorithm, which comes with a tunable slack
parameter e, is given by the following theorem. The larger e is, the faster the algorithm runs, at the cost
of reducing the number of errors that can be corrected.
Theorem 6.2. Let F be a finite field and let S ⊆ F be a nonempty subset of size |S| = n. Let e, d be
nonnegative integers, with e ≤ d < n.
There is a randomized algorithm FastWeightedRMDecodere with running time
1 m
1
O · n · (d + 1) · polylog n, |F|,
e+1 γ
which, given a received word with uncertainties w : Sm → F × [0, 1], finds, with probability 1 − γ, the
unique (if any) polynomial C ∈ F[X1 , . . . , Xm ] with deg(C) ≤ d such that
√
1 d 10m n + e m
∆(w,C) < 1− − n .
2 n n
Remark 6.3. By setting e = d/polylog(n) in Theorem 6.2, the resulting algorithm is almost as good as
the algorithm from Theorem 6.1. The algorithm from Theorem 6.2 is still near-linear time, but decodes
from a number of errors which is a (1/2 − 1/polylog(n))-fraction of the minimum distance, instead of
√
(1/2 − 1/ n)-fraction of the minimum distance.
6.1 The main subroutine: decoding Reed–Muller codes with uncertainties
Proof of Theorem 6.2. The proof is by induction on the number of variables m. The proof of the base
case of m = 1 follows by simply noting that the algorithm FastWeightedRSDecoder mentioned earlier
satisfies the requirement.
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 22
D ECODING R EED –M ULLER C ODES OVER P RODUCT S ETS
Now we will show how to decode m-variate Reed–Muller codes, assuming that we have already
shown how to decode m − 1-variate Reed–Muller codes. Thus we will assume access to the algorithm
FastWeightedRMDecodere ( f , d, γ) with running time
m−1
n (d + 1) 1
O · polylog n, |F|,
e+1 γ
that finds, with probability 1 − γ, the unique polynomial (if any) of degree at most d within distance Λ
from f , where f : Sm−1 → F × [0, 1] and
√
nm−1
d 10(m − 1) n + e
Λ= 1− − .
2 n n
First some convenient notation. Instead of working with the m variables X1 , X2 , . . . , Xm , we work with
the m variables X1 , X2 , . . . , Xm−1 and Y . We will use X to denote (X1 , . . . , Xm−1 ).
We begin by observing that it suffices to give a randomized O (nm (d + 1)/(e + 1)) · polylog(n, |F|))-
time algorithm that succeeds with probability only 2/3: the success probability can be amplified to 1 − γ
by repeating O(log 1/γ) times.
See Algorithm 4 for a formal description of the algorithm (which has success probability 2/3). We
now give a high-level description of what it does.
At the high level, the key difference between Algorithm 4 and Algorithm 2 is that we reduce the
number of Reed–Solomon decodings, at the cost of reducing the radius to which our overall Reed–Muller
decoder works. We write the nearby polynomial C(X X ,Y ) as ∑di=0 Pi (X
X )Y d−i , and find the Pi iteratively.
In the i-th iteration, we would like to decode row wi,xx , x ∈ Sm−1 to a nearby degree d − i univariate
polynomial. To reduce the number of times we decode, we only do the decoding for one in every e + 1
iterations of i, and use this decoding for the subsequent e iterations. This reduces the number of decodings
by a factor e + 1, at the cost of reducing the radius to which we decode a univariate polynomial by e (at
most). These univariate decodings allow us to construct the weighted function fi : Sm−1 → F, where for
each x ∈ Sm−1 , fi (xx) is our guess for Pi (xx). The algorithm then recovers Pi by recursively calling the
(m − 1)-variable Reed–Muller decoder to decode fi , with the parameter e set to a carefully chosen value
(denoted ei above). Analyzing this recursion gives the claimed running time.
Overall, this translates into a faster Reed–Muller decoder, albeit with a slightly smaller decoding
radius.
Proof of Correctness. We will show that for each i ∈ [0, d], Qi (X
X ) = Pi (X
X ).
Formally, we will show by induction on i, the following two statements.
1. If j = bi/(e + 1)c, then for all x ∈ Sm−1 , Gi,xx is the unique (if any) polynomial of degree at most
d − i such that: √
n − d + j · (e + 1)) 10 n
∆(Gi,xx , wi,xx ) ≤ − .
2 2
2. Qi = Pi .
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 23
J OHN Y. K IM AND S WASTIK KOPPARTY
Algorithm 4 FastWeightedRMDecodere : (Quite) Fast decoding of general Reed–Muller codes with
Uncertainties
1: Input: w : Sm → F × [0, 1].
2: Define r : Sm → F and u : Sm → [0, 1] by: w(X
X ,Y ) = (r(X
X ,Y ), u(X
X ,Y )).
3: for i = 0, 1, . . . , d do
4: Define ri : Sm−1 × S → F by
i−1
X ,Y ) = r(X
ri (X X )Y d−` .
X ,Y ) − ∑ Q` (X
`=0
5: for x ∈ Sm−1 do
6: if (e + 1) | i then
7: Define wi,xx : S → F × [0, 1] by
wi,xx (Y ) = (ri (xx,Y ), u(xx,Y )) .
8: Define Gi,xx (Y ) = FastWeightedRSDecoder(wi,xx (Y ), d − i, n−2m ).
9: else
10: Define Gi,xx (Y ) = Gi−1,xx (Y ) − Qi−1 (xx)Y d−i+1 .
11: end if
12: if deg(Gi,xx (Y )) ≤ d − i then
13: σx = CoeffY d−i (Gi,xx (Y )).
14: δx = ∆(Gi,xx , wi,xx ).
15: else
16: σx = 0.
17: δx = n.
18: end if
19: end for
20: Define the weighted function fi : Sm−1 → F × [0, 1] by
δx
fi (xx) = σx , min 1, √ .
(n − d + i − 10 n − e)/2
21: Define ei by: √
(i + 10(m − 1) n)(d − i)
ei = .
n − (d − i)
22: Define Qi : Sm−1 → F by
X ) = FastWeightedRMDecoderei fi , i, n−2m
Qi (X
23: end for
24: Output: ∑di=0 Qi (X
X )Y d−i .
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 24
D ECODING R EED –M ULLER C ODES OVER P RODUCT S ETS
Item 1 implies, in particular, that Gi,xx is the unique polynomial (if any) of degree at most d − i within
distance √
n − d + i 10 n + e
−
2 2
from wi,xx .
We first prove Item 1. If (e + 1) | i, then Step 8 of the algorithm immediately implies Item 1. For
other i, Gi,xx is obtained from Gi−1,xx in Step 10 of the algorithm. Suppose R0 (Y ) ∈ F[Y ] is a polynomial of
degree at most d − i such that
√
0 n − d + j · (e + 1)) 10 n
∆(R , wi,xx ) ≤ − .
2 2
Consider the polynomial R(Y ) = R0 (Y ) + Qi−1Y d−i+1 , which is a polynomial of degree at most d − i + 1.
By Item 2 of the induction hypothesis, R(Y ) = R0 (Y ) + Pi−1Y d−i+1 . Thus:2
√
n − d + j · (e + 1)) 10 n
∆(R, wi−1,xx ) = ∆(R0 , wi−1,xx − Pi−1Y d−i+1 ) = ∆(R0 , wi,x ) ≤ − .
2 2
By Item 1 of the induction hypothesis, we have that R must equal Gi−1,xx , and thus Step 10 of the algorithm
sets Gi,xx (Y ) = R0 (Y ).
Now we prove Item 2. Since Qi is found by decoding fi to a nearby polynomial (in Step 22), it will
be enough for us to show that Pi is sufficiently close fi . We begin by computing the radius Λi to which
the error-correction algorithm in Step 22 decodes. Recall that
√
(i + 10(m − 1) n)(d − i)
ei = .
n − (d − i)
Thus we have the following.
√
1 m−1 i 10(m − 1) n + ei
Λi = n 1− −
2 n n
√ √
1 m−1 i 10(m − 1) n (i + 10(m − 1) n)(d − i)
≥ n 1− − −
2 n n (n − (d − i))n
√ √
1 m−1 i(n − (d − i)) + 10(m − 1)(n − (d − i)) n + (i + 10(m − 1) n)(d − i)
= n 1−
2 n(n − (d − i))
√
1 m−1 in + 10(m − 1)n n
= n 1−
2 n(n − (d − i))
√
1 m−1 i + 10(m − 1) n
= n 1− .
2 n − (d − i)
2 Here we use a simple fact. For a weighted word w = (σ , u) : S → F × [0, 1] and a pure word r : S → F, define w + r by:
(w + r)(y) = (σ (y) + r(y), u(y)) .
Then for a pure word q : S → F, we have:
∆(q − r, w) = ∆(q, w + r) .
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 25
J OHN Y. K IM AND S WASTIK KOPPARTY
Thus, if we show that
√
1 i + 10(m − 1) n
∆( fi , Pi ) < 1− , (6.1)
2 n−d +i
then it will mean that Pi is the unique polynomial of degree i within distance Λi of fi , and thus Step 22
will set Qi = Pi .
We now show that Inequality (6.1) holds. Letting
d
X )Y d− j ,
X ,Y ) = ∑ Pj (X
Ci (X
j=i
we get that ∆(wi ,Ci ) = ∆(w,C). For x ∈ Sm−1 , let Ci,xx (Y ) = Ci (xx,Y ).
By Item 1, we have that Gi,xx is the result of decoding wi,xx to radius
1 √
(n − d + i − 10 n − e) .
2
There are four possibilities.
1. The decoding is unsuccessful (i. e., Gi,xx = ⊥). In this case, δx = n, and so the the uncertainty in
fi (xx) equals 1. The contribution of x to ∆( fi , Pi ) is ∆( fi (xx), Pi (xx)) = 1/2, which is bounded above
by
1 ∆(wi,xx ,Ci,xx ) ∆(wi,xx ,Ci,xx )
√ = √ .
2 (n − d + i − 10 n − e)/2 n − d + i − 10 n − e
2. The decoding succeeds and is correct. In this case, Gi,xx = Ci,xx , so we have
1 ∆(wi,xx ,Ci,xx )
∆( fi (xx), Pi (xx)) = √
2 (n − d + i − 10 n − e)/2
∆(wi,xx ,Ci,xx )
= √ .
n − d + i − 10 n − e
3. The decoding succeeds, but is the wrong codeword, whose leading coefficient disagrees with that
of the correct codeword. In this case, the degree d − i polynomials Gi,xx 6= Ci,xx , and so we have
1 ∆(wi,xx , Gi,xx )
∆( fi (xx), Pi (xx)) = 1 − √
2 (n − d + i − 10 n − e)/2
(n − d + i) − ∆(wi,xx ,Ci,xx )
≤ 1− √
n − d + i − 10 n − e
√
(n − d + i − 10 n − e) − ∆(wi,xx ,Ci,xx )
≤ 1− √
n − d + i − 10 n − e
∆(wi,xx ,Ci,xx )
≤ √ .
n − d + i − 10 n − e)
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 26
D ECODING R EED –M ULLER C ODES OVER P RODUCT S ETS
4. The decoding succeeds, but is the wrong codeword, whose leading coefficient matches that of the
correct codeword. As in the previous case, Gi,xx 6= Ci,xx , and we have
1 ∆(wi,xx , Gi,xx )
∆( fi (xx), Pi (xx)) = √
2 (n − d + i − 10 n − e)/2
1 ∆(wi,xx , Gi,xx )
≤ 1− √ since 12 ε ≤ 1 − 21 ε if ε ≤ 1
2 (n − d + i − 10 n − e)/2
∆(wi,xx ,Ci,xx )
≤ √ ,
n − d + i − 10 n − e
where the deduction of the last step follows from exactly the same argument as in the previous case.
Putting it all together, we have the following inequalities.
∆(wi,xx ,Ci,xx )
∆( fi , Pi ) ≤ ∑ n − d + i − 10√n − e
x ∈Sm−1
∆(wi ,Ci )
= √
n − d + i − 10 n − e
∆(w,C)
= √
n − d + i − 10 n − e
√
nm d+10m n+e
2 1 − n
≤ √
n − d + i − 10 n − e
√
nm−1 n − d − 10m n − e
= √
2 n − d + i − 10 n − e
√
nm−1 n − d − 10(m − 1) n
≤
2 n−d +i
m−1
√
n i + 10(m − 1) n
= 1− .
2 n−d +i
Analysis of running time. The algorithm can be divided into two parts.
1. Constructing the fi , i = 0, . . . , d.
2. Decoding the fi to get the Pi , i = 0, . . . , d.
The dominant contribution to the running time when constructing fi comes from all the Reed–Solomon
decodings with uncertainties we have to do to get the Gi,xx (Y ). For every e + 1 iterations, we have to
decode each row x ∈ Sm−1 again. The total number of such decodings is given by
d + 1 m−1 nm−1 (d + 1)
·n = .
e+1 e+1
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 27
J OHN Y. K IM AND S WASTIK KOPPARTY
Since each Reed–Solomon decoding with uncertainty can be done in O(n polylog(n)) time via the
FastWeightedRSDecoder, we have that the running time of this part of the algorithm is
m
n (d + 1)
O polylog(n) .
e+1
To understand the running time of the second part of the algorithm, we will compute the running time
of decoding fi for each i. By induction, we know that the running time for this decoding during iteration i
is at most m−1
n · (i + 1)
O · polylog(n) .
ei + 1
Summing this up over all i, we get that the total running time for decoding all the fi s is
! !
d d
nm−1 · (i + 1) m−1 i+1
O ∑ · polylog(n)) ≤ O(n polylog(n) · ∑ .
i=0 ei + 1 i=0 ei + 1
It remains to bound ∑di=0 ei+1
i +1
from above.
d d−1
i+1 i+1
≤
∑ ei + 1 ∑ ei + 1 + (d + 1)
i=0 i=0
d−1
i+1
≤ ∑ (i+10(m−1)√n)(d−i) + (d + 1)
i=0 n−d+i
d−1
(i + 1)(n − d + i)
≤∑ √ + (d + 1)
i=0 (i + 10(m − 1) n)(d − i)
d−1
(i + 1)(n − d + i)
≤∑ √ + (d + 1)
i=0 (i + 10(m − 1) n)(d − i)
d−1
n
≤∑ + (d + 1)
i=0 d − i
≤ O(n log d) .
So the running time for decoding the fi for all d + 1 iterations is:
O nm−1 (n log d) polylog(n) = O(nm polylog(n)) .
This means the running time for both parts of the algorithm is just
m
n (d + 1)
O polylog(n) ,
e+1
as desired.
It is worth noting that the bottleneck for the running time is the the first part; that is, for the Reed–
Solomon decodings. This will be speeded up in the subsequent algorithm.
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 28
D ECODING R EED –M ULLER C ODES OVER P RODUCT S ETS
6.2 Decoding Reed–Muller codes in near-linear time
We now prove Theorem 6.1. This algorithm combines aspects of the fast bivariate Reed–Muller decoding
algorithm, Algorithm 3, and the previous algorithm, Algorithm 4.
Proof of Theorem 6.1. The decoding algorithm is given in Algorithm 5.
Proof of Correctness. As commented earlier, since we have set the error probability argument
γ suitably small, we may assume for the analysis that all invocations of the randomized decoder
FastWeightedRMDecoder give the correct answer.
Suppose C(XX ,Y ) = ∑di=0 Pi (X
X )Y d−i is a codeword such that
√
nm
d 10(m − 1) n
∆(r,C) < 1− − .
2 n n
X ) = Pi (X
We want to show that for each i, Qi (X X ). We will do this by induction on i.
By induction on i, we will show the following.
1. ri,xx in Algorithm 2 and Algorithm 5 are the same for all x ∈ Sm−1 .
i
2. For j = b e+1 c, Li,xx contains all polynomials R0 (Y ) of degree at most d − i such that
∆(R0 , ri,xx ) ≤ t j .
3. Qi (X) = Pi (X).
The analysis will follow the analyses of Algorithm 2, Algorithm 3 and Algorithm 4 very closely.
For i = 0, Item 1 is trivial (since in both Algorithm 2 and Algorithm 5, r0,xx (y) = r(xx, y). For other i,
Item 1 follows immediately from the definition of ri,xx and from Item 3 of the induction hypothesis for
i − 1.
For every i with (e + 1) | i (and in particular for i = 0), Item 2 follows from Step 11 of the algorithm.
For other i, Li,xx is obtained from Li−1,xx in Step 13 of the algorithm. Suppose R0 (Y ) is a polynomial of
degree at most d − i such that ∆(R0 , ri,xx ) ≤ t j . Consider the polynomial R(Y ) = R0 (Y ) − Qi−1 (xx)Y d−i+1
which is of degree at most d − i + 1. We will show that R(Y ) ∈ Li−1,xx , and then Step 13 of the algorithm
will put R0 (Y ) into Li,xx . By construction,
∆(R, ri−1,xx ) = ∆(R0 (Y ) − Qi−1 (xx)Y d−i+1 , ri−1,xx )
= ∆(R0 (Y ), ri−1,xx + Qi−1 (xx)Y d−i+1 )
= ∆(R0 , ri,xx )
≤ tj .
This, along with the induction hypothesis for i − 1, implies that R(Y ) ∈ Li−1,xx ), as desired.
Now we discuss Item 3. Let j = bi/(e + 1)c. If Item 2 holds for some i, then using the fact that
n − d + j · (e + 1) n − d + j · (e + 1) + 2cn n − d + j · (e + 1) + e n − d + i
tj = + cn = > ≥ ,
2 2 2 2
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 29
J OHN Y. K IM AND S WASTIK KOPPARTY
Algorithm 5 FastRMDecoder: Fast decoding of general Reed–Muller codes
1: Input: r : Sm → F.
2: Let c = ((1 − α)2 /8).
3: Let e = b2cnc.
4: for i = 0, 1, . . . , d do
5: Define ri : Sm−1 × S → F by
i−1
X ,Y ) = r(X
ri (X X )Y d−` .
X ,Y ) − ∑ Q` (X
`=0
6: for x ∈ Sm−1 do
7: Define ri,xx : S → F by ri,xx (Y ) = ri (xx,Y ).
8: if (e + 1) | i then
i
9: Let j = e+1 .
n−d+i
10: Let t j = 2 + cn.
11: Define Li,xx = FastRSListDecoder(ri,xx , d − i,t j ).
12: else
13: Define Li,xx = {R(Y ) − Qi−1 (xx)Y d−i+1 | R(Y ) ∈ Li−1,xx , CoeffY d−i+1 (R) = Qi−1 (xx)}.
14: end if
15: Define Gx (Y ) ∈ F[Y ] to be the unique element (if any) of the list Li,xx with degree at
most d − i and ∆(Gx , ri,xx ) < (n − d + i)/2
16: if Gx 6= ⊥: then
17: σx = CoeffY d−i (Gx ).
18: δx = ∆(Gx , ri,xx ).
19: else
20: σx = 0.
21: δx = n.
22: end if
23: end for
24: Define the weighted function fi : Sm−1 → F × [0, 1] by
δx
fi (xx) = σx , min 1, .
(n − d + i)/2
25: Define √
(i + 10(m − 1) n)(d − i)
ei = .
n − (d − i)
26: X ) ∈ F[X1 , . . . , Xm ] by
Obtain the polynomial Qi (X
X ), i, n−2m ) .
X ) = FastWeightedRMDecoderei ( fi (X
Qi (X
27: end for
28: Output: ∑di=0 Qi (X
X )Y d−i .
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 30
D ECODING R EED –M ULLER C ODES OVER P RODUCT S ETS
we conclude that Gx (Y ) is the unique polynomial in F[Y ] (if any) of degree at most d − i with
n−d +i
∆(Gx , rx ,i ) < .
2
Thus the Gx produced in Step 15 of Algorithm 5 is the same as the corresponding Gx in Algorithm 2.
This implies that the function fi in Algorithm 2 and Algorithm 5 are the same.
We will now show that
√
1 i + 10(m − 1) n
∆( fi , Pi ) < 1− · nm−1 . (6.2)
2 n−d +i
By induction, we may assume that we have already shown that P` = Q` for each ` ∈ {0, 1, . . . , i − 1}.
Letting
d
X )Y d− j ,
X ,Y ) = ∑ Pj (X
Ci (X
j=i
we get that ∆(ri ,Ci ) = ∆(r,C). Following the same calculation as in (4.5), we have the following
inequalities.
∆(ri ,Ci )
∆( fi , Pi ) <
n−d +i
∆(r,C)
=
n−d +i
1 10(m−1)
2 (1 − α −
√
n
)nm
≤
n−d +i
√
1 n − d − 10(m − 1) n m−1
≤ ·n
2 n−d +i
√
1 i + 10(m − 1) n
= 1− · nm−1 .
2 n−d +i
This completes the proof of Inequality (6.2).
Now we study what happens in the invocation of FastWeightedRMDecoder in Step 26 of the
algorithm. To do this, we need to compute the radius Λi to which the decoder FastWeightedRMDecoderei
in Step 26 will decode. Recall that
√
(i + 10(m − 1) n)(d − i)
ei = .
n − (d − i)
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 31
J OHN Y. K IM AND S WASTIK KOPPARTY
Thus we have
√
1 m−1 i 10(m − 1) n + ei
Λi = n 1− −
2 n n
√
1 m−1 i 10(m − 1) n i(d − i)
≥ n 1− − −
2 n n (n − (d − i))n
√ √
1 m−1 i(n − (d − i)) + 10(m − 1)(n − (d − i)) n + (i + 10(m − 1) n)(d − i)
= n 1−
2 n(n − (d − i))
√
1 in + 10(m − 1)n n
= nm−1 1 −
2 n(n − (d − i))
√
1 m−1 i + 10(m − 1) n
= n 1− .
2 n − (d − i)
Combining this with Inequality (6.2), we see that Λi > ∆( fi , Pi ). This implies that the invocation of
FastWeightedRMDecoder in Step 25 will return Pi , and thus Qi = Pi . This completes the proof of the
inductive step.
Now that we have shown that for all i we have Qi = Pi , we can conclude that the output of the
X ,Y ), as desired.
algorithm is indeed C(X
Analysis of running time. All the invocations of FastWeightedRMDecoder to decode the fi over the
d + 1 values of i take time O(nm polylog(n)) in total, following the exact same running-time analysis
from Theorem 6.2. Now we analyze the time required to construct the fi . This involves a total of
d
nm−1 · = O(nm−1 )
e+1
invocations of FastRSListDecoder, along with some other simpler operations. The total running time for
this part is thus also O(nm polylog(n)).
7 Open problems
We conclude with some open problems.
1. The problem of list-decoding Reed–Muller codes over general product sets Sm up to the Johnson
radius is a very interesting open problem left open by our work. Again, when S is algebraically
special, it is known how to solve this problem [15]. Generalizing our approach seems to re-
quire progress on another very interesting open problem, that of list-decoding Reed–Solomon
concatenated codes. See [6] for the state of the art on this problem.
2. It would be interesting to understand the relationship between our algorithms and the m + 1-variate
interpolation-based list-decoding algorithm of Sudan [20]. Their decoding radii are incomparable,
and perhaps there is some insight into the polynomial method, which is known to face some
difficulties in > 2 dimensions, that can be gained here.
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 32
D ECODING R EED –M ULLER C ODES OVER P RODUCT S ETS
3. It would be interesting to see if one can decode multiplicity codes [11] on arbitrary product sets
Sm up to half their minimum distance. Here too, we know algorithms that decode up to half the
minimum distance only in the case when S is very algebraically special (from [10]), or if the degree
d is very small compared to |S| (via an m + 1-variate interpolation algorithm, similar to [20]).
Acknowledgments
We are grateful to Madhu Sudan for introducing this problem to us many years ago. Many thanks to the
anonymous reviewers for very detailed comments that greatly improved the presentation.
A Decoding of Reed–Solomon codes with uncertainties
In this section, we present algorithms for decoding Reed–Solomon codes with uncertainties. We first
present Forney’s near-quadratic-time deterministic algorithm to decode Reed–Solomon codes with
uncertainties up to half the minimum distance. We then present a randomized near-linear-time version
of that algorithm that decodes Reed–Solomon codes with uncertainties up to almost half the minimum
distance.
Lemma A.1. Let F be a finite field and let S ⊆ F be a nonempty subset of size |S| = n.
There is a deterministic algorithm WeightedRSDecoder which, given a weighted received word
w : S → F × [0, 1], finds the unique polynomial (if any) C ∈ F[X] satisfying
n−d
deg(C) ≤ d and ∆(w,C) <
2
in time O(n2 poly(log(n), log(1/γ))).
Proof. We first present a randomized algorithm, and then we show how to derandomize it.
Let r : S → F and u : S → [0, 1] be the components of w.
The randomized algorithm is based on randomly rounding the weighted received word w to an “errors
and erasures” received word (i. e., a word r0 : S → F ∪ {?}, where ? denotes erasure).
Concretely, for each x ∈ S, the algorithm decides to make r0 (x) = r(x) with probability 1 − u, and
decides to make r0 (x) =? with probability u.
If C(X) is a polynomial of degree at most d with ∆(w,C) = δ , then a simple analysis shows that
E[2E + F] = 2δ ,
where E is the number of errors (= the number of x with r0 (x) 6= C(x) and r0 (x) 6=?) and F is the number
of erasures (= the number of x with r0 (x) =?).
Furthermore, this holds even if the random choices in the construction of r0 are made in the following
correlated way: we first pick p ∈ [0, 1] uniformly at random, and then we set r0 (x) =? if and only if
p ≤ u(x), and we set r0 (x) = r(x) otherwise.
Thus there is a choice of p ∈ [0, 1] (and in fact p ∈ {u(x) : x ∈ S} ∪ {0, 1}) such that the resulting
function r0 has 2E + F ≤ 2δ .
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 33
J OHN Y. K IM AND S WASTIK KOPPARTY
Finally, a standard fast Reed–Solomon decoding algorithm, such as FastRSDecoder, can decode
Reed–Solomon codes of degree d when
2 · (num errors) + (num erasures) < n − d .
This uses the fact that erasures can be thought of as changing the domain S to a subset of S.
To make this algorithm deterministic, we simply cycle over all choices of p ∈ {u(x) : x ∈ S} ∪ {0, 1}
and consider the corresponding r0 . There are at most O(n) such choices of p, and this gives us the desired
algorithm and running time. For details, see Forney [7].
The faster randomized variant simply augments Forney’s randomized decoding algorithm with a
variance analysis to show that it succeeds with high probability (provided ∆(w,C) is somewhat smaller
than half the minimum distance of the Reed–Solomon code).
Lemma A.2. Let F be a finite field and let S ⊆ F be a nonempty subset of size |S| = n.
There is a randomized algorithm FastWeightedRSDecoder which, given a weighted received word
w : S → F × [0, 1], finds the unique polynomial (if any) C ∈ F[X] satisfying
√
n − d − 10 n
deg(C) ≤ d and ∆(w,C) <
2
with probability 1 − γ in time O(n poly(log(n), log(1/γ))).
Proof. The algorithm is given in Algorithm 6.
For a given weighted received word w : S → F × [0, 1], with w = (r, u), suppose there is a polynomial
C of degree at most d such that √
n−d − n
∆(w,C) < .
2
We will show how to design such an algorithm with success probability 2/3. This can be amplified to
1 − γ by repeating O(log 1/γ) times.
Algorithm 6 Fast Reed–Solomon Decoding with Uncertainties
1: Input: w : S → F × [0, 1].
2: Let r : S → F, u : S → [0, 1] be the components of w.
3: for x ∈ S do
4: Pick px ∈ [0, 1] uniformly at random.
5: Define r0 : S → F ∪ {?} by
(
0 r(x) if px ≤ u(x) ,
r (x) =
? if px > u(x) .
6: end for
7: g = FastRSDecoder(r0 , d).
8: Output: g.
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 34
D ECODING R EED –M ULLER C ODES OVER P RODUCT S ETS
As before, we have E[2E + F] < n − d.
We will use Chebyshev’s inequality to show that 2E + F < n − d with probability at least 3/4. To
help us compute the expectation and variance of 2E + F, we write E and F as a sum of indicator random
variables. Let A = {x ∈ S | C(x) = r(x)} be the set of agreeing indices, and let D = {x ∈ S | r(x) 6= C(x)}
be the set of disagreeing indices. Let T = {x ∈ X | r0 (x) =?} be the set of erasure indices.
Then we can write
E = ∑ 1x∈T
/ ,
x∈D
F = ∑ 1x∈T .
x∈S
√
We then can show E[2E + F] is less than n − d by a significant amount n:
E[2E + F] = 2 ∑ (1 − u(x)) + ∑ u(x)
x∈D s∈X
= 2 ∑ (1 − u(x)) + ∑ u(x) + ∑ u(x)
x∈D x∈D x∈A
!
u(x) u(x)
= 2 ∑ 1− +∑
x∈D 2 x∈A 2
= 2∆(w,C)
√
< n − d − 10 n .
Finally, we show that Var(2E + F) is small:
Var(2E + F)
= 4 Var(E) + 4 Cov(E, F) + Var(F)
" # !
= 4 ∑ u(x)(1 − u(x)) + 4 E / ∧y∈T − ∑ (1 − u(x)) ∑ u(y) + ∑ u(y)(1 − u(y))
∑ ∑ 1x∈T
x∈D x∈D y∈S x∈D y∈S y∈S
" # !
= 4 ∑ u(x)(1 − u(x)) + 4 E ∑ ∑ (1 − u(x))u(y) − ∑ ∑ (1 − u(x))u(y) + ∑ u(y)(1 − u(y))
x∈D x∈D y6=x x∈D y∈S y∈S
= 4 ∑ u(x)(1 − u(x)) − 4 ∑ u(x)(1 − u(x)) + ∑ u(y)(1 − u(y))
x∈D x∈D y∈S
= ∑ u(y)(1 − u(y))
y∈S
n
≤ .
4
By Chebyshev’s inequality, Pr(2E + F ≥ n − d) ≤ 1/4. Hence we have Pr(2E + F < n − d) ≥ 3/4.
That is, with probability at least 3/4, the algorithm outputs C.
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 35
J OHN Y. K IM AND S WASTIK KOPPARTY
References
[1] M IKHAIL A LEKHNOVICH: Linear diophantine equations over polynomials and soft decoding of
Reed–Solomon codes. IEEE Trans. Inform. Theory, 51(7):2257–2265, 2005. Preliminary version in
FOCS’02. [doi:10.1109/TIT.2005.850097] 9, 18
[2] L ÁSZLÓ BABAI , L ANCE F ORTNOW, L EONID L EVIN , AND M ARIO S ZEGEDY: Checking
computations in polylogarithmic time. In Proc. 23rd STOC, pp. 21–31. ACM Press, 1991.
[doi:10.1145/103418.103428] 4
[3] Y UVAL C ASSUTO AND J EHOSHUA B RUCK: A combinatorial bound on the list size. Technical
Report ETR 058, Paradise Laboratory, 2004. Avaliable at CalTech Library. 18
[4] PARIKSHIT G OPALAN , V ENKATESAN G URUSWAMI , AND P RASAD R AGHAVENDRA: List decod-
ing tensor products and interleaved codes. SIAM J. Comput., 40(5):1432–1462, 2011. Preliminary
version in STOC’09. [doi:10.1137/090778274] 5
[5] V ENKATESAN G URUSWAMI AND M ADHU S UDAN: Improved decoding of Reed-Solomon and
algebraic-geometric codes. IEEE Trans. Inform. Theory, 45(6):1757–1767, 1999. Preliminary
version in FOCS’98. [doi:10.1109/18.782097] 4, 9
[6] V ENKATESAN G URUSWAMI AND M ADHU S UDAN: Decoding concatenated codes using soft
information. In Proc. 17th IEEE Conf. on Computational Complexity (CCC’02), pp. 148–157. IEEE
Comp. Soc. Press, 2002. [doi:10.1109/CCC.2002.1004350] 32
[7] G EORGE DAVID F ORNEY J R .: Generalized minimum distance decoding. IEEE Trans. Inform.
Theory, 12(2):125–131, 1966. [doi:10.1109/TIT.1966.1053873] 5, 8, 34
[8] TADAO K ASAMI , S HU L IN , AND W ILLIAM W ESLEY P ETERSON: Polynomial codes. IEEE Trans.
Inform. Theory, 14(6):807–814, 1968. [doi:10.1109/TIT.1968.1054226] 4
[9] J OHN Y. K IM AND S WASTIK KOPPARTY: Decoding Reed-Muller codes over product sets. In
Proc. 31st Conf. on Computational Complexity (CCC’16), volume 50 of Leibniz Internat. Proc.
in Informatics (LIPIcs), pp. 11:1–28. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016.
[doi:10.4230/LIPIcs.CCC.2016.11] 1
[10] S WASTIK KOPPARTY: List-decoding multiplicity codes. Theory of Computing, 11(5):149–182,
2015. [doi:10.4086/toc.2015.v011a005] 33
[11] S WASTIK KOPPARTY, S HUBHANGI S ARAF, AND S ERGEY Y EKHANIN: High-rate codes with
sublinear-time decoding. J. ACM, 61(5):28:1–28:20, 2014. Preliminary version in STOC’11.
[doi:10.1145/2629416] 3, 33
[12] F LORENCE J ESSIE M AC W ILLIAMS AND N EIL J. A. S LOANE: The Theory of Error-Correcting
Codes. Elsevier/North-Holland, Amsterdam, New York, 1981. 3, 8
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 36
D ECODING R EED –M ULLER C ODES OVER P RODUCT S ETS
[13] JAMES L EE M ASSEY: Shift-register synthesis and BCH decoding. IEEE Trans. Inform. Theory,
15(1):122–127, 1969. [doi:10.1109/TIT.1969.1054260] 3
[14] DAVID E UGENE M ULLER: Application of boolean algebra to switching circuit de-
sign and to error detection. IEEE Trans. on Computers, EC-3(3):6–12, 1954.
[doi:10.1109/IREPGELC.1954.6499441] 2
[15] RUUD P ELLIKAAN AND X IN -W EN W U: List decoding of q-ary Reed-Muller codes. IEEE Trans.
Inform. Theory, 50(4):679–682, 2004. [doi:10.1109/TIT.2004.825043] 4, 32
[16] W ILLIAM W ESLEY P ETERSON: Encoding and error-correction procedures for Bose-Chaudhuri
codes. IEEE Trans. Inform. Theory, 6(4):459–470, 1960. [doi:10.1109/TIT.1960.1057586] 3
[17] I RVING S TOY R EED: A class of multiple-error-correcting codes and the decoding scheme. IEEE
Trans. Inform. Theory, 4(4):38–49, 1954. [doi:10.1109/TIT.1954.1057465] 2
[18] I RVING S TOY R EED AND G USTAV S OLOMON: Polynomial codes over certain finite fields. J. Soc.
Indust. Appl. Math., 8(2):300–304, 1960. [doi:10.1137/0108018] 2
[19] RONNY ROTH AND G ITIT RUCKENSTEIN: Efficient decoding of Reed-Solomon codes beyond half
the minimum distance. IEEE Trans. Inform. Theory, 46(1):246–257, 2000. Preliminary version in
ISIT’98. [doi:10.1109/18.817522] 9
[20] M ADHU S UDAN: Decoding of Reed Solomon codes beyond the error-correction bound. J. Com-
plexity, 13(1):180–193, 1997. Preliminary version in FOCS’96. [doi:10.1006/jcom.1997.0439] 4, 9,
32, 33
[21] L LOYD R ICHARD W ELCH AND E LWYN R ALPH B ERLEKAMP: Error correction of algebraic block
codes. US Patent Number 4,633,470, December 1986. URL: www.google.com/patents/US4633470.
3
AUTHORS
John Y. Kim
Trader
Virtu Financial
Austin, TX
jonykim gmail com
http://www.math.rutgers.edu/~jonykim/
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 37
J OHN Y. K IM AND S WASTIK KOPPARTY
Swastik Kopparty
Associate professor
Department of Mathematics & Department of Computer Science
Rutgers University
swastik kopparty gmail com
http://www.math.rutgers.edu/~sk1233/
ABOUT THE AUTHORS
J OHN Y. K IM received his Ph. D. from Rutgers University in 2016 under the guidance of
his advisor Swastik Kopparty. He currently trades commodities at Virtu Financial, an
electronic market-making firm. He once considered a career in professional table tennis,
but gave it up after losing in spectacular fashion to his advisor.
S WASTIK KOPPARTY got his his Ph. D. from M.I.T. in 2010; his advisor was Madhu Sudan.
He was a postdoc at I.A.S. during 2010-2011, and has been on the faculty at Rutgers ever
since. His research interests are in complexity theory, coding theory, algebraic methods,
randomness and pseudorandomness. He is addicted to cappuccinos and, recently, table
tennis.
T HEORY OF C OMPUTING, Volume 13 (21), 2017, pp. 1–38 38