{'fraction_non_alphanumeric': 0.053413271562883224, 'fraction_numerical': 0.0175091974383431, 'mean_word_length': 4.035506003430532, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
List Decoding Barnes-Wall Lattices

The question of list decoding error-correcting codes over finite fields (under the Hamming metric) has been widely studied in recent years. Motivated by the similar discrete structure of linear codes and point lattices in R^N, and their many shared applications across complexity theory, cryptography, and coding theory, we initiate the study of list decoding for lattices. Namely: for a lattice L in R^N, given a target vector r in R^N and a distance parameter d, output the set of all lattice points w in L that are within distance d of r. In this work we focus on combinatorial and algorithmic questions related to list decoding for the well-studied family of Barnes-Wall lattices. Our main contributions are twofold: 1) We give tight (up to polynomials) combinatorial bounds on the worst-case list size, showing it to be polynomial in the lattice dimension for any error radius bounded away from the lattice's minimum distance (in the Euclidean norm). 2) Building on the unique decoding algorithm of Micciancio and Nicolosi (ISIT '08), we give a list-decoding algorithm that runs in time polynomial in the lattice dimension and worst-case list size, for any error radius. Moreover, our algorithm is highly parallelizable, and with sufficiently many processors can run in parallel time only poly-logarithmic in the lattice dimension. In particular, our results imply a polynomial-time list-decoding algorithm for any error radius bounded away from the minimum distance, thus beating a typical barrier for error-correcting codes posed by the Johnson radius.


Introduction
A linear error-correcting code C of block length N and dimension K over a field F is a K-dimensional subspace of F N , generated as all F-linear combinations of K linearly independent vectors. The code's minimum distance, denoted d(C), is the minimum Hamming distance between any two distinct codewords in C, or equivalently the minimum Hamming weight over all nonzero codewords. It is often convenient to normalize distances by the dimension, yielding the relative (minimum) distance δ(C) = d(C)/N of the code. Similarly, a point lattice of dimension N and rank K (where often K = N ) is a discrete additive subgroup of R N (or C N ), generated as all integer linear combinations of K linearly independent vectors. The lattice's minimum distance λ(L) is the minimum Euclidean norm over all nonzero lattice points x ∈ L. Here it can also be convenient to normalize by the dimension, and for a closer analogy between the Hamming and Euclidean distances, in what follows we work with the relative squared distance (abbreviated rsd) δ(x, y) = δ(x − y) on R N or C N , where δ(z) = 1 The relative squared minimum distance (abbreviated rsmd) δ(L) of a lattice is therefore δ(L) = λ(L) 2 /N .
Codes and lattices are intensely studied objects, with many applications in computational complexity, cryptography, and coding theory. In particular, both kinds of objects can be used to encode data so that it can be recovered reliably after being sent over a noisy channel. A central question associated with codes is unique decoding: given a received word r ∈ F N within relative Hamming distance less than δ(C)/2 of some codeword w ∈ C, find w. Similarly, the unique (also known as bounded-distance) decoding problem on lattices is: given a received word r ∈ R N within rsd less than δ(L)/4 of some lattice vector v ∈ L, find v. (Note that the 1/4 factor arises because distances are squared in our formulation.) For error-correcting codes, Elias [14] and Wozencraft [48] proposed extending the classical unique decoding problem to settings where the amount of error could cause ambiguous decoding. More precisely, the goal of list decoding is to find all codewords within a certain relative distance (typically exceeding d(C)/2) of a received word; in many cases, the list is guaranteed to contain few codewords. The first breakthrough algorithmic list decoding results were due to Goldreich and Levin [17] for the Hadamard code, and to Sudan [42] and Guruswami-Sudan [24] for Reed-Solomon codes. These results and others have had countless applications, e.g., in building hard-core predicates for one-way functions [17], in hardness amplification [45], in learning Fourier coefficients [30,16,2], and in constructing randomness extractors [46,47,26].
There are two central tasks associated with list decoding: combinatorially bounding the number of codewords within a given radius of a received word, and algorithmically finding these codewords. An important question in understanding list decodability is finding the list-decoding radius of the code, i.e., the maximum distance from a received word within which the number of codewords is guaranteed to be polynomial in the input parameters.
The Johnson bound. Under the Hamming metric, the Johnson bound gives a distance up to which list decoding is guaranteed to be combinatorially efficient. One version of the Johnson bound states that for any code C of relative distance δ, a Hamming ball of relative radius J(δ) − ǫ contains at most 1/ǫ 2 codewords, and a ball of relative radius J(δ) contains at most δN 2 |F| codewords, where J(δ) = 1 − √ 1 − δ. The Johnson bound is generic since it does not use any structure of the code (not even linearity), and in many cases it is not necessarily the same as the list-decoding radius. It is, however, a barrier in the current analysis of combinatorial list decoding for many well-studied families like Reed-Solomon codes, algebraic geometry codes, Chinese remainder codes, and others. The breakthrough works of Parvaresh-Vardy [36] and Guruswami-Rudra [23] gave families of codes which could be (efficiently) list decoded beyond the Johnson bound, and were followed by several related combinatorial and algorithmic results for other codes (e.g., [9,19,29,18]). For more detailed surveys on list decoding of codes we refer to [43,20,21,22].

