Abstract 1 Introduction 2 Preliminaries 3 Fast construction of differential equation 4 List-recovery algorithm for multiplicity codes References

Fast List Recovery of Univariate Multiplicity Codes

Rohan Goyal ORCID Massachusetts Institute of Technology, Cambridge, MA, USA    Prahladh Harsha ORCID Tata Institute of Fundamental Research, Mumbai, India    Mrinal Kumar ORCID Tata Institute of Fundamental Research, Mumbai, India    Ashutosh Shankar ORCID Tata Institute of Fundamental Research, Mumbai, India
Abstract

Recent work gave near-linear time algorithms for list decoding Folded Reed–Solomon codes and univariate multiplicity codes up to capacity in their natural parameter regimes. Unlike most known list decoding algorithms, these techniques appeared inherently tied to list decoding, and it was unclear whether they could be extended to list recovery in near-linear time.

In this work, we resolve this question by giving O~⁢(n)-time algorithms for list recovery of Folded Reed–Solomon codes and univariate multiplicity codes up to capacity, where n is the block length. Our algorithms build on the lattice-based framework of the prior work, augmented with a new technical ingredient: the construction of suitably structured lattices over the univariate polynomial ring that capture the list recovery problem for these codes.

Keywords and phrases:
list-recovery, multiplicity-codes, near-linear-algorithm
Category:
RANDOM
Funding:
Rohan Goyal: Supported by (Yael Tauman Kalai’s) grant from Defense Advanced Research Projects Agency (DARPA) ††margin: [Uncaptioned image] under Contract No. HR0011-25-C-0300. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the Defense Advanced Research Projects Agency (DARPA).
Prahladh Harsha: Supported by the Department of Atomic Energy††margin: [Uncaptioned image] , Government of India, under project number RTI400112 and in part by a Google research grant††margin: [Uncaptioned image] .
Mrinal Kumar: Supported by the Department of Atomic Energy, Government of India, under project number RTI400112, and in part by research grants from Google, SERB††margin: [Uncaptioned image] and Premji Invest††margin: [Uncaptioned image] .
Ashutosh Shankar: Supported by the Department of Atomic Energy, Government of India, under project number RTI400112.
Copyright and License:
[Uncaptioned image] © Rohan Goyal, Prahladh Harsha, Mrinal Kumar, and Ashutosh Shankar; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation → Error-correcting codes
; Theory of computation → Design and analysis of algorithms
Related Version:
Full Version: https://arxiv.org/abs/2512.00248
Editors:
Mohit Singh and Tom Gur

1 Introduction

An error-correcting code 𝒞⊆Σn is said to be (η,L) list decodable if every Hamming ball of radius η⁢n in Σn contains at most L codewords of 𝒞. When η<δ/2, where δ is the minimum distance of the code, we are in the unique decoding regime, in which at most one codeword lies in such a ball. List decoding is of fundamental interest both from a combinatorial perspective, where one studies tradeoffs between parameters such as η, L, δ, and the rate of the code, and from an algorithmic perspective, where the goal is to design efficient decoding algorithms for increasingly large values of η. Since Sudan’s breakthrough work showing that Reed–Solomon codes can be efficiently list decoded beyond the unique decoding radius [19], there has been substantial progress in our understanding of list decoding, culminating in explicit codes that achieve list decoding capacity with constant list size [9, 8, 10, 14, 15, 17, 5, 11] and, in several cases, near-linear time decoding algorithms [6, 2, 18]. Beyond coding theory, list decoding has deep and fruitful connections to complexity theory and pseudorandomness, including randomness extraction and hardness amplification [21].

Our focus in this paper is on the related notion of list recovery. A code 𝒞⊆Σn is said to be (η,ℓ,L) list recoverable if for all subsets E1,…,En⊆Σ with |Ei|≤ℓ, there are at most L codewords c∈𝒞 such that ci∉Ei for at most η⁢n coordinates i∈[n]. Clearly, the case ℓ=1 recovers the definition of list decoding. List recovery has attracted considerable attention both because of its close connection to list decoding and because of its numerous applications, including the construction of pseudorandom objects such as extractors and expanders, cryptographic constructions, and algorithmic problems such as group testing and compressed sensing. We refer the reader to the survey of Resch and Venkitesh [16] and the lecture notes of Wootters [23] for further background.

A notable feature of many list decoding algorithms is that they naturally extend to the more general setting of list recovery. This phenomenon holds for the classical Sudan and Guruswami–Sudan algorithms for Reed–Solomon codes [19, 9], for algorithms achieving capacity for Folded Reed–Solomon (FRS) and (univariate and multivariate) multiplicity codes [8, 10, 14, 15, 3, 4], as well as for recent results on expander-based codes approaching list decoding capacity [11, 18, 12]. Consequently, one might expect fast list decoding algorithms to extend automatically to fast list recovery.

A central direction in the study of list decoding and list recovery is the design of near-linear time algorithms. This includes both the construction of codes admitting such fast decoding algorithms and the development of efficient algorithms for several well-studied and natural code families. A key milestone in this direction is the work of Alekhnovich [1], which gave a near-linear time algorithm for list decoding (and list recovery) Reed–Solomon codes up to the Johnson radius. Alekhnovich’s algorithm can be viewed as a fast implementation of the Guruswami–Sudan algorithm that exploits natural connections between polynomial interpolation-based decoding algorithms and lattices over the univariate polynomial ring. More recently, a lattice-based framework building on these ideas was used to obtain near-linear time list decoding algorithms up to capacity for FRS codes and univariate multiplicity codes [6]. In addition, this work developed fast algorithms for solving certain families of differential and functional equations that arise naturally in this context.

Perhaps surprisingly, the techniques underlying these near-linear time list decoding results do not appear to extend directly to the setting of list recovery. This obstruction already arises for ℓ=2, and stands in contrast to the behavior of most known list decoding algorithms. In this work, we show that this limitation can in fact be overcome111In this paper we focus on univariate multiplicity codes. We believe our results extend to FRS codes and defer that case to the full version..

Informally, our main result gives a near-linear time algorithm for list recovery up to capacity. In the standard parameter regime for univariate multiplicity codes, where the list-size parameter ℓ, the error parameter ε, and the multiplicity parameter s are treated as constants, the running time of our algorithm is O~⁢(n).

More formally, we prove the following theorem.

Theorem 1 (main result for multiplicity codes).

For every ε>0 and ℓ∈ℕ, there exists s0=Θ⁢(ℓ/ε2)∈ℕ such that for all s>s0, degree parameter k, block length n, and fields 𝔽 of characteristic zero or characteristic greater than k, satisfying k<n⁢s, the following holds. There is a randomized algorithm that, given a set S⊆𝔽 of size n and sets Eα⊆𝔽s with |Eα|≤ℓ for each α∈S, takes

O⁢(n⋅𝗉𝗈𝗅𝗒⁢(s,ℓ,log⁡n,(ℓ/ε)1+log⁡ℓε))

field operations and with high probability outputs all univariate polynomials f⁢(X)∈𝔽⁢[X] of degree less than k such that for at least (ks⁢n+ε) fraction of α∈S,

(f⁢(α),f(1)⁢(α),…,f(s−1)⁢(α))∈Eα.

1.1 An overview of the proof

We give a high-level overview of the proof, focusing on the list-recovery problem for univariate multiplicity codes. Our algorithm follows the same two-step structure as prior near-linear time list-decoding algorithms, but the interpolation step requires a fundamentally new construction.

The input to the list-recovery problem consists of a set S⊆𝔽 of size n, where each α∈S is associated with a list {β⁢(α)j}j∈[ℓ] of s-tuples in 𝔽s. As in the list-decoding setting, we refer to this input as the received word.

