Time and Space Efficient Deterministic List Decoding

Error correcting codes encode information in a robust way, so that even if part of an encoding gets corrupted, it is still possible to decode the information. Codes are of great importance in communication and storage and have been studied for decades [27, 39]. In theoretical computer science, codes have numerous applications, e.g., for pseudorandomness [30, 47, 49, 20], interactive protocols [33, 21, 40], probabilistically checkable proofs [5, 18, 3, 2] and cryptography [48, 34, 12, 38, 43].

The number of indices $i\in [n]$ where two strings $w,w^{\prime }\in {\mathrm{\Sigma }}^n$ differ, i.e., $w_i\ne w_i^{\prime }$, is called the Hamming distance between the strings. The number of indices $i$ where $w_i=w_i^{\prime }$ is the agreement of the strings. The process of computing $C(x)$ for a message $x$ is called encoding. The process of computing $x$ from a word $w$ that agrees with a codeword $C(x)$ on most indices, is called decoding. Note that only words $w$ that agree with a codeword $C(x)$ on all but less than $d/2$ indices can be uniquely decoded. An important generalization of decoding is list decoding [17, 50]. Here, the decoder outputs all the codewords that have sufficient agreement with $w$. List decoding with short lists is often possible even for corrupted codewords with close to $d$ errors (!) Such words may only agree with a codeword on a small fraction of the positions $i\in [n]$. List decoding turns out to be important for communication, and is crucial for many applications in theoretical computer science, such as pseudorandom generators [47, 42], low error PCPs [37, 13, 29, 35] and optimal inapproximability [28].

Algorithmic coding theory aims to implement error correcting codes efficiently. Much work focuses on the time complexity of encoding and decoding, resulting in explicit asymptotically good codes that can be encoded and decoded in deterministic linear time [45, 44]. List decoding too can be achieved in linear time [26]. However, these algorithms have a linear space complexity. Other work focused on space complexity. All asymptotically good linear codes can be encoded in logarithmic space and quadratic time. Some codes (e.g., [45]) were shown to also have decoding in logarithmic space, however the algorithms use large polynomial time. For instance, Spielman codes [45] have uniform circuits with linear size and $d=O(\log (n))$ depth circuits that decode them. These low depth circuits have a straightforward algorithm evaluating them in $O(d)=O(\log (n))$ space (where $d>2\log (n)$), but it runs in time $\mathrm{\Omega }(2^d)=\mathrm{\Omega }(n^2)$.

The current work focuses on deterministic algorithms that run simultaneously in almost linear time and sub-linear space. The question of whether there are explicit asymptotically good codes with time-space efficient encoding or decoding was raised in [7] and [22], respectively. Much of the initial work in the area focused on negative results. Bazzi, Mahdian and Spielman [7] considered Turbo-like codes that could potentially have linear time and logarithmic space encoding, but showed that they were not asymptotically good. Bazzi and Mitter [6] proved that codes that can be encoded in linear time and sub-linear space cannot be asymptotically good. Gronemeier [22] showed that deterministic non-adaptive decoders in almost linear time must run in near-linear space. In sharp contrast, recent work gave positive results. The paper [10] constructs explicit asymptotically good codes with deterministic almost-linear time and sub-linear space encoders [10]. It evades the impossibility result by considering almost linear time instead of linear time. The paper [11] constructs explicit asymptotically good codes with deterministic almost-linear time and sub-linear space decoders. It evades the impossibility result by using an adaptive decoder.

A downside of the paper [11] is that it only gives unique decoding algorithms. The goal of the current paper is to design time-space efficient deterministic list decoding algorithms. Our main theorem is as follows:

The code for which we can give time-space efficient list decoding is the Reed-Muller code, as well as small alphabet versions of it obtained by concatenation with constant alphabet codes. See the end of Section 6 for more detailed results. The Reed-Muller code is natural and widely used. Its codewords are the truth tables of low degree multivariate polynomials over a finite field. The code is known for its strong local testing and correction properties, and those properties are crucial for our result.

We remark that if one only wants a non-uniform list decoder for codes that are locally testable and correctable (with weaker parameters than Reed-Muller) one can employ a technique from the paper [23] that reduces list decoding to unique decoding.