Contributions
Motivated by the common discrete linear structure of codes and lattices, we initiate the study of list decoding for lattices, from both a combinatorial and algorithmic perspective. Conway and Sloane [7] promoted the applicability of lattices in practice as alternatives to codes. Therefore, our study is motivated by practical applications in error-tolerant communication, but primarily by the naturalness of the list-decoding problem from a mathematical and computational perspective, and we hope that our work will find other applications in theoretical computer science.
In this work we focus on the Barnes-Wall (BW) [4] family of lattices in C N , which have been wellstudied in coding theory (see, e.g., [27,28,3,35,40]) and share many connections to the Reed-Muller [34,39] family of error-correcting codes (we elaborate below). Barnes-Wall lattices were first constructed in order to demonstrate dense sphere packings, a feature that makes them useful in communications settings. Minimum-distance decoding algorithms for BW lattices were given in [27,38,41], but they are either for fixed low dimensions or have runtimes exponential in the lattice dimension N . Micciancio and Nicolosi [33] gave the first poly(N )-time algorithms for bounded-distance (unique) decoding of any BW lattice up to δ/4 relative error, along with parallel versions which run in as little as polylog(N ) parallel time on sufficiently many processors. They also posed list decoding of BW lattices as an open problem.
Our main contributions are twofold: 1. We give tight (up to polynomials) combinatorial bounds on the worst-case list size for BW lattices, showing it to be polynomial in the lattice dimension N for any relative squared distance (rsd) bounded away from the rsmd δ of the lattice. (See Theorems 1.2 and 1.3 below for precise statements.) We note that it was already known that the list size is super-polynomial N Θ(log N ) when the rsd equals δ (see, e.g., [7, Chapter 1, §2.2, page 24]).
2. We give a corresponding list-decoding algorithm that, for any rsd, runs in time polynomial in the lattice dimension and worst-case list size. Our algorithm is a variant of the Micciancio-Nicolosi uniquedecoding algorithm, and as such it is also highly parallelizable: with sufficiently many processors it runs in only poly-logarithmic O(log 2 N ) parallel time.
We note that Johnson-type bounds for lattices are known and easy to obtain (in fact, the Johnson bound for codes under the Hamming metric is typically proved by reducing it to a packing bound in R N under the Euclidean norm; see, e.g., [5,25,44,32]). For a lattice L ⊂ C N with rsmd δ, the list size for rsd δ · ( 1 2 − ǫ) is at most 1 2ǫ , and for rsd δ 2 is at most 4N (see Lemma 2.3). Interestingly, the latter bound is tight for BW lattices (see Corollary 2.4). Since δ = 1 for every BW lattice, our combinatorial and algorithmic results for rsd up to 1 therefore apply far beyond the Johnson bound.
To describe our results in more detail, we need to define Barnes-Wall lattices. Let G = Z[i] be the ring of Gaussian integers, and let φ = 1 + i ∈ G. Definition 1.1 (Barnes-Wall lattice). The nth Barnes-Wall lattice BW n ⊆ G N of dimension N = 2 n is defined recursively as BW 0 = G, and for positive integer n ≥ 1 as One can check that BW n is a lattice; indeed, it is easy to verify that it is generated as the G-linear combinations of the rows of the n-fold Kronecker product A simple induction proves that the minimum distance of BW n is √ N , i.e., its rsmd is δ = 1. 1 Also observe that if [u, w = u + φv] ∈ BW n for u, w ∈ C N/2 , then [w, u] ∈ BW n : indeed, we have w, −v ∈ BW n−1 and so [w, u = w + φ · −v] ∈ BW n . The mathematical and coding properties of Barnes-Wall lattices have been studied in numerous works, e.g., [1,7,27,28,35,40,41,33].
Combinatorial bounds. Let ℓ(η, n) denote the worst-case list size (over all received words) for BW n at rsd η. We prove the following upper bound. Theorem 1.2. For any integer n ≥ 0 and real ǫ > 0, we have Moreover, we show that the above bound is tight, up to polynomials.
As previously mentioned, it is also known that at rsd η = 1, the maximum list size ℓ(1, n) is quasipolynomial N Θ(log N ) in the lattice dimension, and is achieved by letting the received word be any lattice point [7, Chapter 1, §2.2, page 24]. Because the rsmd of BW n is exactly 1, here we are just considering the number of lattice points at minimum distance from the origin, the so-called "kissing number" of the lattice.
List-decoding algorithm. We complement the above combinatorial bounds with an algorithmic counterpart, which builds upon the unique (bounded-distance) decoding algorithm of Micciancio and Nicolosi [33] for rsd up to 1 4 .