We begin by recalling the structure of the near-linear time list-decoding algorithm of [6], which is a fast implementation of the algorithm of Guruswami and Wang [10]. This algorithm has two main components:

  • ■

    Interpolation via a differential equation. One constructs, for an appropriately chosen parameter m=Θ⁢(s), a nonzero polynomial Q⁢(X,Y0,…,Ym)=Q~⁢(X)+∑iQi⁢(X)⁢Yi, linear in the Y-variables and of bounded degree, such that every polynomial f whose encoding agrees sufficiently with the received word satisfies the differential equation:

    Q⁢(X,f⁢(X),f(1)⁢(X),…,f(m)⁢(X))≡0.
  • ■

    Solving the differential equation. The solution space of this linear differential equation is an affine space of dimension at most m. A near-linear time algorithm computes a basis for this space, followed by a pruning step [15, 20] to recover the constant-sized list of close enough codewords.

The fast list-recovery algorithm in this paper follows the same high-level outline. This is consistent with the polynomial-time list-recovery algorithm of Guruswami and Wang [10], where the list-decoding and list-recovery procedures are structurally identical, differing only in parameter settings.

To extend the results of [6] to the list-recovery setting, we use the fast differential equation solver from [6] as is. The main new ingredient is in the first step: constructing an appropriate differential equation in near-linear time.

We briefly recall the relevant interpolation framework from [6]. In the list-decoding setting, each α∈S is associated with a unique received vector β⁢(α). The algorithm constructs in near-linear time univariate polynomials A0⁢(X),A1⁢(X),…,Am⁢(X) satisfying (Ai)(j)⁢(α)=β⁢(α)(i+j) for all α∈S, i∈[m],j∈[s−m]. One then considers the 𝔽⁢[X]-module (lattice) of polynomials in X,Y0,…,Ym generated by

{Yi−Ai⁢(X):i∈[m]}∪{∏α∈S(X−α)s−m}. (1)

This lattice has the property that any nonzero element of this lattice of sufficiently small degree yields a polynomial Q⁢(X,Y0,…,Ym)=Q~⁢(X)+∑iQi⁢(X)⁢Yi such that every polynomial f whose encoding agrees with the received word on sufficiently many α’s satisfies

Q⁢(X,f,f(1),…,f(m))≡0.

In [6], existence of such a “short” nonzero lattice element is proved via an analogue of Minkowski’s theorem, and it is found in near-linear time using Alekhnovich’s algorithm for shortest vectors (with respect to the degree norm) in polynomial lattices. The “short” guarantee here matches that [10] achieve via variable and constraint counting.

The difficulty in moving to list recovery is that each α now comes with ℓ candidate vectors β⁢(α)1,…,β⁢(α)ℓ, so the received word is no longer a function α↦β⁢(α). In particular, the definition of the polynomials Ai above breaks down. A natural attempt is to arbitrarily “split” the input into ℓ received words in the list-decoding sense: for t∈[ℓ], let rt=(α,β⁢(α)t)α∈S, and construct the corresponding polynomials At,0,…,At,m. One could then try to work with the lattice generated by products such as ∏t=1ℓ(Yj−At,j⁢(X)) (over 𝔽⁢[X]), thereby capturing the disjunction “Yj matches one of the ℓ possibilities.” However, this immediately leads to polynomials Q with Y-degree ℓ, and hence to nonlinear differential equations. This is the main obstacle. Even if one could find such a low-degree Q in near-linear time, it is unclear how to solve the resulting nonlinear differential equation and recover all close codewords efficiently: the solution set need not be an affine subspace, and the linear-algebraic techniques of [6] do not apply. While high Y-degree interpolation is standard in other contexts (e.g., [19, 9, 1, 14, 13]), we do not know how to make this approach work here222Note that the Guruswami–Sudan list-decoding algorithm, and Alekhnovich’s near-linear time implementation thereof, already employ a Y-degree larger than one; consequently, Alekhnovich’s approach readily extends to list recovery..

Motivated by this, it is natural to insist on keeping Q linear in the Y-variables even in the list-recovery setting. Guruswami and Wang show that this can be done in polynomial time. Our main technical contribution is to show that it can in fact be done in near-linear time: we construct a carefully structured lattice over 𝔽⁢[X] whose generators are linear in Y0,…,Ym, and whose short nonzero vectors correspond precisely to linear differential equations that capture all close codewords. In the list-decoding setting the received word is a function α↦β⁢(α) leading to an almost-diagonal basis of the form (1) for the resulting (m+1)-dimensional lattice. In list recovery, the received word no longer has such a functional structure and hence one cannot expect the resulting lattice to admit a similar simple basis. What we show is the next best thing: there exists a lattice whose basis has a structured almost-triangular form, which is sufficient for computing short nonzero vectors efficiently and for deriving the required linear differential equation. The basis we obtain has the following form.

∏α∈S(X−α)s−m,
Yi⋅∏α∈S(X−α)s−m, ∀i, such that ⁢0≤i≤ℓ−2
Ci~⁢(X)+∑r=0i−1Yr⋅Ci,r⁢(X)+Yi⋅∏α∈S(X−α)ℓ−1, ∀i, such that ⁢ℓ−1≤i≤m

for some polynomials Ci~,Ci,r∈𝔽⁢[X] for ℓ−1≤i≤m and 0≤r≤i−1. The proof that such a basis exists is considerably involved. We first show that such an almost-triangular basis exists for each α∈S and then combine the almost-triangular bases for the different α to obtain the basis of the above type using the Chinese remainder theorem. See Section 3 for details.

Organization

The rest of this paper is organized as follows. Section 2 introduces univariate multiplicity codes and the subroutines used in the lattice construction. Section 3 gives the fast lattice construction and the resulting differential equation. Setting up this lattice is the key novelty of the paper. Section 4 describes the list-extraction procedure from the differential equation, completing the proof of Theorem 1.

2 Preliminaries

2.1 Notation

  • ■

    We work in some fixed finite field 𝔽.

  • ■

    For a natural number N, we will use [N] to refer to the set {0,1,2,…,N−1}.

  • ■

    We use 𝟎k to denote the k-length zero vector. We may drop the subscript if the length is clear from context.

2.2 Univariate multiplicity codes

We recall the formal definition of the univariate multiplicity code.

Definition 2 (Multiplicity codes).

Let n,k,s be positive integers satisfying k<n⁢s, 𝔽 be a field of characteristic zero or at least s and size at least n, and let S={α1,α2,…,αn} be a set of n distinct elements of 𝔽. Then, the univariate multiplicity code with multiplicity parameter s and degree parameter k is defined as follows.

The alphabet of the code is E=𝔽s and the block length is n=|S|, where the coordinates of a codeword are indexed by α∈S. The message space is the set of all univariate polynomials of degree less than k in 𝔽⁢[x]. The encoding of such a message f∈𝔽⁢[x], denoted by 𝖬𝗎𝗅𝗍s⁢(f)∈ES is defined as

𝖬𝗎𝗅𝗍s⁢(f)|α:=(f⁢(α),f(1)⁢(α),…,f(s−1)⁢(α)),

where f(j)⁢(α) is the evaluation of the jt⁢h-order derivative333This definition in terms of (standard) derivatives requires the characteristic of the field to be 0 or at least k. All known capacity-achieving list-decoding results for univariate multiplicity codes require large characteristic (previous works [14, 10, 15, 6] as well as our work). For this reason as well as ease of presentation, we work with standard derivatives. of f on the input α. The rate of this code is k/n⁢s while the distance is 1−(k−1)/n⁢s.

In the list-recovery setting, the received word R assigns to every evaluation point α∈S a collection of tuples β⁢(α)j=(β⁢(α)j(0),β⁢(α)j(1),…,β⁢(α)j(s−1)) for every j∈[ℓ]. In words β⁢(α)j(i) is the jt⁢h option for the it⁢h derivative of the message polynomial at α. Agreement is with respect to inclusion in this list; that is, 𝖬𝗎𝗅𝗍⁢(f) agrees with R on point α if there exists j∈[ℓ] such that (f⁢(α),f(1)⁢(α),…,f(s−1)⁢(α))=β⁢(α)j=(β⁢(α)j(0),β⁢(α)j(1),…,β⁢(α)j(s−1)).