Our main technical contribution is generalizing the unique decoding algorithm from the paper [11] to the list decoding setting. The method of [11] iteratively corrects the received word until it becomes a codeword. This approach makes sense in the unique decoding setting, but does not seem appropriate for the list decoding setting, where the received word might have small agreement with many different codewords.

The key idea of our solution is as follows. First, we identify a simpler problem that we call codewords list recovery, for which we are able to generalize the approach of [11]. Then, we show how to reduce the list decoding problem to the codewords list recovery problem in efficient time and space.

The general structure of our list decoding algorithm is described in Figure 1.

Codewords list recovery is a special case of the list recovery problem. In list recovery the input consists of short lists of possible symbols for each position in the codeword, and the goal is to find all the codewords that are consistent with most of the lists. In codewords list recovery, the lists come from $\mathrm{\ell }$ codewords. Most of the lists are exactly consistent with those $\mathrm{\ell }$ codewords, and the goal is to correct those lists:

Our algorithm for codewords list recovery requires a generalization of the algorithm in [11] to the case where there are $\mathrm{\ell }$ symbols rather than one per index. Meanwhile, it is the time-space efficient reduction from list decoding to codewords list recovery that does much of the heavy lifting for the list decoding algorithm. The reduction uses local correction to compose the lists and local testing to ensure that most lists match exactly with global codewords.

Our list decoding algorithm relies on local correction and testing. The paper [11] on unique decoding relies on local correction. The codewords in the paper [10] or in Turbo-like codes [7] have symbols that depend on a small number of other codeword symbols and input symbols. A natural question is whether the locality of all those codes is an artifact of the ideas that were used so far in this area, or whether locality is somehow inherent to time-space efficient error correcting codes.

Perhaps surprisingly, we show that locality is inherent, in the following sense. We consider linear codes, i.e., linear transformations $𝒞:{\mathrm{\Sigma }}^k\to {\mathrm{\Sigma }}^n$. Moreover, we assume that $𝒞$ is systematic, i.e., $𝒞$ maps $x\in {\mathrm{\Sigma }}^k$ to a codeword $C(x)=(x,y)\in {\mathrm{\Sigma }}^n$ that starts with the input $x$. (Note that there is no loss of generality in considering systematic codes, and this assumption will allow us to handle encoding and decoding at the same time.) For linear codes, $𝒞({\mathrm{\Sigma }}^k)$ is a linear subspace, and the orthogonal subspace $𝒞{({\mathrm{\Sigma }}^k)}^{\perp }$ consists of the linear constraints that all the codewords satisfy. The weight of a constraint in $𝒞{({\mathrm{\Sigma }}^k)}^{\perp }$ is its Hamming distance from $\overrightarrow{0}$. The minimum weight over all non-zero elements in $𝒞{({\mathrm{\Sigma }}^k)}^{\perp }$ is a measure of the locality of $𝒞$. All locally testable and locally correctable codes have low weight constraints, however this is a necessary but not a sufficient condition for local testability and local correction.

We show that linear, systematic, codes $𝒞$ with time-space efficient encoding or decoding must have a low weight linear constraint:

This theorem implies that codes with time-space efficient encoding or decoding must be local in the sense of having a low weight constraint. Locally correctable codes like those considered in this paper or in [11] indeed have low weight constraints. The codes considered in [10, 7] are not locally correctable but they have low weight constraints too. Since self dual codes do not have low weight constraints, this recovers the result of [41] that self dual codes cannot be encoded time and space efficiently and generalizes it to decoding, and more general codes.

One can add a local constraint to any code (e.g., by repeating a symbol in the codeword) and foil the premise of Theorem 5. However, the theorem rules out many natural codes from having time-space efficient encoding or decoding. For instance, the Reed-Solomon code does not have low weight constraints, and therefore cannot have time-space efficient encoding or decoding:

The theorem also suggests a path for ruling out more contrived codes from having time-space efficient encoding or decoding: Find a sub-code without low weight constraints that still has time-space efficient encoding or decoding.

Observe that randomized time-space efficient unique decoding follows from locally decodable codes with a sub-linear number of queries [31, 51]. In locally decodable codes it is possible to get “random access” to the message given a corrupted codeword. That is, to decode a single symbol in the message $x_i$, it suffices to make a small number of queries to the corrupted codeword, chosen in a randomized fashion.

