Fast List Recovery of Univariate Multiplicity Codes
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 -time algorithms for list recovery of Folded Reed–Solomon codes and univariate multiplicity codes up to capacity, where 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-algorithmCategory:
RANDOMFunding:
Rohan Goyal: Supported by (Yael Tauman Kalai’s) grant from Defense Advanced Research Projects Agency (DARPA) ††margin:Copyright and License:
2012 ACM Subject Classification:
Theory of computation Error-correcting codes ; Theory of computation Design and analysis of algorithmsEditors:
Mohit Singh and Tom GurSeries and Publisher:
Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik
1 Introduction
An error-correcting code is said to be list decodable if every Hamming ball of radius in contains at most codewords of . When , 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 , , , 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 is said to be list recoverable if for all subsets with , there are at most codewords such that for at most coordinates . Clearly, the case 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 , 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 are treated as constants, the running time of our algorithm is .
More formally, we prove the following theorem.
Theorem 1 (main result for multiplicity codes).
For every and , there exists such that for all , degree parameter , block length , and fields of characteristic zero or characteristic greater than , satisfying , the following holds. There is a randomized algorithm that, given a set of size and sets with for each , takes
field operations and with high probability outputs all univariate polynomials of degree less than such that for at least fraction of ,
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 of size , where each is associated with a list of -tuples in . 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 , a nonzero polynomial , linear in the -variables and of bounded degree, such that every polynomial whose encoding agrees sufficiently with the received word satisfies the differential equation:
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 is associated with a unique received vector . The algorithm constructs in near-linear time univariate polynomials satisfying for all , . One then considers the -module (lattice) of polynomials in generated by
| (1) |
This lattice has the property that any nonzero element of this lattice of sufficiently small degree yields a polynomial such that every polynomial whose encoding agrees with the received word on sufficiently many ’s satisfies
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 , so the received word is no longer a function . In particular, the definition of the polynomials above breaks down. A natural attempt is to arbitrarily “split” the input into received words in the list-decoding sense: for , let , and construct the corresponding polynomials . One could then try to work with the lattice generated by products such as (over ), thereby capturing the disjunction “ matches one of the possibilities.” However, this immediately leads to polynomials with -degree , and hence to nonlinear differential equations. This is the main obstacle. Even if one could find such a low-degree 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 -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 -degree larger than one; consequently, Alekhnovich’s approach readily extends to list recovery..
Motivated by this, it is natural to insist on keeping linear in the -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 whose generators are linear in , 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 -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.
for some polynomials for and . The proof that such a basis exists is considerably involved. We first show that such an almost-triangular basis exists for each 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 , we will use to refer to the set .
-
We use to denote the -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 be positive integers satisfying , be a field of characteristic zero or at least and size at least , and let be a set of distinct elements of . Then, the univariate multiplicity code with multiplicity parameter and degree parameter is defined as follows.
The alphabet of the code is and the block length is , where the coordinates of a codeword are indexed by . The message space is the set of all univariate polynomials of degree less than in . The encoding of such a message , denoted by is defined as
where is the evaluation of the -order derivative333This definition in terms of (standard) derivatives requires the characteristic of the field to be 0 or at least . 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 on the input . The rate of this code is while the distance is .
In the list-recovery setting, the received word assigns to every evaluation point a collection of tuples for every . In words is the option for the derivative of the message polynomial at . Agreement is with respect to inclusion in this list; that is, agrees with on point if there exists such that .
Our goal is to carry out list recovery from an agreement fraction of , for a given parameter .
2.3 Polynomial operators and lattices
Definition 3 (Tau operator).
Let be a parameter. Then, for every such that , the function is an -linear map from the set of polynomials in with -degree to the set of polynomials in with -degree and is defined as follows.
For an integer , we use to denote the linear map from to obtained by applying the operator iteratively times.
The operator is defined this way so that
It will be convenient to view polynomials in for as polynomials in . Thus, when evaluating a polynomial at the point , refers to .
We will extensively use the following simple property of the operator.
Proposition 4.
Let be a field element and . Then, for any integer with ,
Proof.
We prove this by induction on . When , the left-hand side is . From the definition, this equals . (This can be checked term by term.) The first term is zero when evaluated at leaving as required.
For the induction step, observe similarly that
Evaluating at , by the induction hypothesis,
We now define lattices and state the version of Minkowski’s theorem for polynomial lattices.
Definition 5 (polynomial lattice).
Let be a set of -dimensional vectors of polynomials, that is, for all . The lattice generated by this set over the ring is the set of all linear combinations
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 of rational functions over . A basis can be viewed as an matrix (the basis vectors written side by side as columns).
For a full-rank lattice (i.e., when ), 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 .
Let be a vector of polynomials. We define the max-degree norm as follows .
Theorem 6 (polynomial version of Minkowski’s theorem).
Let be an -dimensional polynomial lattice. Then, there is a nonzero vector in the lattice satisfying
where is the max-degree norm and is the determinant of the lattice basis.
A proof can be found in [6].
Theorem 7 ([1, Theorem 2.1],[7, Theorem 9]).
Let be a set of vectors of dimension . Let be the maximal degree of the polynomials which are entries of the vectors in . Then, there is an algorithm ShortVector that finds the shortest vector in , the lattice generated by , in time 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 be univariate polynomials in with pairwise GCD equal to 1. Let such that for all . Then, we can find the unique polynomial of degree less than such that for all , in time .
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 be a received word and let be a parameter.
Then, for , there exists a nonzero polynomial of the form of -degree at most with the following property: if is such that for at least values of , we have
for some , then,
| (2) |
Furthermore, there is a deterministic algorithm that takes as input and returns as a list of coefficients that carries out field operations – specifically, .
A natural way to ensure that the polynomial satisfies (2), is to ensure that for each , we have the following conditions
| (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 satisfying (3) are closed under addition and multiplication by a polynomial in . In other words, they form a -module (or equivalently a lattice with entries from the univariate ring ). Here, it will be convenient to view the polynomial as an -dimensional vector of the form where the first component is the -free part of and the subsequent components are the coefficients of 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 be the received word and let be a parameter.
Then, there exist polynomials in satisfying the -conditions (3) for all of the following type
for some polynomials for and . Furthermore, there is a deterministic algorithm that takes as input and returns these -polynomials carrying out 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., ) 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 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 (which is proved in Section 3.1).
Proposition 11.
Let and be the list size and let be a parameter.
Given possible evaluations (i.e., for each ) at the point , there exist polynomials in satisfying the -conditions (3) for this specific of the following type
for some polynomials for and . Furthermore, there is a deterministic algorithm that takes as input and returns these polynomials, carrying out field operations.
We then show in Section 3.2 that the bases for two disjoint sets of evaluation points (i.e., ) can be combined into a basis for the set in time approximately . We use this procedure recursively over the bases constructed via Proposition 11 for each to obtain a basis that works simultaneously for all to yield Proposition 10.
3.1 Construction of basis for a single evaluation point
In this section, we will fix an evaluation point and construct a set of linearly independent polynomials (over the ring ) as specified in Proposition 11. More precisely, we want to show that there exist 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.
for some polynomials for and .
To this end, given a polynomial of the above form and any we will find it convenient to use the following notation for the vector in composed of evaluations of iterated -operator of the polynomial at the point :
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 for all and each . Clearly, this is true when . In the rest of the proof, we will construct polynomials , such that this is also true for the polynomials . We will prove this by induction on , the list size.
- Base case :
-
This is the list-decoding setting, where we have only in the list corresponding to , namely . The proof in this case is similar to the corresponding step in [6], which is obtained by Hermite interpolation. For each , we define the polynomial to be the unique -degree polynomial in such that for all , we have
The remaining are set to zero for all and . In other words, the polynomial for . clearly satisfies the -conditions (3) for .
- Induction step :
-
By induction, let us assume that for the first list elements , we have polynomials satisfying the -conditions for , namely for all such that and . We now need to construct polynomials for such that for all such that and . Note that the number of polynomials to be constructed in the -case is one less than the -case while the number of ’s for which we need is one more.
Fix an such that . We will construct the polynomial from the polynomial . Consider the polynomial . Clearly, this polynomial is of the required form . By Proposition 4, we have that for all . Now, if is also , we can set and be done.
Suppose . Then, let be the least such that but . By Proposition 4, definition of and the fact that is less than the characteristic of , we also have but . Let us consider the polynomials . The -th polynomial in this set, namely satisfies but . Hence, the vectors form a basis for the space of all vectors in which are zero in the first coordinates. This space contains the vector and hence there exist scalars for such that
We can now set
By choice of the scalars , we have that . Since and for all , we also have that for all . Combining, we have that for all .
It can be seen that is of the required form since is of this form and each of the polynomials are of the form .
We turn to the time complexity. For each list element, we may have to solve a system of equations to find the scalars . Observe that this is a triangular system in at most variables, and hence can be solved with operations; giving an overall total of operations. This concludes the proof of the proposition.
3.2 Combining the bases
In the previous section, we constructed a structured basis for each . In this section, we will show how to combine these bases recursively to obtain a single basis that works for all . To this end, we begin by showing a general procedure to combine the bases of two -modules to generate the basis for a related -module.
Let be the set of evaluation points. For each , let be an associated monic polynomial of degree at most such that for any two distinct , we have . We will be setting for multiplicity codes.
Let be two disjoint non-empty subsets of . Define the polynomials
Observe that since , we have .
Let be two -dimensional -modules444Here, we identify the polynomial with the -dimensional vector with lower-triangular bases and respectively of the following type:
Furthermore, suppose these bases behave “nicely” with their respective polynomials in the following sense: the diagonal elements are nonzero factors of the polynomial and similarly are nonzero factors of the polynomial .
Let and be the associated polynomial with the set . We can construct a lower-triangular basis which behaves “nicely” with the polynomial as follows:
where the diagonal elements are given by and and the non-diagonal elements are the unique polynomials (by the Chinese remainder theorem) such that
This basis satisfies that and symmetrically, .
Let be the -module generated by this basis . This basis satisfies the following property.
Claim 12.
If or equivalently satisfies and , then .
Proof.
Since and , we have polynomials such that
Define polynomials
We claim that
Indeed, observe the right-hand side mod . All the terms involving vanish, leaving . Simplifying using the definition of , we have , which is . The case mod is symmetric and the equivalence follows from the Chinese remainder theorem.
For the specific setting of multiplicity codes, the polynomial will be . For any subset of the evaluation points, we will say that the basis is -good, if the following two properties are satisfied.
-
1.
The diagonal elements of the basis satisfy
where is the list size.
-
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 be two disjoint non-empty subsets of the set of evaluation points . 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 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 off-diagonal elements , we carry out a CRT of polynomials of degree at most .
We now prove Item 2. Let . If , then and hence satisfies the -conditions for all . Suppose for some . Let . Suppose . By definition of , we have and is hence of the form for some polynomial . Since is -good, satisfies the -conditions with respect to . Hence, so does and . The case when is similar.
We are now ready to prove Proposition 10.
Proof of Proposition 10.
Let be obtained by the following process: Divide 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 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 be the running time where is the size of the set . We split it into two instances of size , each of which can be solved in time . Claim 13 states that the bases for the two instances can be combined in time . Finally, Proposition 11 states that the base case when the set is a single point requires time . Putting all this together, we have and . Solving, we get .
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 have -degree at most and -degree at most 1 for every . Let be such that for values of , for some . Then, .
Proof.
Let . Since has degree less than and is linear in the -variables, has degree less than . The definition of the operator is set up such that . This combined with Proposition 10 implies that for an agreement point ,
for any . That is, at these points, vanishes with multiplicity at least . Therefore, if the number of such agreements is at least , must be identically zero.
We are now ready to prove the main theorem of the section.
Proof of Theorem 9.
We will take to be a polynomial in the -span of the polynomials given by Proposition 10. Since each of them satisfies the -conditions, as given by the proposition, so will . In addition, will have the form , inherited from the basis polynomials.
We now have to bound the degree of the coefficients. Following our previous notation, let be . By Theorem 6, contains a polynomial of degree at most . Because of the lower triangular structure, to find , we need only multiply the degrees of the terms on the diagonal.
The first terms on the diagonal are , and the remaining are . This gives . 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 .
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 .
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 or zero, and let
be a nonzero polynomial with -degree at most . Then, the set of polynomials of degree at most that satisfy
is contained in an affine space of dimension at most .
Furthermore, there is a deterministic algorithm FastDESolver that when given as an input via its coefficient vector, and the parameter , performs at most field operations and outputs a basis for this affine space.
Remark 16.
The [6, Theorem 1.6] paper presents a complexity of . On closer examination, their recursion contains a factor of at most as they solve for 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 .
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 , all integers , degree parameter , block length and field of characteristic zero or greater than , the following is true.
Define
Then, for any , there is a randomized algorithm Prune that when given as input sets and , with for every and , and a basis for an affine space of dimension at most , outputs
with probability at least in time and it is guaranteed that
4.2 Algorithm and proof of main theorem
The final algorithm proceeds in 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 with , degree parameter , block length and field of characteristic zero or greater than , the following is true.
There is a deterministic algorithm that, when given as input sets and with for every and , runs in time and outputs the basis of an affine space of dimension at most such that contains all polynomials of degree less than such that for at least fraction of ,
Proof.
We begin by describing the algorithm.
Input:
Task: Return the basis of an affine space of dimension at most containing all such that for values of ,
for some .
-
1.
Construct a multivariate polynomial as per Theorem 9.
-
2.
Solve the resulting differential equation using the algorithm in Theorem 15, to obtain an affine space containing all the codewords.
Observe that by Theorem 9, we can construct a multivariate polynomial of the form of -degree at most with the following property: if is such that for at least values of , we have
then,
in time which is within our time complexity.
Now, Theorem 15 outputs the basis of the affine space of dimension at most of the polynomials of degree which are solutions of the above differential equation in time . Substituting , 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 and , there exists such that for all , degree parameter , block length , and fields of characteristic zero or characteristic greater than , satisfying , the following holds. There is a randomized algorithm that, given a set of size and sets with for each , takes
field operations and with high probability outputs all univariate polynomials of degree less than such that for at least fraction of ,
Proof.
We will first set the parameters. Recall that the agreement fraction for which Theorem 9 works is
The rate is . For the above to approximately equal , we set and with . Thus,
Since and thus , we get that
The algorithm is given below.
Input:
Task: Return all such that for values of ,
for some .
-
1.
Find an affine space of dimension at most which contains all the required codewords using Theorem 18.
-
2.
Using the algorithm in Theorem 17, obtain a list of codewords and return it.
Let be a polynomial such that for values of ,
for some . By Theorem 18, is contained in the output affine space. The algorithm in Theorem 17 finds with high probability.
We saw in Theorem 18 that step can be done in time. Combining with the runtime of Theorem 17, we get a runtime of .
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. th 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. th 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. th 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. th 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 . 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. th 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. th 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. th 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. th 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. th 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.