Our goal is to carry out list recovery from an agreement fraction of k/n⁢s+ε, for a given parameter ε.

2.3 Polynomial operators and lattices

We recall below the τ operator, used in [10, 13], and [6].

Definition 3 (Tau operator).

Let s∈ℕ be a parameter. Then, for every m such that 0≤m<s, the function τ is an 𝔽-linear map from the set of polynomials in 𝔽⁢[X,Y0,Y1,…,Ym] with 𝐘-degree 1 to the set of polynomials in 𝔽⁢[X,Y0,Y1,…,Ym+1] with 𝐘-degree 1 and is defined as follows.

τ⁢(Q~⁢(X)+∑i=0mQi⁢(X)⋅Yi):=Q~(1)⁢(X)+∑i=0m(Qi(1)⁢(X)⋅Yi+Qi⁢(X)⋅Yi+1).

For an integer i≤(s−m−1), we use τ(i) to denote the linear map from 𝔽⁢[X,Y0,Y1,…,Ym] to 𝔽⁢[X,Y0,Y1,…,Ym+i] obtained by applying the operator τ iteratively i times.

The operator is defined this way so that

dd⁢X⁢Q⁢(X,f⁢(X),f(1)⁢(X),…,f(m)⁢(X))=τ⁢Q⁢(X,f⁢(X),f(1)⁢(X),…,f(m+1))⁢(X).

It will be convenient to view polynomials in 𝔽⁢[X,Y0,…,Ym+i] for i≤s−m−1 as polynomials in 𝔽⁢[X,Y0,…,Ys−1]. Thus, when evaluating a polynomial R∈𝔽⁢[X,Y0,…,Ym+i−1] at the point (α,β)∈𝔽s+1, R⁢(α,β) refers to R⁢(α,β[m+i])=R⁢(α,β0,…,βm+i−1).

We will extensively use the following simple property of the τ operator.

Proposition 4.

Let α be a field element and β=(β0,…,βi,…,βs−1)∈𝔽s. Then, for any integer j with 1≤j≤s−m,

τ(j)⁢[(X−α)⁢Q]⁢(α,β)=j⁢τ(j−1)⁢(Q)⁢(α,β).

Proof.

We prove this by induction on j. When j=1, the left-hand side is τ⁢[(X−α)⁢Q]⁢(α,β). From the definition, this equals [(X−α)⁢τ⁢Q+Q]⁢(α,β). (This can be checked term by term.) The first term (X−α)⁢τ⁢Q is zero when evaluated at (α,β) leaving Q⁢(α,β) as required.

For the induction step, observe similarly that

τ(j)⁢[(X−α)⁢Q]=τ(j−1)⁢τ⁢[(X−α)⁢Q]=τ(j−1)⁢[(X−α)⁢τ⁢Q+Q]=τ(j−1)⁢[(X−α)⁢τ⁢Q]+τ(j−1)⁢Q

Evaluating at (α,β), by the induction hypothesis,

τ(j−1)⁢[(X−α)⁢τ⁢Q]⁢(α,β)+τ(j−1)⁢Q⁢(α,β)=(j−1)⁢τj−2⁢[τ⁢Q]⁢(α,β)+τ(j−1)⁢Q⁢(α,β)=(j−1)⁢τ(j−1)⁢Q⁢(α,β)+τ(j−1)⁢Q⁢(α,β)=j⁢τ(j−1)⁢Q⁢(α,β).

◀

We now define lattices and state the version of Minkowski’s theorem for polynomial lattices.

Definition 5 (polynomial lattice).

Let ℬ={𝐯1,𝐯2,…,𝐯N} be a set of m-dimensional vectors of polynomials, that is, 𝐯i∈𝔽⁢[X]m for all i. The lattice ℒℬ generated by this set over the ring 𝔽⁢[X] is the set of all linear combinations

ℒℬ:={fi⁢𝐯1+f2⁢𝐯2+⋯+fN⁢𝐯N:fi∈𝔽⁢[X]}.

A basis of a lattice is a set ℬ of vectors of polynomials such that ℬ generates the lattice in the sense of the above definition and the vectors in ℬ are linearly independent over the field 𝔽⁢(X) of rational functions over 𝔽. A basis B can be viewed as an m×ℓ matrix (the ℓ basis vectors written side by side as columns).

For a full-rank lattice (i.e., when ℓ=m), the determinant of a basis ℬ refers to the determinant of this matrix Since this quantity is independent of the choice of basis, it is also referred to as the determinant of the lattice, denoted by detℒ.

Let β=(β⁢(1),β⁢(2),…,β⁢(m))∈𝔽⁢[X]m be a vector of polynomials. We define the max-degree norm as follows β:=maxj∈[m]⁡deg⁡β⁢(j).

Theorem 6 (polynomial version of Minkowski’s theorem).

Let ℒ be an m-dimensional polynomial lattice. Then, there is a nonzero vector 𝐯 in the lattice ℒ satisfying

deg⁡𝐯≤1m⁢deg⁢detℒ

where deg⁡𝐯 is the max-degree norm and detℒ is the determinant of the lattice basis.

A proof can be found in [6].

Theorem 7 ([1, Theorem 2.1],[7, Theorem 9]).

Let B be a set of N vectors of dimension m. Let d be the maximal degree of the polynomials which are entries of the vectors in B. Then, there is an algorithm ShortVector that finds the shortest vector in ℒB, the lattice generated by B, in time O~⁢(d⁢(N+m)ω) where ω is the exponent in the complexity of matrix multiplication.

Here “shortest vector” is in the max-degree norm. See [6] for details.

We will also use the following off-the-shelf subroutines for fast Hermite interpolation and polynomial Chinese remainders.

Theorem 8 ([22, Algorithm 10.22]).

Let m1⁢(X),m2⁢(X),…,mr⁢(X) be univariate polynomials in 𝔽⁢[x] with pairwise GCD equal to 1. Let v1⁢(X),v2⁢(X),…,vr⁢(X)∈𝔽⁢[X] such that deg⁡vi<deg⁡mi for all i∈[r]. Then, we can find the unique polynomial f⁢(X)∈𝔽⁢[X] of degree less than d=∑ideg⁡mi such that f≡vimodmi for all i∈[r], in time O⁢(d⁢𝗉𝗈𝗅𝗒⁢log⁡(d)).

3 Fast construction of differential equation

As in Guruswami–Wang, our first step is to construct an “explanation” polynomial for the received word. In this section, we show that this can be done in near-linear time. Below is the main theorem for this section.

Theorem 9.

Let R=(α,βj(0),βj(1),…,βj(s−1))α∈S,j∈[ℓ] be a received word and let m≤s−1 be a parameter.

Then, for D≤n⁢ℓ⁢(s−m)/m+n⁢ℓ, there exists a nonzero polynomial Q⁢(X,Y0,Y1,…,Ym) of the form Q=Q~⁢(X)+∑iQi⁢(X)⋅Yi of X-degree at most D with the following property: if f⁢(X)∈𝔽<k⁢[X] is such that for at least (D+k)/(s−m) values of α∈S, we have

(f⁢(α),f(1)⁢(α),…,f(s−1)⁢(α))=(βj(0),βj(1),…,βj(s−1))

for some j∈[ℓ], then,

Q⁢(X,f⁢(X),f(1)⁢(X),…,f(m)⁢(X))≡0. (2)

Furthermore, there is a deterministic algorithm that takes as input R and returns Q as a list of coefficients that carries out O~⁢(n⁢𝗉𝗈𝗅𝗒⁢(s+m+ℓ)) field operations – specifically, O~⁢(n⁢[ℓ⁢(s−m)2+m2⁢(s−m)+(s−m)⁢mω]).

A natural way to ensure that the polynomial Q satisfies (2), is to ensure that for each α∈S, we have the following conditions

τ(t)⁢(Q)⁢(α,βj0,βj1,…,βjm+t)=0,∀t∈[s−m],j∈[ℓ]. (3)