By repeating the local decoder $\mathrm{\Theta }(\log k)$ times, its error probability is sufficiently smaller than $1/k$, and running the decoder on every $i\in [k]$, one obtains a time-space efficient randomized decoder. Provided that the local decoder makes $q=n^{o(1)}$ queries and runs in time and space that are polynomial in $q$, the space complexity of the decoder we get is sub-linear and the time complexity is almost linear. Those ideas can also be extended to get a randomized time-space efficient list decoding algorithm from locally list decodable codes.

The challenge in decoding is to get time-space efficiency in a deterministic algorithm. A natural derandomization would take at least quadratic time: it would enumerate over all possible randomness strings of the local decoder (at least a linear number). For each randomness string, it would compute, in at least linear time, the corresponding codeword and check how close it is to the received word.

In contrast, we want a derandomization that does not increase the run-time substantially. Randomized local (i.e., sub-linear time) decoding provably cannot be derandomized without increasing the run-time significantly (to linear run-time), since any deterministic decoder must read the entire received word. However, the paper [11] succeeds in derandomizing (global) decoding without significantly increasing the runtime. Unfortunately, the derandomization requires the unique decoding setup.

The paper [11] assumes that the code is locally correctable. Local correction is similar to local decoding, except that the corrector receives $i\in [n]$ and wishes to find $C{(x)}_i$.

The approach of [11] is to iteratively decrease the number of corruptions in the received word by local correction. The insight is to decrease the number of corruptions only by a factor $n^{o(1)}$ in each iteration, and show that only $n^{o(1)}$ randomness strings suffice for such a small improvement. Since one can test each randomness string in linear time (comparing the corrected word with the received word), one gets time $n^{1+o(1)}$ overall.

The idea of iterative correction worked in the unique decoding setting, where there is a single codeword we wish to correct, and there is a natural progress measure, namely the distance to that codeword. In this paper, we generalize this approach to the case of the codewords list recovery problem (See Definition 4).

The input to the codewords list recovery problem consists of $n$ sets of up to $\mathrm{\ell }$ symbols each, denoted $W_1,\mathrm{\dots },W_n\subseteq \mathrm{\Sigma }$.

It is guaranteed that there are $\mathrm{\ell }$ global codewords $Q^1,\mathrm{\dots },Q^{\mathrm{\ell }}$ such that all sets $W_i$, except perhaps $\delta n$, are consistent with the global codewords, i.e., $W_i=\{Q_i^1,\mathrm{\dots },Q_i^{\mathrm{\ell }}\}$. We refer to the $i\in [n]$ where there is no consistency as a corruption. The goal of the algorithm is to find the $\mathrm{\ell }$ global codewords $Q^1,\mathrm{\dots },Q^{\mathrm{\ell }}$.

Note that for $\mathrm{\ell }=1$ this problem is precisely the unique decoding problem. We generalize the unique decoding algorithm of [11] from $\mathrm{\ell }=1$ to general $\mathrm{\ell }$. The algorithm is described in detail in Section 4.

The algorithm gradually decreases the number $\delta n$ of corrupted lists from a small constant $\delta$ until it reaches (i.e., no corruptions). When all lists are consistent with the $\mathrm{\ell }$ codewords, there is a time and space efficient algorithm for identifying the codewords that give those lists (see Lemma 26). As in the unique decoding case [11], the algorithm decreases the number of corrupted lists, $\delta n$, using local correction, except that now local correction manipulates sets of $\mathrm{\ell }$ symbols instead of individual symbols. We will elaborate on local correction of the Reed-Muller code, and how to manipulate $\mathrm{\ell }$ symbols, in the next subsection. Overall, we get an almost-linear time and sub-linear space algorithm for the codewords list recovery problem of Reed-Muller codes.

In this subsection we discuss local correction in the list decoding regime, which we refer to as local list correction. Recall that we discussed local correction in the unique decoding regime in Section 2.1. Local list correction is crucial both for the algorithm for codewords list recovery, and for the reduction of list decoding to codewords list recovery.

There are several ways to define local correction in the list decoding regime, so first we discuss the definition we use and contrast it with another standard definition. The corrector is given oracle access to a highly corrupted codeword. Let $\mathrm{\ell }$ denote the number of codewords in the $\gamma$-list decoding of the received word. On input an index $i\in [n]$ the corrector wishes to find the $i$’th symbol of each of the $\mathrm{\ell }$ codewords in the list decoding using a small number of queries to the word. One standard definition of local list correctors involves outputting $\mathrm{\ell }$ different circuits, each consistent with a single codeword. On input $i\in [n]$ the $j$’th circuit outputs the $i$’th symbol of the $j$’th codeword. We use a weaker definition, where the corrector only needs to output at most $\mathrm{\ell }$ symbols for the $i$’th index, containing the symbols from the $\mathrm{\ell }$ codewords, but without associating each with its codeword. The definition we use for local correction is as follows.