Theorem 1.4.
There is a deterministic algorithm that, given any received word r ∈ C N and η ≥ 0, outputs the list of all points in BW n that lie within rsd η of r, and runs in time O(N 2 ) · ℓ(η, n) 2 .
We also remark that the algorithm can be parallelized just as in [33], and runs in only polylogarithmic O(log 2 N ) parallel time on p ≥ N 2 · ℓ(η, n) 2 processors. Theorems 1.2 and 1.4 immediately imply the following corollary for η = 1 − ǫ.

Corollary 1.5.
There is a deterministic algorithm that, given a received word r ∈ C N and ǫ > 0, outputs the list of all lattice points in BW n that lie within rsd (1 − ǫ) of r, and runs in time Given the lower bounds, our algorithm is optimal in the sense that for any constant ǫ > 0, it runs in poly(N ) time for rsd 1 − ǫ, and that list decoding in poly(N ) time is impossible (in the worst case) at rsd 1.
This is better than the normalized minimum distance 1 of the integer lattice G N , but worse that the largest possible of Θ( √ N ) for N -dimensional lattices.

Proof Overview and Techniques
Combinatorial bounds. Our combinatorial results exploit a few simple observations, some of which were also useful in obtaining the algorithmic results of [33]. The first is that by the Pythagorean theorem, if η = δ(r, w) is the rsd between a received vector r = [r 0 , r 1 ] ∈ C N and a lattice vector The second observation (proved above) is that BW lattices are closed under the operation of swapping the two halves of their vectors, namely, [w 0 , w 1 ] ∈ BW n if and only if [w 1 , w 0 ] ∈ BW n . Therefore, without loss of generality we can assume that δ(r 0 , w 0 ) ≤ η, while incurring only an extra factor of 2 in the final list size. A final important fact is the relationship between the rsd's for the two Barnes- Our critical insight in analyzing the list size is to carefully partition the lattice vectors in the list according to their distances from the respective halves of the received word. Informally, a larger distance on the left half (between r 0 and u) allows for a larger list of u's, but also implies a smaller distance on the right half (between 1 φ (r 1 − u) and v), which limits the number of possible corresponding v's. We bound the total list size using an inductive argument for various carefully chosen ranges of the distances at lower dimensions. Remarkably, this technique along with the Johnson bound allows us to obtain tight combinatorial bounds on the list size for distances all the way up to the minimum distance.
As a warm-up example, which also serves as an important step when analyzing larger rsd's, Lemma 2.5 gives a bound of ℓ( 5 8 , n) ≤ 4 · 24 n = poly(N ) for rsd η = 5 8 . This bound is obtained by partitioning according to the two cases δ(r 0 , u) ∈ [0, 5 12 ) and δ(r 0 , u) ∈ [ 5 12 , 5 8 ], which imply that the rsd between v and 1 φ (r 1 − u) is at most 5 8 and 5 12 , respectively. When bounding the corresponding number of u's and v's, the rsd's up to 5 12 < 1 2 are handled by the Johnson bound, and rsd's up to 5 8 are handled by induction on the dimension.
To extend the argument to rsd's up to η = 1 − ǫ, we need to partition into three cases, including ones which involve rsd's 1 − 3ǫ 2 and 3 4 . In turn, the bound for rsd 3 4 also uses three cases, plus the above bound for rsd 5 8 . Interestingly, all our attempts to use fewer cases or a more direct analysis resulted in qualitatively worse list size bounds, such as N O(log 2 (1/ǫ)) or worse.
Lastly, our lower bounds from Theorem 1.3 are obtained by using a representation of BW lattices in terms of RM codes (see Fact 2.7), and by adapting the lower bounds from [19] for RM codes to BW lattices.
List-decoding algorithm. A natural approach to devising a list-decoding algorithm using the above facts (also used in the context of Reed-Muller codes [19]) is to first list decode the left half r 0 of the received word to get a list of u's, and then sequentially run through the output list to decode the right half 1 φ (r 1 − u) and get a corresponding list of v's for each value of u. However, because the recursion has depth n, the straightforward analysis reveals a super-polynomial runtime N Ω(n) for rsd η ≥ 1/2, because the list size at depth d can be ≥ 4N/2 d .
Instead, our list-decoding algorithm is based on the elegant divide-and-conquer algorithm of [33] for bounded-distance (unique) decoding, which decodes up to half the minimum distance (i.e., η = 1 4 ) in quasi-linearÕ(N ) time, or even poly-logarithmic O(log c N ) parallel time on a sufficiently large poly(N ) number of processors.
The main feature of the algorithm, which we exploit in our algorithm as well, is the use of a distancepreserving linear automorphism T of the BW lattice, i.e., T (BW n ) = BW n (see Fact 3.1). In particular, a lattice vector w ∈ BW n can be reconstructed from just one arbitrary half of each of w = [w 0 , w 1 ] and T (w) = [T 0 (w), T 1 (w)]. Recall that for a received word r = [r 0 , r 1 ] (where r i ∈ C N/2 ), we are guaranteed that δ(r b , w b ) ≤ δ(r, w) for some b ∈ {0, 1}, and similarly for T (r) and T (w). These facts straightforwardly yield a divide-and-conquer, parallelizable list-decoding algorithm that recursively list decodes each of the four halves r 0 , r 1 , T 0 (r), T 1 (r) and reconstructs a list of solutions by combining appropriate pairs from the sub-lists, and keeping only those that are within the distance bound. The runtime of this algorithm is only quadratic in the worst-case list size, times a poly(N ) factor (see Section 3). We emphasize that the only difference between our algorithm and the MN algorithm is the simple but crucial observation that one can replace single words by lists in the recursive steps. The runtime analysis, however, is entirely different, because it depends on the combinatorial bounds on list size.