This will ensure that every close enough codeword satisfies (2) (see Lemma 14 for exact details). We will refer to these conditions as the “τ-conditions”. The set of polynomials Q satisfying (3) are closed under addition and multiplication by a polynomial in 𝔽⁢[X]. In other words, they form a 𝔽⁢[X]-module (or equivalently a lattice with entries from the univariate ring 𝔽⁢[X]). Here, it will be convenient to view the polynomial Q=Q~⁢(X)+∑iQi⁢(X)⋅Yi as an (m+2)-dimensional vector of the form (Q~,Q0,Q1,…,Qm)∈𝔽⁢[X]m+2 where the first component Q~ is the Y-free part of Q and the subsequent components are the coefficients of Y0,Y1,…,Ym respectively. To prove Theorem 9, we will first construct a structured basis for this lattice and then use Minkowski’s theorem to show that there exists a short vector in this lattice. The following proposition gives this structured basis for a sub-lattice of the lattice of polynomials satisfying the “τ-conditions”.

Proposition 10.

Let ℓ be the list size and R=(α,βj(0),βj(1),…,βj(s−1))α∈S,j∈[ℓ] be the received word and let m≤s−1 be a parameter.

Then, there exist m+2 polynomials in 𝔽⁢[X,Y0,…,Ym] satisfying the τ-conditions (3) for all α∈S of the following type

𝐁~ =∏α∈S(X−α)s−m,
𝐁i =Yi⋅∏α∈S(X−α)s−m, ∀i, such that ⁢0≤i≤ℓ−2
𝐁i =Ci~⁢(X)+∑r=0i−1Yr⋅Ci,r⁢(X)+Yi⋅∏α∈S(X−α)ℓ−1, ∀i, such that ⁢ℓ−1≤i≤m.

for some polynomials Ci~,Ci,r∈𝔽⁢[X] for ℓ−1≤i≤m and 0≤r≤i−1. Furthermore, there is a deterministic algorithm that takes as input R and returns these (m+2)-polynomials carrying out O~⁢(n⁢[ℓ⁢(s−m)2+m2⁢(s−m)]) field operations.

The analogue of Proposition 10 in the list-decoding case was easier to obtain since the conditions for all the evaluation points (i.e., α∈S) are identical. However, this is not the case when the list size ℓ is more than 1. In order to address this, we first show that a version of Proposition 10 can be proved for each α∈S and then combine these different bases for the different α into a single basis that works for all the α. The following proposition is the version of Proposition 10 for a single α∈S (which is proved in Section 3.1).

Proposition 11.

Let α∈S and ℓ be the list size and let m≤s−1 be a parameter.

Given ℓ possible evaluations (i.e., (βj(0),βj(1),…,βj(s−1)) for each j∈[ℓ]) at the point α, there exist m+2 polynomials in 𝔽⁢[X,Y0,…,Ym] satisfying the τ-conditions (3) for this specific α∈S of the following type

𝐁~α =(X−α)s−m,
𝐁α,i =Yi⋅(X−α)s−m, ∀i, such that ⁢0≤i≤ℓ−2
𝐁α,i =Ci~⁢(X)+∑r=0i−1Yr⋅Ci,r⁢(X)+Yi⋅(X−α)ℓ−1, ∀i, such that ⁢ℓ−1≤i≤m.

for some polynomials Ci~,Ci,r∈𝔽⁢[X] for ℓ−1≤i≤m and 0≤r≤i−1. Furthermore, there is a deterministic algorithm that takes as input (βj(0),βj(1),…,βj(s−1))j∈[ℓ] and returns these (m+2) polynomials, carrying out O~⁢(ℓ⁢(s−m)2) field operations.

We then show in Section 3.2 that the bases for two disjoint sets U,V of evaluation points (i.e., U,V⊆S) can be combined into a basis for the set W=U∪V in time approximately O~⁢(max⁡(|U|,|V|)). We use this procedure recursively over the bases constructed via Proposition 11 for each α∈S to obtain a basis that works simultaneously for all α∈S to yield Proposition 10.

3.1 Construction of basis for a single evaluation point

In this section, we will fix an evaluation point α∈S and construct a set of m+2 linearly independent polynomials (over the ring 𝔽⁢[X]) as specified in Proposition 11. More precisely, we want to show that there exist m+2 polynomials of the following type that satisfy the τ-conditions for α. Since α will be fixed throughout this section, we will drop α from the subscript to declutter the notation.

𝐁~ =(X−α)s−m,
𝐁i =Yi⋅(X−α)s−m, ∀i, such that ⁢0≤i≤ℓ−2
𝐁i =Ci~⁢(X)+∑r=0i−1Yr⋅Ci,r⁢(X)+Yi⋅(X−α)ℓ−1, ∀i, such that ⁢ℓ−1≤i≤m.

for some polynomials Ci~,Ci,r∈𝔽⁢[X] for ℓ−1≤i≤m and 0≤r≤i−1.

To this end, given a polynomial 𝐁 of the above form and any β=(β(0),β(1),…,β(s−1)) we will find it convenient to use the following notation for the vector in 𝔽s−m composed of evaluations of iterated τ-operator of the polynomial 𝐁 at the point (α,β):

τ⁢(𝐁,β):=τ(<s−m)⁢(𝐁)⁢(α,β)=[𝐁⁢(α,β)τ⁢(𝐁)⁢(α,β)τ(2)⁢(𝐁)⁢(α,β)⋮τ(s−m−1)⁢(𝐁)⁢(α,β)].

The linearity of the τ operator shows that the function τ⁢(⋅,⋅) is linear in its first argument.

Proof of Proposition 11.

In the notation defined above, we want to show that τ⁢(𝐁,β)=𝟎s−m for all β∈{βj:j∈[ℓ]} and each 𝐁∈{𝐁~,𝐁0,𝐁1,…,𝐁m}. Clearly, this is true when 𝐁∈{𝐁~,𝐁0,𝐁1,…,𝐁ℓ−2}. In the rest of the proof, we will construct polynomials Ci~,Ci,r∈𝔽⁢[X], such that this is also true for the polynomials 𝐁={𝐁ℓ−1,𝐁ℓ,…,𝐁m}. We will prove this by induction on ℓ, the list size.

Base case ℓ=1:

This is the list-decoding setting, where we have only β in the list corresponding to α, namely β0=(β0(0),β0(1),…,β0(s−1)). The proof in this case is similar to the corresponding step in [6], which is obtained by Hermite interpolation. For each 0≤i≤m, we define the polynomial Ci~ to be the unique (s−m−1)-degree polynomial in 𝔽⁢[X] such that for all j∈[s−m], we have

Ci~(j)⁢(α)=−β0(i+j).

The remaining Ci,r⁢(X) are set to zero for all 0≤i≤m and r∈[i]. In other words, the it⁢h polynomial 𝐁i:=Yi+C~i⁢(X) for ℓ−1=0≤i≤m. 𝐁i clearly satisfies the τ-conditions (3) for α.

Induction step ℓ≥2:

By induction, let us assume that for the first (ℓ−1) list elements βj,j∈[ℓ−1], we have polynomials 𝐁i′ satisfying the τ-conditions for α, namely τ⁢(𝐁i′,βj)=𝟎 for all i such that ℓ−2≤i≤m and j∈[ℓ−1]. We now need to construct polynomials 𝐁i for ℓ−1≤i≤m such that τ⁢(𝐁i,βj)=𝟎 for all i such that ℓ−1≤i≤m and j∈[ℓ]. Note that the number of polynomials to be constructed in the ℓ-case is one less than the (ℓ−1)-case while the number of β’s for which we need τ⁢(𝐁i,βj)=𝟎 is one more.

Fix an i such that ℓ−1≤i≤m. We will construct the polynomial 𝐁i from the polynomial 𝐁i−1′. Consider the polynomial 𝐁i′′:=τ⁢((X−α)⋅𝐁i−1). Clearly, this polynomial is of the required form Yi⋅(X−α)ℓ−1+∑r∈[i]Yr⋅Ci,r⁢(X)+C~i⁢(X). By Proposition 4, we have that τ⁢(𝐁i′′,βj)=𝟎 for all j∈[ℓ−1]. Now, if τ⁢(𝐁i′′,βℓ−1) is also 𝟎, we can set 𝐁i:=𝐁i′′ and be done.