We focus on the Reed-Muller code, which is perhaps the most natural locally correctable code (See also the survey by Yekhanin [51] on local decoding). First, let us formally define the Reed-Muller code: For natural numbers $\text{dim},\text{deg}\ge 1$ and a finite field $𝔽$ the degree deg Reed-Muller code over ${𝔽}^{\text{dim}}$ is the set of dim-variate, total degree deg polynomials. The codeword length is $n=|{𝔽}^{\text{dim}}|$, the alphabet is $𝔽$, and we identify the indices $i\in [n]$ with points $x\in {𝔽}^{\text{dim}}$. The codeword consists of the evaluations of the polynomial on all points in ${𝔽}^{\text{dim}}$. That is, for a polynomial $p:{𝔽}^{\text{dim}}\to 𝔽$, the corresponding codeword is ${(p(x))}_{x\in {𝔽}^{\text{dim}}}$.

The Reed-Muller code has a simple local list correction [4, 47], which we describe next. Given a received word $w:{𝔽}^{\text{dim}}\to 𝔽$ and a point to correct $x\in {𝔽}^{\text{dim}}$, local correction is as follows:

1. 1.

   Pick a line through $x$ in ${𝔽}^{\text{dim}}$ uniformly at random.

2. 2.

   Perform Reed-Solomon list decoding [46, 24, 19] of the restriction of $w$ to the line to find degree-deg polynomials with at least $\approx \gamma$ agreement.

3. 3.

   Output the evaluations of all the polynomials from step 2 on $x$.

The corrector only queries $|𝔽|$ points out of $n=|{𝔽}^{\text{dim}}|$, and is therefore local. Given access to $w$ which is a codeword $Q$, the corrector always outputs $Q(x)$. The idea is that if $w$ agrees with a polynomial $Q$ on a large fraction of the points in ${𝔽}^{\text{dim}}$, then a uniform line is expected to contain a similar fraction of points they agree on. Therefore, $Q(x)$ would probably be outputted. On the other hand, if there are few $x\in {𝔽}^{\text{dim}}$ such that $w(x)\notin \{Q^1(x),\mathrm{\dots },Q^{\mathrm{\ell }}(x)\}$ where $Q^1,\mathrm{\dots },Q^{\mathrm{\ell }}$ is the list decoding of $w$, a random line will rarely contain enough of those to output a symbol inconsistent with $Q^1,\mathrm{\dots },Q^{\mathrm{\ell }}$.

The property of lines that enables local correction is sampling:

In the context of local correction, the set $A$ corresponds to corrupted symbols in $w$, or to points where $w$ agrees with a codeword $Q$. Note the dependence of the error probability $\delta \mu$ on $\mu$ (the relative size of $A$). Hence, when $\mu$ corresponds to the fraction of corruptions in $w$, the sampling error is appropriately smaller.

Like [11], we will need the following variations on local correction, used here in the list decoding regime instead of the unique decoding regime:

In the next subsection we describe the reduction of the list decoding problem to the codewords list recovery problem in efficient time-space. This reduction completes our list decoding algorithm. For the reduction, we crucially rely on incorporating local testing in our local correction. The use of a local testing theorem is new to the list decoding regime and did not appear in the time-space efficient unique decoding algorithm [11].

In this subsection we discuss the definition of local testing we use and contrast it with other standard definitions. In local testing, there is oracle access to a word in ${\mathrm{\Sigma }}^n$, which may or may not agree much with a codeword. The tester uses randomness to make a small number of queries to the word. The tester accepts if there exists a codeword that is consistent with the outcome of its queries. Otherwise, the tester rejects. This way, queries to codewords are always accepted. In contrast, words that are far from the code should be rejected with good probability. The definition we use asks that the rejection probability of the tester equals the distance of the word from a codeword up to a small additive term (equivalently, the acceptance probability of the tester equals the agreement of the word with a codeword up to a small additive term):