Comparison with Reed-Muller Codes
Here we discuss several common and distinguishing features of Barnes-Wall lattices and Reed-Muller codes.
The recursive definition of RM codes already hints at structural similarities between BW lattices and RM codes. Indeed, BW lattices can be equivalently defined as evaluations modulo φ n of (Gaussian) integer multilinear polynomials in n variables over the domain {0, φ} n . Recall that an integer multilinear polynomial p ∈ G[x 1 , . . . , x n ] is one whose monomials have degree at most one in each variable (and hence total degree at most n), i.e., p(x 1 , . . . , where each a S ∈ G. A simple inductive argument proves the following lemma. Thus, while RM d n codewords correspond to low-degree polynomials (when d is small), BW lattice points correspond to possibly high-degree polynomials. As an immediate application, our main theorems imply the following corollary regarding the set of integer multilinear polynomials that approximate a function f : {0, φ} n → C. Just as in our algorithmic results for BW lattices, the recursive structure of RM codes is critically used in list-decoding algorithms for these codes, but in a different way than in our algorithm. The list-decoding algorithm for RM d n given in [19] recursively list decodes one of the halves of a received word, and then for each codeword in the list it recursively list decodes the other half of the received word. The recursion has depth d and thus has a total running time of poly(N ) · ℓ(η) d , where ℓ(η) is the list size at relative (Hamming) distance η. As mentioned above, a similar algorithm can work for BW lattices, but the natural analysis implies a super-polynomial ℓ(η) n lower bound on the running time, since now the recursion has depth n. The reason we can overcome this potential bottleneck is the existence of the linear automorphism T of BW n , which allows us to make only a constant number of recursive calls (independently of each other), plus a poly(N ) · ℓ(η) 2 -time combining step, which yields a runtime of the form O(1) n · poly(N ) · ℓ(η) 2 = poly(N ) · ℓ(η) 2 .
We note that RM d n codes are efficiently list decodable up to a radius larger than the minimum distance [19], and remark that while RM codes are some of the oldest and most intensively studied codes, it was not until recently that their list-decoding properties have been very well understood [37,19,29].

Other Related Work
Cohn and Heninger [6] study a list-decoding model on polynomial lattices, under both the Hamming metric and certain 'non-Archimedian' norms. Their polynomial analogue of Coppersmith's theorem [8] implies, as a special case, Guruswami and Sudan's result on list decoding Reed-Solomon codes [24].
Decoding and list decoding in the Euclidean space has been also considered for embeddings into real vector spaces of codes classically defined over finite fields. These embeddings can give rise to so-called spherical codes, where the decoding problem has as input a received vector on the unit sphere, and is required to output the points in the code (also on the unit sphere) that form a small angle with the given target. Another related decoding model is soft-decision decoding, where for each position of the received word, each alphabet symbol is assigned a real-valued weight representing the confidence that the received symbol matches it. Soft decision unique decoding for RM codes was studied in [11,13,12], and listdecoding algorithms were shown in [10,15].
Further, the question of decoding lattices is related to the well-studied vector quantization problem. In this problem, vectors in the ambient space need to be rounded to nearby points of a discrete lattice; for further details on this problem see, for example, [7].
Organization. In Section 2 we prove our combinatorial upper and lower bounds for BW lattices. In Section 3 we present and analyze our main list-decoding algorithm. We conclude with several open problems in Section 4.

Combinatorial Bounds
We start with a few basic definitions. For a lattice L, a vector r ∈ C m (often called a received word) and any η ≥ 0, define L L (r, η) = {x ∈ L : δ(r, x) ≤ η} to be the list of lattice points w ∈ L such that δ(r, w) ≤ η. We often omit the subscript L when the lattice is clear from context. For η ≥ 0 and nonnegative integer n with N = 2 n , we define ℓ(η, n) = max r∈C n |L BWn (r, η)| to be the maximum list size for rsd η, for the nth Barnes-Wall lattice.

Helpful Lemmas
We start with two simple but important observations about Barnes-Wall lattices. The first relates the rsd's between the respective "left" and "right" halves of a received word and a lattice point. The second relates the list sizes for the same rsd but different dimensions. Lemma 2.1. Let r = [r 0 , r 1 ] ∈ C N with r 0 , r 1 ∈ C N/2 , and w = [u, u + φv] ∈ BW n for u, v ∈ BW n−1 . Let η = δ(r, w), η 0 = δ(r 0 , u) and
We next state a Johnson-type bound on the list size for arbitrary lattices; see, e.g., [5,25,44,32] for proofs. Note that these sources work in R N ; our form follows because the standard isomorphism between C N and R 2N as real vectors spaces also preserves Euclidean norm.

Beyond the Johnson Bound
In this section we prove our main combinatorial bounds on the list size for Barnes-Wall lattices BW n ⊆ G N . Our main result is that the list size at rsd (1 − ǫ) is (1/ǫ) O(n) = N O(log(1/ǫ)) for any ǫ > 0. The proof strategy is inductive, and is based on a careful partitioning of the lattice vectors in the list according to the distances of their left and right halves from the respective halves of the received word. Intuitively, the larger the distance on one half, the smaller the distance on the other (Lemma 2.1 above makes this precise). The total list size can therefore be bounded using list bounds for various carefully chosen distances at lower dimensions. Our analysis relies on a poly(N ) list-size bound for rsd 3 4 , which in turn relies on a poly(N ) bound for rsd 5 8 . We first prove these simpler bounds, also using a partitioning argument. (Note that the concrete constants appearing below are chosen to simplify the analysis, and are likely not optimal.) Lemma 2.5. For any integer n ≥ 0, we have ℓ( 5 8 , n) ≤ 4 · 24 n .
Proof of Theorem 1.2. We need to show that ℓ(1 − ǫ, n) ≤ 4 · (1/ǫ) 16n for any n ≥ 0 and ǫ > 0; obviously, we can assume ǫ ≤ 1 as well. The claim is clearly true for n = 0. We proceed by induction on n; namely, we assume that for all γ > 0 it is the case that ℓ(1 − γ, n − 1) ≤ 4 · (1/γ) 16(n−1) . Define the same notation as in the proof of Lemma 2.5, using rsd bound 1 − ǫ instead of 5 8 . As in earlier proofs, we assume that η 0 ≤ 1 − ǫ and account for the accompanying factor of 2 in the list size. We split the analysis into 3 cases: For conciseness, in the calculation below we write ℓ(η) for ℓ(η, n − 1). Using Corollary 2.4, Lemma 2.6, and the inductive hypothesis, it follows that ℓ(1 − ǫ, n) is bounded by , and the proof is complete.
Notice that in the above proof, it is important to use an upper bound like η 0 ≤ 1 − 3ǫ 2 in one of the cases, so that the factor ( 2 3 ) 16(n−1) from the inductive list bound can cancel out the corresponding factor of 24 2(n−1) for the corresponding rsd bound η 1 ≤ 3 4 . This allows the recurrence to be dominated by the term yielding a solution of the form (1/ǫ) O(n) .

Lower Bounds
For our lower bounds we make use of a relationship between Barnes-Wall lattices and Reed-Muller codes, and then apply known lower bounds for the latter.
where the embedding of F 2 into C is given by 0 → 0 and 1 → 1. In particular, any codeword c d ∈ RM n d gives rise to a lattice point φ d · c d ∈ BW n ,

There are
Proof of Theorem 1.3. Let k ≥ 0 be an integer such that 2 n ǫ ≤ 2 k ≤ 2 n+1 ǫ. Let the received word be r = φ k · [1, 0, . . . , 0] ∈ G N , where we assume that the first coordinate is indexed by 0 n ∈ F n 2 . By Fact 2.8 and Fact 2.7, for any subspace H ⊆ F n 2 of dimension n − k, we have φ k · c H ∈ BW n . Notice that By Fact 2.8, there are at least 2 k(n−k) ≥ 2 (n−log 1 ǫ ) log 1 2ǫ subspaces H ⊂ F n 2 of dimension n − k, which completes the proof.

List-Decoding Algorithm
In this section we prove Theorem 1.4 by giving a list-decoding algorithm that runs in time polynomial in the list size; in particular, by Theorem 1.2 it runs in time N O(log(1/ǫ)) for rsd (1 − ǫ) for any fixed ǫ > 0. The runtime and error tolerance are optimal (up to polynomial overhead) in the sense that the list size can be N Ω(log(1/ǫ)) by Theorem 1.3, and can be super-polynomial in N for rsd 1 or more.
The list-decoding algorithm is closely related to the highly parallel Bounded Distance Decoding algorithm of Micciancio and Nicolosi [33], which outputs the unique lattice point within rsd η < 1 4 of the received word (if it exists). In particular, both algorithms work by recursively (and independently) decoding four words of dimension N/2 that are derived from the received word, and then combining the results appropriately. In our case, the runtime is strongly influenced by the sizes of the lists returned by the recursive calls, and so the combinatorial bounds from Section 2 are critical to the runtime analysis.
We need the following easily-verified fact regarding the symmetries (automorphisms) of BW n .
Proof of Theorem 1.4. We need to show that on input r ∈ C N and η ≥ 0, Algorithm 1 runs in time O(N 2 ) · ℓ(η, n) 2 and outputs L = L(r, η).
By the inductive hypothesis and the above observations, we will have (w b , w s ) ∈ L b × L s for at least one choice of (b, s) ∈ {0, 1} × {+, −}. The algorithm calculates the vector w = [w 0 , w 1 ] as a candidate, simply by solving for w 0 , w 1 using w b , w s and the definition of T . Therefore, w will appear in the output list L. And because L ⊆ L(r, η), the claim follows.
We now analyze T (n), the number of operations over C for an input of dimension N = 2 n , which is easily seen to satisfy the recurrence T (n) ≤ 4T (n − 1) + 4 · ℓ(η, n − 1) 2 · O(2 n−1 ) ≤ 4 n · T (0) + n i=1 4 i · ℓ(η, n − i) 2 · O(2 n−i ) Remark 3.2. We note that the above algorithm, like the unique decoder of [33], can be easily parallelized. The parallel time on p processors (counting the number of operations in C) satisfies the recurrence T (n, p) = T (n) if n = 0 or p < 4 T (n − 1, p/4) + O(N · ℓ(η, n − 1) 2 /p + log N ) otherwise, where T (n) is the sequential time computed in Theorem 1.4. This is because it takes O(N · ℓ(η, n − 1) 2 /p) time per processor to combine the lists in Step 6 of the algorithm, and computing the ℓ(η, n − 1) 2 distances in Step 7 requires computing sums of N terms in C, and takes a total of O(N · ℓ(η, n − 1) 2 /p + log N ) parallel time. Notice that when p ≥ N 2 · ℓ(η, n − 1) 2 , the algorithm runs in only polylogarithmic O(log 2 N ) parallel time. Note also that when the list size ℓ(η, n − 1) = 1, our analysis specializes exactly to that of [33].

Discussion and Open Problems
Some immediate open questions arise from comparison to the results in [33]. Motivated by the sequential unique decoder proposed in [33], is there a (possibly sequential) list decoder that runs in time quasilinear in N and the list size, rather than quadratic? Also, as asked in [33], is there an efficient algorithm for solving the Closest Vector Problem (i.e., minimum-distance decoding) on Barnes-Wall lattices? Note that our lower bounds do not rule out the existence of such an algorithm.
An important variant of the list-decoding problem for codes is local list decoding. In this model, the algorithm is required to run in time polylogarithmic in the block length, and output succinct representations of all the codewords within a given radius. Defining a meaningful notion of local decoding for lattices (and BW lattices in particular) would require additional constraints, since lattice points do not in general admit succinct representations (since one needs to specify an integer coefficient for each basis vector). While by the Johnson bound we have a poly(n) list size for rsd up to 1/2 − poly(1/n), achieving a meaningful notion of local decoding in this context would be interesting.
Another interesting direction is to find (or construct) more asymptotic families of lattices with nice listdecoding properties. In particular, are there generic operations that when applied to lattices guarantee good list-decoding properties? For codes, list decodability has been shown to behave well under the tensoring and interleaving operations, as demonstrated in [18]. Since at least tensoring is also well-defined for lattices, understanding its effect in the context of list decoding is a natural further direction.
Finally, it would be also interesting and potentially useful to consider list decoding for norms other than the Euclidean norm, such as the ℓ ∞ or ℓ 0 norms.