Suppose τ⁢(𝐁i′′,βℓ−1)≠𝟎. Then, let r∗∈[s−m] be the least r such thatτ(<r)⁢(𝐁i′′)⁢(α,βℓ−1)=𝟎r but τ(r)⁢(𝐁i′′)⁢(α,βℓ−1)≠0. By Proposition 4, definition of 𝐁i′′ and the fact that s−m is less than the characteristic of 𝔽, we also have τ(<r∗)⁢(𝐁i−1′)⁢(α,βℓ−1)=𝟎r∗ but τ(r∗)⁢(𝐁i−1′)⁢(α,βℓ−1)≠0. Let us consider the (s−m−r∗) polynomials {(X−α)t⋅𝐁i−1′:t∈[s−m−r∗]}. The t-th polynomial in this set, namely (X−α)t⋅𝐁i−1′ satisfies τ(<r∗+t)⁢((X−α)t⋅𝐁i−1′)⁢(α,βℓ−1)=𝟎r∗+t but τ(r∗+t)⁢((X−α)t⋅𝐁i−1′)⁢(α,βℓ−1)≠0. Hence, the (s−m−r∗) vectors {τ⁢((X−α)t⋅𝐁i−1′,βℓ−1):t∈[s−m−r∗]} form a basis for the space of all vectors in 𝔽s−m which are zero in the first r∗ coordinates. This space contains the vector τ⁢(𝐁i′′,βℓ−1) and hence there exist scalars ct∈𝔽 for t∈[s−m−r∗] such that

τ⁢(𝐁i′′,βℓ−1)=∑t∈[s−m−r∗]ct⋅τ⁢((X−α)t⋅𝐁i−1′,βℓ−1).

We can now set

𝐁i:=𝐁i′′−∑t∈[s−m−r∗]ct⋅(X−α)t⋅𝐁i−1′.

By choice of the scalars ct, we have that τ⁢(𝐁i,βℓ−1)=𝟎. Since τ⁢(𝐁i′′,βj)=𝟎 and τ⁢(𝐁i−1′,βj)=𝟎 for all j∈[ℓ−1], we also have that τ⁢(𝐁i,βj)=𝟎 for all j∈[ℓ−1]. Combining, we have that τ⁢(𝐁i,βj)=𝟎 for all j∈[ℓ].

It can be seen that 𝐁i is of the required form Yi⋅(X−α)ℓ−1+∑r∈[i]Yr⋅Ci,r⁢(X)+C~i⁢(X) since 𝐁i′′ is of this form and each of the polynomials (X−α)t⋅𝐁i−1′ are of the form ∑r∈[i]Yr⋅Ci,r⁢(X)+C~i⁢(X).

We turn to the time complexity. For each list element, we may have to solve a system of equations to find the scalars {ct}. Observe that this is a triangular system in at most s−m variables, and hence can be solved with O⁢(s−m)2 operations; giving an overall total of O~⁢(ℓ⁢(s−m)2) operations. This concludes the proof of the proposition. ◀

3.2 Combining the bases

In the previous section, we constructed a structured basis for each α∈S. In this section, we will show how to combine these bases recursively to obtain a single basis that works for all α∈S. To this end, we begin by showing a general procedure to combine the bases of two 𝔽⁢[X]-modules to generate the basis for a related 𝔽⁢[X]-module.

Let S be the set of evaluation points. For each α∈S, let pα⁢(X) be an associated monic polynomial of degree at most (s−m) such that for any two distinct α,β∈S, we have gcd⁡(pα,pβ)=1. We will be setting pα⁢(X)=(X−α)s−m for multiplicity codes.

Let 𝒰,𝒱 be two disjoint non-empty subsets of S. Define the polynomials

P𝒰⁢(X):=∏α∈𝒰pα⁢(X), P𝒱⁢(X):=∏α∈𝒱pα⁢(X).

Observe that since 𝒰∩𝒱=∅, we have gcd⁡(P𝒰,P𝒱)=1.

Let ℳ𝒰,ℳ𝒱 be two (m+2)-dimensional 𝔽⁢[X]-modules444Here, we identify the polynomial Q~+∑i∈[m]Yi⋅Qi⁢(X) with the (m+2)-dimensional vector (Q~,Q0,Q1,…,Qm) with lower-triangular bases ℬ𝒰={𝐔~,𝐔0,𝐔1,…,𝐔m} and ℬ𝒱={𝐕~,𝐕0,𝐕1,…,𝐕m} respectively of the following type:

𝐔~ =U~⁢(X), 𝐕~ =V~⁢(X)
𝐔i =Ui~⁢(X)+∑r=0iYr⋅Ui,r⁢(X), 𝐕i =Vi~⁢(X)+∑r=0iYr⋅Vi,r⁢(X), ∀0≤i≤m

Furthermore, suppose these bases ℬ𝒰,ℬ𝒱 behave “nicely” with their respective polynomials P𝒰,P𝒱 in the following sense: the diagonal elements U~,Ui,i,i∈[m] are nonzero factors of the polynomial P𝒰 and similarly V~,Vi,i,i∈[m] are nonzero factors of the polynomial P𝒱.

Let 𝒲=𝒰∪𝒱 and P𝒲=P𝒰⋅P𝒱 be the associated polynomial with the set 𝒲. We can construct a lower-triangular basis ℬ𝒲={𝐖~,𝐖0,𝐖1,…,𝐖m} which behaves “nicely” with the polynomial P𝒲 as follows:

𝐖~ =W~⁢(X)
𝐖i =Wi~⁢(X)+∑r=0iYr⋅Wi,r⁢(X), ∀0≤i≤m

where the diagonal elements are given by W~=U~⋅V~ and Wi,i=Ui,i⋅Vi,i,0≤i≤m and the non-diagonal elements Wi,r⁢(X),r∈[i] are the unique polynomials (by the Chinese remainder theorem) such that

Wi,r≡Ui,r⋅Vi,imodP𝒰,Wi,r≡Vi,r⋅Ui,imodP𝒱.

This basis satisfies that 𝐖i≡Vi,i⁢(X)⋅𝐔imodP𝒰 and symmetrically, 𝐖i≡Ui,i⁢(X)⋅𝐕imodP𝒱.

Let ℳ𝒲 be the 𝔽⁢[X]-module generated by this basis ℬ𝒲. This basis satisfies the following property.

Claim 12.

If 𝐇=H~⁢(X)+∑i∈[m]Yi⋅Hi⁢(X) or equivalently (H~,H0,H1,…,Hm) satisfies 𝐇modP𝒰∈ℳ𝒰 and 𝐇modP𝒱∈ℳ𝒱, then 𝐇modP𝒲∈ℳ𝒲.

Proof.

Since 𝐇modP𝒰∈ℳ𝒰 and 𝐇modP𝒱∈ℳ𝒱, we have polynomials A~,B~,Ai,Bi,0≤i≤m such that

𝐇modP𝒰 =A~⁢(X)⋅𝐔~+∑i=0mAi⁢(X)⋅𝐔i,
𝐇modP𝒱 =B~⁢(X)⋅𝐕~+∑i=0mBi⁢(X)⋅𝐕i.

Define polynomials

C~⁢(X) :=U~−1⋅P𝒰−1⋅B~modP𝒱, D~⁢(X) :=V~−1⋅P𝒱−1⋅A~modP𝒰
Ci⁢(X) :=Ui,i⁢(X)−1⋅P𝒰−1⋅BimodP𝒱, Di⁢(X) :=Vi,i−1⋅P𝒱−1⋅AimodP𝒰, i∈[m]

We claim that