The additive approximation definition is much stronger than other definitions of local testing that are sometimes considered. In many definitions, certain distance from the code implies a certain rejection probability, but farther distance from the code does not necessitate higher rejection probability. A different standard definition requires that the probability that the tester rejects provides a multiplicative approximation (with a factor strictly larger than $1$) of the distance to a codeword. This definition allows the distinguishing of codewords from words that have noticeable distance from the code, but does not provide useful information if $w$ is very far from the code. The small additive approximation in Definition 11 means that one can detect codewords even if they agree with the received word on a very small fraction of positions.

A slight modification of the local corrector of the Reed-Muller code described in the previous section, namely replacing lines with certain $O(1)$-dimensional subspaces, makes the corrector into a local tester with a small additive approximation ${|𝔽|}^{-\mathrm{\Omega }(1)}$ [36]. This means that, except with probability ${|𝔽|}^{-\mathrm{\Omega }(1)}$, whenever a word agrees locally (on a random $O(1)$-dimensional subspace) with a low degree polynomial, this low degree polynomial is consistent with one of the global low degree polynomials close to the word. In other words, there cannot be more than ${|𝔽|}^{-\mathrm{\Omega }(1)}$ fraction of the $O(1)$-dimensional subspaces on which the word agrees with a low degree polynomial, without the local low degree polynomial agreeing with one of the global low degree polynomials that are close to the word.

At the time of writing this paper, we do not know of other codes with a randomness-efficient local corrector and a small additive approximation. This is the reason our result is only for Reed-Muller codes. In the subsection that follows we discuss the time-space efficient reduction from list decoding to codewords list recovery, and give more details about the reason for using local testing.

In this subsection we describe the time-space efficient reduction from list decoding to codewords list recovery. This reduction is one of the key contributions of the current work. In the reduction we use the local list correction of Subsection 2.3, combined with local testing, as described in Subsection 2.4. In the list decoding problem, we are given oracle access to a word $w:{𝔽}^{\text{dim}}\to 𝔽$ and we wish to find all the dim-variate polynomials $Q^1,\mathrm{\dots },Q^{\mathrm{\ell }}$ of degree at most deg that agree with $w$ on at least $\gamma$ fraction of the points in ${𝔽}^{\text{dim}}$. In codewords list recovery, we are given a list of sets of symbols, call it $W$, such that for most $x\in {𝔽}^{\text{dim}}$ we have that $W(x)=Q(x)$, where $Q(x)=\{Q^1(x),\mathrm{\dots },Q^{\mathrm{\ell }}(x)\}$, and we want to find $Q^1,\mathrm{\dots },Q^{\mathrm{\ell }}$. We wish to construct a codewords list recovery instance that corresponds to the list decoding of $w$.

Recall that local list correction as in subsection 2.3 converts an input word $w$ to a list of sets $W$. This algorithm falls short of a reduction due to two issues: (1) It does not guarantee a precise equality $W(x)=Q(x)$ for most $x\in {𝔽}^{\text{dim}}$. (2) It is randomized. In the remainder of this subsection we explain how to resolve issue (1). Issue (2) is resolved thanks to average-case local correction. If there are only $n^{o(1)}$ randomness strings per $x$, our algorithm can try all of them and pick the majority outcome. Note that here we use the fact there is only one correct outcome per $x$, namely the list $Q(x)$.

Towards resolving issue (1), note that there are two ways that we could have $W(x)\ne Q(x)$. One is that $Q(x)⊈W(x)$, and the other is that $W(x)⊈Q(x)$. That is, the first way is that $W(x)$ could be missing symbols from $Q(x)$; we call these in-codeword errors. The other is $W(x)$ could contain extra symbols not in $Q(x)$; We call these out-of-codeword errors. In-codeword errors mean that there is a global codeword that is close to $w$ but is missed in the local corrector sample. This is a sampling error, and it is rare as discussed in Subsection 2.3. In contrast, out-of-codeword errors correspond to symbols that appear in the local sample of the corrector, but not in any global codeword that is close to $w$. Our key idea is that out-of-codeword errors are rare if the local corrector is also a local tester. This follows from the definition of a local tester discussed in Subsection 2.4. Local testing precludes a situation where many of the local polynomials the corrector sees do not correspond to any global codeword that is close to $w$. As explained in Subsection 2.4, we adapt our local corrector to incorporate local testing by querying certain $O(1)$-dimensional subspaces instead of lines. Importantly, we only use subspaces for the reduction to codewords list recovery. Everywhere else in this work, local correction uses more query efficient correctors.