𝐇=[C~⋅P𝒰+D~⋅P𝒱]⁢𝐖~+∑i=0m[Ci⋅P𝒰+Di⋅P𝒱]⁢𝐖imodP𝒰⁢P𝒱.

Indeed, observe the right-hand side mod P𝒰. All the terms involving P𝒰 vanish, leaving D~⋅P𝒱⋅𝐖~+∑i=0mDi⋅P𝒱⋅𝐖i. Simplifying using the definition of 𝐖, we have A~⋅𝐔~+∑i∈[m]Ai⋅𝐔i, which is 𝐇modP𝒰. The case mod P𝒱 is symmetric and the equivalence follows from the Chinese remainder theorem. ⊲

For the specific setting of multiplicity codes, the polynomial pα⁢(X) will be (X−α)s−m. For any subset 𝒰⊆S of the evaluation points, we will say that the basis ℬ𝒰={𝐔~,𝐔0,…,𝐔m} is 𝒰-good, if the following two properties are satisfied.

  1. 1.

    The diagonal elements of the basis satisfy

    U~⁢(X) :=∏α∈𝒰(X−α)s−m,
    Ui,i⁢(X) :=∏α∈𝒰(X−α)s−m,0≤i≤ℓ−2
    Ui,i⁢(X) :=∏α∈𝒰(X−α)ℓ−1,ℓ−1≤i≤m

    where ℓ is the list size.

  2. 2.

    Every basis element 𝐔∈ℬ𝒰 satisfies the τ-conditions (3) for every α∈𝒰.

Clearly, the basis generated by Proposition 11 when 𝒰={α} is a singleton set is {α}-good. The following claim shows that if ℬ𝒰,ℬ𝒱 are both good, so is ℬ𝒲.

Claim 13.

Let 𝒰,𝒱⊆S be two disjoint non-empty subsets of the set of evaluation points S. If ℬ𝒰 is 𝒰-good and ℬ𝒱 is 𝒱-good, then ℬ𝒲 is 𝒲-good.

Furthermore, there is a deterministic algorithm that when given the bases ℬ𝒰 and ℬ𝒱 outputs the basis ℬ𝒲, carrying out O~⁢(max⁡{|𝒰|,|𝒱|}⁢m2⁢(s−m)) field operations.

Proof.

Item 1 follows from how the diagonal elements of the basis ℬ𝒲 are defined. The runtime bound follows from the time required for the Chinese remainder theorem (Theorem 8): for the O⁢(m2) off-diagonal elements Wi,r, we carry out a CRT of polynomials of degree at most max⁡{|𝒰|,|𝒱|}⁢(s−m).

We now prove Item 2. Let 𝐖∈ℬ𝒲. If 𝐖=𝐖~, then 𝐖=𝐕~⋅𝐔~=∏α∈𝒲(X−α)s−m and hence satisfies the τ-conditions for all α∈𝒲. Suppose 𝐖=𝐖i for some 0≤i≤m. Let α∈𝒲. Suppose α∈𝒰. By definition of 𝐖i, we have 𝐖i≡Vi,i⋅𝐔imodP𝒰 and is hence of the form Vi,i⋅𝐔i+∏α∈𝒰(X−α)s−m⋅𝐇 for some polynomial 𝐇=H~+∑i=0mYi⋅Hi⁢(X). Since ℬ𝒰 is 𝒰-good, 𝐔i satisfies the τ-conditions with respect to α. Hence, so does Vi,i⋅𝐔i and 𝐖i. The case when α∈𝒱 is similar. ⊲

We are now ready to prove Proposition 10.

Proof of Proposition 10.

Let ℬS:={𝐁~,𝐁0,𝐁1,…,𝐁m} be obtained by the following process: Divide S into two halves 𝒰 and 𝒱, and recursively compute bases ℬ𝒰 and ℬ𝒱 for them, and then combine them as indicated earlier in this section. For a singleton set, we use the basis given by Proposition 11.

It follows from Claim 13, that since the bases for the singleton sets are good, so are all the bases that are recursively constructed. Thus, the basis ℬS has all the properties mentioned in Proposition 10. The only thing left to be verified is the running time.

As for the running time, let T⁢(n) be the running time where n is the size of the set S. We split it into two instances of size n/2, each of which can be solved in time T⁢(n/2). Claim 13 states that the bases for the two instances can be combined in time O~⁢(n⁢m2⁢(s−m)). Finally, Proposition 11 states that the base case when the set is a single point requires time O~⁢(ℓ⁢(s−m)2). Putting all this together, we have T⁢(n)=2⁢T⁢(n/2)+O~⁢(n⁢m2⁢(s−m)) and T⁢(1)=O~⁢(ℓ⁢(s−m)2). Solving, we get T⁢(n)=O~⁢(n⁢[ℓ⁢(s−m)2+m2⁢(s−m)]). ◀

3.3 Proof of Theorem 9

Before we prove the main theorem of the section, we have to connect the τ-conditions to the desired property, of close enough codewords satisfying the differential equation.

Lemma 14.

Let Q⁢(X,Y0,Y1,…,Ym)∈ℳS have X-degree at most D≤n⁢ℓ⁢(s−m)/m+n⁢ℓ and Yi-degree at most 1 for every Yi. Let f⁢(X)∈𝔽<k⁢[X] be such that for (D+k)/(s−m) values of α∈S, (f⁢(α),f(1)⁢(α),…,f(s−1)⁢(α))=(βj(0),βj(1),…,βj(s−1)) for some j∈[ℓ]. Then, Q⁢(X,f⁢(X),f(1)⁢(X),…,f(m)⁢(X))≡0.

Proof.

Let P⁢(X)=Q⁢(X,f⁢(X),f(1)⁢(X),…,f(s−1)⁢(X)). Since f has degree less than k and Q is linear in the Y-variables, P⁢(X) has degree less than D+k. The definition of the τ operator is set up such that τ(i)⁢(Q)⁢(X,f⁢(X),f(1)⁢(X),…,f(s−1)⁢(X))=di⁢Pd⁢Xi. This combined with Proposition 10 implies that for an agreement point α,

di⁢Pd⁢Xi⁢(α)=[τ(i)⁢(Q)]⁢(α,f⁢(α),f(1)⁢(α),…,f(s−1)⁢(α))=τ(i)⁢(Q)⁢(α,βj(0),βj(1),…,βj(s−1))=0

for any i∈[s−m]. That is, at these points, P vanishes with multiplicity at least (s−m). Therefore, if the number of such agreements is at least (D+k)/(s−m), P must be identically zero. ◀

We are now ready to prove the main theorem of the section.

Proof of Theorem 9.

We will take Q to be a polynomial in the 𝔽⁢[X]-span of the polynomials 𝐁~,𝐁0,𝐁1,…,𝐁m given by Proposition 10. Since each of them satisfies the τ-conditions, as given by the proposition, so will Q. In addition, Q will have the form Q=Q~⁢(X)+∑iQi⁢(X)⋅Yi, inherited from the basis polynomials.

We now have to bound the degree of the coefficients. Following our previous notation, let ℳS be span⁡{𝐁~,𝐁0,𝐁1,…,𝐁m}. By Theorem 6, ℳS contains a polynomial of degree at most (deg⁢detℳS)/(m+2). Because of the lower triangular structure, to find deg⁢detℳS, we need only multiply the degrees of the terms on the diagonal.

The first ℓ terms on the diagonal are ∏α∈S(X−α)s−m, and the remaining m+2−ℓ are ∏α∈S(X−α)ℓ−1. This gives deg⁢detℳS=n⁢ℓ⁢(s−m)+(m+2−ℓ)⁢n⁢(ℓ−1)≤n⁢ℓ⁢(s−m)+n⁢(m+2)⁢ℓ. Applying the Minkowski statement gives the required bound.

The close enough codewords statement is given by Lemma 14. This gives all the required properties of Q.

The running time is the time to construct the basis followed by the time to find a short vector in the lattice. From Proposition 10 and Theorem 7, we get a running time bound of O~⁢(n⁢[ℓ⁢(s−m)2+m2⁢(s−m)+(s−m)⁢mω]). ◀

4 List-recovery algorithm for multiplicity codes

Having constructed the differential equation, we now have to solve it in near-linear time. We use off-the-shelf subroutines for this. We recall the relevant algorithms before analyzing the overall list-recovery algorithm.

4.1 Fast algorithms for solving differential equations

We will invoke the following algorithms for solving differential equations from [6]. (Their paper also contains an analogous result for functional equations, for FRS codes.)

Theorem 15 ([6, Theorem 1.6]).

Let 𝔽 be a finite field of characteristic greater than d or zero, and let

Q⁢(X,Y0,…,Ym)=Q~⁢(X)+∑i=0mQi⁢(X)⋅Yi

be a nonzero polynomial with X-degree at most D. Then, the set of polynomials f⁢(X)∈𝔽⁢[X] of degree at most d that satisfy

Q⁢(X,f,f(1)⁢…,f(m))≡0

is contained in an affine space of dimension at most m.

Furthermore, there is a deterministic algorithm FastDESolver that when given Q as an input via its coefficient vector, and the parameter d, performs at most O~⁢((D+d)⁢m4) field operations and outputs a basis for this affine space.

▶ Remark 16.

The [6, Theorem 1.6] paper presents a complexity of O~⁢((D+d)⁢𝗉𝗈𝗅𝗒⁢(m)). On closer examination, their recursion contains a factor of at most m4 as they solve for m different basis elements separately and each is solved using [6, Algorithm 1]. The time complexity for this step is analyzed in [6, Lemma 5.8] which their analysis shows has a dependence of at most O⁢(m3).

These algorithms output a subspace containing the codewords. We use the “Prune” subroutine introduced by [15], which was simplified by [20], to obtain the codewords. The list-size bounds we present below are due to [20].

Theorem 17 ([15, Lemma 3.1], [20, Theorem 4.5]).

For every ε>0,ℓ∈ℕ, all integers s>16⁢ℓε2, degree parameter k, block length n and field 𝔽 of characteristic zero or greater than k, the following is true.

Define

L⁢(δ,ε,ℓ,r)=(ℓε)O⁢(1+log⁡(ℓ)ε).

Then, for any γ>0, there is a randomized algorithm Prune that when given as input sets S⊆𝔽 and Eα⊆𝔽s, with |Eα|≤ℓ for every α∈S and |S|=n, and a basis for an affine space 𝒜 of dimension at most 4⁢ℓ/ε, outputs

ℒ={f⁢(X)∈𝔽<k⁢[X]∩𝒜∣|{α∈S∣(f⁢(α),f(1)⁢(α),⋯,f(s−1)⁢(α))∈Eα}|>(R+ε)⁢n}

with probability at least 1−γ in time O~⁢(n)⁢𝗉𝗈𝗅𝗒⁢(log⁡q,s,L⁢(δ,ε,ℓ,r),log⁡(1/γ)) and it is guaranteed that

|ℒ|≤L⁢(δ,ε,ℓ,r).

4.2 Algorithm and proof of main theorem

The final algorithm proceeds in 3 steps: finding the differential equation, solving it, and pruning. Before restating and proving the main theorem, we state separately here the combination of the first two steps, as the time complexity in those parts is our main contribution.

Theorem 18.

For all integers ℓ,m,s∈ℕ with m<s, degree parameter k, block length n and field 𝔽 of characteristic zero or greater than k, the following is true.

There is a deterministic algorithm that, when given as input sets S⊆𝔽 and Eα⊆𝔽s with |Eα|≤ℓ for every α∈S and |S|=n, runs in time O⁢(n⁢log⁡|𝔽|⁢(ℓ⁢(s2+s⁢m3)+kn⁢m4)⁢𝗉𝗈𝗅𝗒𝗅𝗈𝗀⁢(n,s,log⁡log⁡|𝔽|)) and outputs the basis of an affine space 𝒜⊆𝔽⁢[X] of dimension at most m such that 𝒜 contains all polynomials f⁢(X) of degree less than k such that for at least (n⁢ℓ+kn⁢(s−m)+ℓm) fraction of α∈S,

(f⁢(α),⋯,f(s−1)⁢(α))∈Eα.

Proof.

We begin by describing the algorithm.

Input: R={(αi,βj(0),βj(1),…,βj(s−1))}i∈[n],j∈[ℓ],k∈ℤ

Task: Return the basis of an affine space 𝒜 of dimension at most m containing all f∈𝔽<k⁢[X] such that for n⁢ℓ/m+(n⁢ℓ+k)/(s−m) values of i,

(f⁢(αi),f(1)⁢(αi),…,f(s−1)⁢(αi))=(βj(0),βj(1),…,βj(s−1))

for some j∈[ℓ].

  1. 1.

    Construct a multivariate polynomial Q as per Theorem 9.

  2. 2.

    Solve the resulting differential equation using the algorithm in Theorem 15, to obtain an affine space A containing all the codewords.

Observe that by Theorem 9, we can construct a multivariate polynomial Q⁢(X,Y0,⋯,Ym) of the form Q=Q~⁢(X)+∑iQi⁢(X)⋅Yi of X-degree at most D≤n⁢ℓ⁢(s−m)m+n⁢ℓ with the following property: if f⁢(X)∈𝔽<k⁢[X] is such that for at least 1s−m⁢(n⁢ℓ⁢(s−m)m+n⁢ℓ+k)=n⁢ℓm+n⁢ℓ+ks−m values of α∈S, we have

(f⁢(α),⋯,f(s−1)⁢(α))∈Eα,

then,

Q⁢(X,f⁢(X),f(1)⁢(X),⋯,f(m)⁢(X))≡0

in time O~⁢(n⁢ℓ⁢((s−m)2+(s−m)⁢mω)) which is within our time complexity.

Now, Theorem 15 outputs the basis of the affine space of dimension at most m of the polynomials of degree <k which are solutions of the above differential equation in time O~⁢((D+k)⁢m4). Substituting D≤n⁢ℓ⁢(s−m)m+n⁢ℓ, the time complexity is within the claimed range. ◀

We are finally ready to prove the main theorem. We first recall the theorem statement.

Theorem 1 (main result for multiplicity codes). [Restated, see original statement.]

For every ε>0 and ℓ∈ℕ, there exists s0=Θ⁢(ℓ/ε2)∈ℕ such that for all s>s0, degree parameter k, block length n, and fields 𝔽 of characteristic zero or characteristic greater than k, satisfying k<n⁢s, the following holds. There is a randomized algorithm that, given a set S⊆𝔽 of size n and sets Eα⊆𝔽s with |Eα|≤ℓ for each α∈S, takes

O⁢(n⋅𝗉𝗈𝗅𝗒⁢(s,ℓ,log⁡n,(ℓ/ε)1+log⁡ℓε))

field operations and with high probability outputs all univariate polynomials f⁢(X)∈𝔽⁢[X] of degree less than k such that for at least (ks⁢n+ε) fraction of α∈S,

(f⁢(α),f(1)⁢(α),…,f(s−1)⁢(α))∈Eα.

Proof.

We will first set the parameters. Recall that the agreement fraction for which Theorem 9 works is

n⁢ℓ+kn⁢(s−m)+ℓm.

The rate R is k/n⁢s. For the above to approximately equal R+ε, we set s0=16⁢ℓ/ε2+4⁢ℓε and m=4⁢ℓ/ε with s>s0. Thus,

n⁢ℓ+kn⁢(s−m)+ℓm≤ℓ(s−m)+kn⁢(s−m)+ε2≤ε216+ε4+R⋅(ss−m)≤R+ε⋅R4+ε4+ε216

Since ε≤1−R and thus ε2≤ε⁢(1−R), we get that

n⁢ℓ+kn⁢(s−m)+ℓm<R+ε/2.

The algorithm is given below.

Input: R={(αi,βj(0),βj(1),…,βj(s−1))}i∈[n],j∈[ℓ],k∈ℤ