In this section, we will briefly define erasure decoding. An erasure of a word is just the same word with some of the symbols erased.

The idea of erasure decoding is that instead of corruption being a symbol change, corruption is a symbol being replaced with a special empty symbol outside the original alphabet. In erasure decoding, the decoder knows what symbols are corrupted, but not what their original value was. In the standard definition of erasure decoding, one does not know what symbols will be erased before hand. Our results hold even if one does know which symbols will be erased. Finally, our results are stated most naturally in terms of correction, so we will define targeted erasure correction.

Erasure decoding is easier than standard decoding because one can reduce erasure decoding to standard decoding by guessing the erased symbols.

Now we will give a slightly more formal overview of the proof. In our proof, it is useful to imagine that the corrector gets as input a uniformly random codeword, and is trying to read just enough of it to learn a few symbols. At any given point in time, the corrector has some state which is reached by some specific set of codewords. The first observations is that since there are few states, the state reached with high probability must be reached by many other codewords. In Lemma 16 we argue that as long as there are enough codewords that map to the current state, the corrector must read a lot of symbols before outputting the next $S+1$ corrections. We then use Lemma 16 many times in Theorem 17 to give the final result.

An improving set is a set of deterministic local functions that takes as input a string near a codeword and outputs another string that in expectation is closer to that codeword. Improving sets were defined in [11] to allow time and space efficient global decoding. In this paper we use a generalization called a list improving set which takes as input a multi-string that is near a codeword multi-string (a multi-string that is exactly made from codewords) and in expectation outputs a multi-string closer to that codeword multi-string.

One technical note is that we separate the kind of errors in an input multi-string into two kinds. The in-codeword, or completeness, errors where there are symbols missing in the multi-string that are in a codeword, and the out-of-codeword, or soundness, errors where there are symbols in the multi-string that are not in a codeword. By separating the two we are able to handle many more out-of-codeword errors since we start with fewer in-codeword errors.

A straightforward consequence of this definition is a test for how close a multi-string is to a codeword multi-string. Specifically, we can test if some $y$ is closer to the codewords that $w$ is close to.

To run our list recovery algorithm, we need to first construct list improving sets. In fact, our list improving sets use the same correcting lines used by [11] to construct their improving sets. Our corrector uses a set of pseudorandom lines through a point, corrects along each, and takes a majority vote. We will now more formally define what properties our lines must have to give us a good list improving set.

The first concept is called “correcting lines”. Correcting lines for a given index $x\in {𝔽}^{\text{dim}}$ are just a set of lines that pass through $x$. A set of such correcting lines will be good if less than half over-sample the set of corruptions.

A correcting lines set is a set of correcting lines (so it is a set of sets of lines) such that for any set $A$, most correcting lines are $ϵ$-sampling for $A$. If this is true, then we can do error correction. Specifically, we need the probability that correcting lines are not $ϵ$-sampling to be proportional to the size of $A$ so the correction always decreases the number of errors.

We use the same correcting lines as used in the prior work. The following result is proved during the proof of [11, Lemma 8.11]. This correcting line set is made by using an $ϵ$-biased set to make a subspace sampler, and then sampling lines in that subspace.

In prior work, Cook and Moshkovitz [11] showed that correcting line sets give improving sets for Reed-Muller codes. We show that they further give list improving sets.

Now using the correcting lines, we can get list improving sets, which give us codewords list recovery. Now we just need to convert the codewords list recovery into regular list recovery. Essentially, we need some way to associate each symbol in the multi-string with the specific codeword it is associated with so we can print the codewords in order.

We use the special properties of Reed-Muller codes to show how to take a multi-string codeword and efficiently output the corresponding list of codewords. In particular, that for every two points, there is a local code that contains those two points (namely, the low degree polynomials on the line between them).

Now, we can use our correcting lines from Lemma 24 with Lemma 25 to get a list improving set. We can use that list improving set with Lemma 21 to recover the codeword multi-string. Finally we use Lemma 26 to turn that codeword multi-string into the distinct codewords. All together, this gives us efficient list recovery in the low error regime. In Section 6 we combine Lemma 27 with the results in Section 5 to get list decoding in the high error regime.