Task: Return all f∈𝔽<k⁢[X] such that for n⁢ℓ/m+(n⁢ℓ+k)/(s−m) values of i,

(f⁢(αi),f(1)⁢(αi),…,f(s−1)⁢(αi))=(βj(0),βj(1),…,βj(s−1))

for some j∈[ℓ].

  1. 1.

    Find an affine space of dimension at most m which contains all the required codewords using Theorem 18.

  2. 2.

    Using the algorithm in Theorem 17, obtain a list ℒ of codewords and return it.

Let f be a polynomial such that for n⁢ℓ/m+(n⁢ℓ+k)/(s−m) values of i,

(f⁢(αi),f(1)⁢(αi),…,f(s−1)⁢(αi))=(βj(0),βj(1),…,βj(s−1))

for some j∈[ℓ]. By Theorem 18, f is contained in the output affine space. The algorithm in Theorem 17 finds f with high probability.

We saw in Theorem 18 that step 1 can be done in O~⁢(n⁢𝗉𝗈𝗅𝗒⁢(s+m+ℓ)) time. Combining with the runtime of Theorem 17, we get a runtime of O~⁢(n⁢𝗉𝗈𝗅𝗒⁢(s,ℓ,(ℓ/ε)1+log⁡ℓε)). ◀

References

  • [1] Michael Alekhnovich. Linear Diophantine equations over polynomials and soft decoding of Reed-Solomon codes. IEEE Trans. Inform. Theory, 51(7):2257–2265, 2005. (Preliminary version in 43rd FOCS, 2002). doi:10.1109/TIT.2005.850097.
  • [2] Vikrant Ashvinkumar, Mursalin Habib, and Shashank Srivastava. Algorithmic improvements to list decoding of folded Reed-Solomon codes. In Kasper Green Larsen and Barna Saha, editors, Proc. 37th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 880–898, 2026. doi:10.1137/1.9781611978971.35.
  • [3] Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, and Madhu Sudan. Decoding multivariate multiplicity codes over product sets. IEEE Trans. Inform. Theory, 70(1):154–169, 2024. (Preliminary version in 53rd STOC, 2021). doi:10.1109/TIT.2023.3306849.
  • [4] Joshua Brakensiek, Yeyuan Chen, Manik Dhar, and Zihan Zhang. Combinatorial bounds for list recovery via discrete Brascamp–Lieb inequalities. In Aditya Bhaskara and Artur Czumaj, editors, Proc. 58th ACM Symp. on Theory of Computing (STOC), pages 365–376. ACM, 2026. doi:10.1145/3798129.3800756.
  • [5] Yeyuan Chen and Zihan Zhang. Explicit folded Reed-Solomon and multiplicity codes achieve relaxed generalized singleton bound. In Michal Koucký and Nikhil Bansal, editors, Proc. 57th ACM Symp. on Theory of Computing (STOC), pages 1–12, 2025. doi:10.1145/3717823.3718114.
  • [6] Rohan Goyal, Prahladh Harsha, Mrinal Kumar, and Ashutosh Shankar. Fast list-decoding of univariate multiplicity and folded Reed-Solomon codes. In Santosh Vempala, editor, Proc. 65th IEEE Symp. on Foundations of Comp. Science (FOCS), pages 328–343, 2024. doi:10.1109/FOCS61266.2024.00028.
  • [7] Somit Gupta, Soumojit Sarkar, Arne Storjohann, and Johnny Valeriote. Triangular x-basis decompositions and derandomization of linear algebra algorithms over k⁢[x]. J. Symb. Comput., 47(4):422–453, 2012. doi:10.1016/J.JSC.2011.09.006.
  • [8] Venkatesan Guruswami and Atri Rudra. Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy. IEEE Trans. Inform. Theory, 54(1):135–150, 2008. (Preliminary version in 38th STOC, 2006). doi:10.1109/TIT.2007.911222.
  • [9] Venkatesan Guruswami and Madhu Sudan. Improved decoding of Reed-Solomon and algebraic-geometry codes. IEEE Trans. Inform. Theory, 45(6):1757–1767, 1999. (Preliminary version in 39th FOCS, 1998). doi:10.1109/18.782097.
  • [10] Venkatesan Guruswami and Carol Wang. Linear-algebraic list decoding for variants of Reed-Solomon codes. IEEE Trans. Inform. Theory, 59(6):3257–3268, 2013. (Preliminary version in 26th IEEE Conference on Computational Complexity, 2011 and 15th RANDOM, 2011). doi:10.1109/TIT.2013.2246813.
  • [11] Fernando Granha Jeronimo, Tushant Mittal, Shashank Srivastava, and Madhur Tulsiani. Explicit codes approaching generalized Singleton bound using expanders. In Michal Koucký and Nikhil Bansal, editors, Proc. 57th ACM Symp. on Theory of Computing (STOC), pages 843–854, 2025. doi:10.1145/3717823.3718302.
  • [12] Fernando Granha Jeronimo and Nikhil Shagrithaya. Probabilistic guarantees to explicit constructions: Local properties of linear codes. In Aditya Bhaskara and Artur Czumaj, editors, Proc. 58th ACM Symp. on Theory of Computing (STOC), pages 806–813, 2026. doi:10.1145/3798129.3800795.
  • [13] Itay Kalev and Amnon Ta-Shma. Unbalanced expanders from multiplicity codes. In Amit Chakrabarti and Chaitanya Swamy, editors, Proc. 26th International Conf. on Randomization and Computation (RANDOM), volume 245 of LIPIcs, pages 12:1–12:14. Schloss Dagstuhl, 2022. doi:10.4230/LIPIcs.APPROX/RANDOM.2022.12.
  • [14] Swastik Kopparty. Some remarks on multiplicity codes. In Alexander Barg and Oleg R. Musin, editors, Discrete Geometry and Algebraic Combinatorics, volume 625 of Contemporary Mathematics, pages 155–176. AMS, 2014. doi:10.1090/conm/625/12497.
  • [15] Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, and Mary Wootters. Improved list decoding of Folded Reed-Solomon and Multiplicity codes. SIAM J. Comput., 52(3):794–840, 2023. (Preliminary version in 59th FOCS, 2018). doi:10.1137/20M1370215.
  • [16] Nicolas Resch and S. Venkitesh. List recoverable codes: The good, the bad, and the unknown (hopefully not ugly). (manuscript).
  • [17] Shashank Srivastava. Improved list size for folded Reed-Solomon codes. In Yossi Azar and Debmalya Panigrahi, editors, Proc. 36th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 2040–2050, 2025. doi:10.1137/1.9781611978322.64.
  • [18] Shashank Srivastava and Madhur Tulsiani. List decoding expander-based codes up to capacity in near-linear time. In Rotem Oshman and Ran Raz, editors, Proc. 66th IEEE Symp. on Foundations of Comp. Science (FOCS), pages 1465–1487, 2025. doi:10.1109/FOCS63196.2025.00077.
  • [19] Madhu Sudan. Decoding of Reed-Solomon codes beyond the error-correction bound. J. Complexity, 13(1):180–193, 1997. (Preliminary version in 37th FOCS, 1996). doi:10.1006/jcom.1997.0439.
  • [20] Itzhak Tamo. Tighter list-size bounds for list-decoding and recovery of folded Reed-Solomon and multiplicity codes. IEEE Trans. Inform. Theory, 70(12):8659–8668, 2024. doi:10.1109/TIT.2024.3402171.
  • [21] Salil P. Vadhan. Pseudorandomness. Found. Trends Theor. Comput. Sci., 7(1-3):1–336, 2012. doi:10.1561/0400000010.
  • [22] Joachim von zur Gathen and Jürgen Gerhard. Modern Computer Algebra. Cambridge University Press, 3 edition, 2013. doi:10.1017/CBO9781139856065.
  • [23] Mary Wootters. CS250/EE387: Algebraic error correcting codes, 2019. (A course on coding theory at Stanford, Winter 2019). URL: https://web.stanford.edu/˜marykw/classes/CS250_W19/index.html.