OPTIMAL RATE LIST DECODING OVER BOUNDED ALPHABETS
USING ALGEBRAIC-GEOMETRIC CODES

arXiv:1708.01070v1 [cs.CC] 3 Aug 2017

VENKATESAN GURUSWAMI AND CHAOPING XING

Abstract. We give new constructions of two classes of algebraic code families which
are efficiently list decodable with small output list size from a fraction 1 − R − ε of
adversarial errors where R is the rate of the code, for any desired positive constant ε.
The alphabet size depends only ε and is nearly-optimal.
The first class of codes are obtained by folding algebraic-geometric codes using automorphisms of the underlying function field. The list decoding algorithm is based on a
linear-algebraic approach, which pins down the candidate messages to a subspace with a
nice “periodic” structure. The list is pruned by pre-coding into a special form of subspaceevasive sets. Instantiating this construction with the explicit Garcia-Stichtenoth tower
of function fields yields codes list-decodable up to a 1 − R − ε error fraction with list size
bounded by O(1/ε), matching the existential bound for random codes up to constant factors. Further, the alphabet size of the codes is a constant depending only on ε — it can
be made exp(Õ(1/ε2 )) which is not much worse than the lower bound of exp(Ω(1/ε)).
The parameters we achieve are thus quite close to the existential bounds in all three
aspects — error-correction radius, alphabet size, and list-size — simultaneously. Our
code construction is Monte Carlo and has the claimed list decoding property with high
probability. Once the code is (efficiently) sampled, the encoding/decoding algorithms
are deterministic with a running time Oε (N c ) for an absolute constant c, where N is the
code’s block length.
The second class of codes are obtained by restricting evaluation points of an algebraicgeometric code to rational points from a subfield. Once again, the linear-algebraic approach to list decoding to pin down candidate messages to a “periodic” subspace. We
develop an alternate approach based on subspace designs is used to pre-code messages
and prune the subspace of candidate solutions. Together with the subsequent explicit
constructions of subspace designs, this yields the first deterministic construction of an
algebraic code family of rate R with efficient list decoding from 1 − R − ε fraction of
errors over an alphabet of constant size exp(Õ(1/ε2 )). The list size is bounded by a very
slowly growing function of the block length N ; in particular, it is at most O(log(r) N )
(the r’th iterated logarithm) for any fixed integer r. The explicit construction avoids the
shortcoming of the Monte Carlo sampling at the expense of a slightly worse list size.

Extended abstracts announcing these results were presented at the 2012 and 2013 ACM Symposia
on Theory of Computing (STOC) [16, 17]. This is a merged and revised version of these conference
papers, that accounts for the explicit subspace designs that were constructed in [8] subsequent to [17], and
makes some simplifications and improvements in the construction of h.s.e sets in Section 6 compared to [16].
The research of V. Guruswami was supported in part by a Packard Fellowship and NSF grants
CCF-0963975 and CCF-1422045. Some of this work was done during visits by the author to Nanyang
Technological University. Any opinions, findings, and conclusions or recommendations expressed in this
material are those of the author(s) and do not necessarily reflect the views of the National Science
Foundation.
The research of C. Xing was supported by the Singapore MoE Tier 1 grants RG20/13 and RG25/16,
and NTU grant M4081575.

2

V. GURUSWAMI AND C. XING

Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.1.

Prior and related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.2.

Open questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

1.3.

Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2. Our techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.1.

Algebraic ideas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.2.

Pseudorandomness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

3. Periodic subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4. Preliminaries on function fields and algebraic-geometric codes . . . . . . . . . . . . . . . . 11
5. Folded codes from the Hermitian tower . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5.1.

Background on Hermitian tower. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

5.2.

Redefining the code in terms of local expansion at P0 . . . . . . . . . . . . . . . . . . 15

5.3.

List decoding folded codes from the Hermitian tower . . . . . . . . . . . . . . . . . . . 16

6. Subspace evasive sets with additional structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
6.1.

Hierarchical subspace-evasive sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

6.2.

Random sets are hierarchically subspace evasive . . . . . . . . . . . . . . . . . . . . . . . . 19

6.3.

Pseudorandom construction of large h.s.e subsets . . . . . . . . . . . . . . . . . . . . . . . 20

6.4.

Efficient computation of intersection with h.s.e. subsets . . . . . . . . . . . . . . . . 22

7. Folded codes from the Garcia-Stichtenoth tower . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
7.1.

Background on Garcia-Stichtenoth tower . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

7.2.

Redefining the code in terms of local expansion at P∞ . . . . . . . . . . . . . . . . . 25

7.3.

List decoding FGS codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

8. Pruning list for folded AG codes using h.s.e sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
8.1.

Combining folded Hermitian codes and h.s.e sets . . . . . . . . . . . . . . . . . . . . . . . 28

8.2.

Combining folded Garcia-Stichtenoth codes and h.s.e sets . . . . . . . . . . . . . . 29

9. List decoding AG codes with subfield evaluation points . . . . . . . . . . . . . . . . . . . . . . . 31

10.

11.

9.1.

Decoding Reed-Solomon codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

9.2.

Decoding algebraic-geometric codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

9.3.

Decoding the codes from the Garcia-Stichtenoth tower . . . . . . . . . . . . . . . . . 38

Subspace designs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
10.1.

Constructing subspace designs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

10.2.

Cascaded subspace designs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

Good list decodable subcodes of RS and AG codes . . . . . . . . . . . . . . . . . . . . . . . . . . 44
11.1.

Reed-Solomon codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

11.2.

Subcodes of Garcia-Stichtenoth codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

AG CODES & NEAR-OPTIMAL LIST DECODING

3

1. Introduction
An error-correcting code C of block length N over a finite alphabet Σ maps a set M
of messages into codewords in ΣN . The rate of the code C, denoted R, equals N1 log|Σ| |M|.
In this work, we will be interested in codes for adversarial noise, where the channel can
arbitrarily corrupt any subset of up to τ N symbols of the codeword. The goal will be to
correct such errors and recover the original message/codeword efficiently. It is easy to see
that information-theoretically, we need to receive at least RN symbols correctly in order
to recover the message (since |M| = |Σ|RN ), so we must have τ 6 1 − R.

Perhaps surprisingly, in a model called list decoding, recovery up to this informationtheoretic limit becomes possible. Let us say that a code C ⊆ ΣN is (τ, ℓ)-list decodable
if for every received word y ∈ ΣN , there are at most ℓ codewords c ∈ C such that y
and c differ in at most τ N positions. Such a code allows, in principle, the correction
of a fraction τ of errors, outputting at most ℓ candidate codewords one of which is the
originally transmitted codeword.
The probabilistic method shows that a random code of rate R over an alphabet of
size exp(O(1/ε)) is with high probability (1 − R − ε, O(1/ε))-list decodable [2]. However,
it is not known how to construct or even randomly sample such a code for which the
associated algorithmic task of list decoding (i.e., given y ∈ ΣN , find the list of codewords
within fractional radius 1 − R − ε) can be performed efficiently. This work takes a big step
in that direction, giving a randomized construction of such efficiently list-decodable codes
over a slightly worse alphabet size of exp(Õ(1/ε2 )). We note that the alphabet size needs
to be at least exp(Ω(1/ε)) in order to list decode from a fraction 1 − R − ε of errors, so
this is close to optimal. For the list-size needed as a function of ε for decoding a 1 − R − ε
fraction of errors, the best lower bound is only Ω(log(1/ε)) [9], but as mentioned above,
even random coding arguments only achieve a list-size of O(1/ε), which our construction
matches up to constant factors. We also give a fully deterministic construction with a
list-size that is very slowly growing as a function of the block length.
We now review some of the key results on algebraic list decoding leading up to this
work. A more technical comparison with related work appears in Section 1.1. The first
construction of codes that achieved the optimal trade-off between rate and list-decoding
radius, i.e., enabled list decoding up to a fraction 1−R−ε of worst-case errors with rate R,
was due to Guruswami and Rudra [11]. They showed that a variant of Reed-Solomon (RS)
codes called folded RS codes admit such a list decoder. For a decoding radius of 1 − R − ε,
the code was based on bundling together disjoint windows of m = Θ(1/ε2 ) consecutive
symbols of the RS codeword into a single symbol over a larger alphabet. As a result, the
2
alphabet size of the construction was N Ω(1/ε ) . Ideas based on code concatenation and
expander codes can be used to bring down the alphabet size to exp(Õ(1/ε4 )), but this
compromises some nice features such as list recovery and soft decoding of the folded RS
code. Also, the decoding time complexity as well as proven bound on worst-case output
list size for these constructions were N Ω(1/ε) .
Our main final result statement is the following, offering two constructions, one randomized and one deterministic, of variants of algebraic-geometric (AG) codes that are
list-decodable with optimal rate. More detailed statements can be found in the technical
sections of the paper.
Theorem 1.1 (Main). For any R ∈ (0, 1) and positive constant ε ∈ (0, 1), there is
(i) a Monte Carlo construction of a family of codes of rate at least R over an alphabet
size exp(O(log(1/ε)/ε2 )) that are encodable and (1−R−ε, O(1/(Rε))-list decodable

4

V. GURUSWAMI AND C. XING

in Oε (N c ) time1, where N is the block length of the code and c is an absolute
positive constant.
(ii) a deterministic construction of a family of codes of rate at least R over an alphabet
size exp(O(log2 (1/ε)/ε2 )) that are encodable and (1 − R − ε, L(N ))-list decodable
in Oε (N c ) time, for a list size that satisfies L(N ) = o(log(r) N ) (the r’th iterated
logarithm) for any fixed integer r.
The first part of Theorem 1.1 is achieved through folded algebraic-geometric codes
and hierarchical subspace-evasive sets. To fold algebraic-geometric codes, we first find
suitable automorphisms of the ground function field. Consequently, the list of possible
candidate messages has an exponential size, but is well structured. To prune down the
list size, we only encode messages in a subspace-evasive set which has small intersection
with the original list. To make use of subspace-evasive sets efficiently, we have to: (i)
give an explicit pseudorandom construction of these sets; and (ii) encode the messages to
subspace-evasive sets efficiently. We refer to Section 2 for details.
The second part of Theorem 1.1 is obtained through usual algebraic-geometric codes
with evaluation points over subfields and subspace design. As in the fist part, the list of
possible candidate messages has an exponential size, but is well structured. The approach
based on hierarchical subspace-evasive sets in the first part leads to excellent list size;
however, we only know randomized constructions of hierarchical subspace-evasive sets. To
obtain a deterministic list decoding, we prune down the list of possible solutions through
subspace designs (see Section 2 for details).
We note that our Monte Carlo construction gives codes that are quite close to the
existential bounds in three aspects simultaneously — the trade-off between error fraction
1 − R − ε and rate R, the list-size as a function of ε, and the alphabet size of the code
family (again as a function of ε). Even though these codes are not fully explicit, they are
“functionally explicit” in the sense that once the code is (efficiently) sampled, with high
probability the polynomial time encoding and decoding algorithms deliver the claimed
error-correction guarantees for all allowed error pattern. The explicit construction avoids
this shortcoming at the expense of a slightly worse list size. Our algorithms can also be
extended to the “list recovery” setting in a manner similar to [11, 7]; we omit discussion
of this aspect and the straightforward details.
1.1. Prior and related work. Let us recap a bit more formally the construction of
folded RS codes from [11]. One begins with the Reed-Solomon encoding of a polynomial f ∈ Fq [X] of degree < k consisting of the evaluation of f on a subset of field
elements ordered as 1, γ, . . . , γ N −1 for some primitive element γ ∈ Fq and N < q. For
an integer “folding” parameter m > 1 that divides N , the folded RS codeword is defined over alphabet Fm
q and consists of n/m blocks, with the j’th block consisting of the
(j−1)m
m-tuple (f (γ
), f (γ (j−1)m+1 ), . . . , f (γ jm−1 )). The algorithm in [11] for list decodq
ing these codes was based on the algebraic identity f (γX) = f (X) in the residue field
Fq [X]/(X q−1 − γ) where f denotes the residue f mod (X q−1 − γ). This identity is used to
solve for f from an equation of the form Q(X, f (X), f (γX), . . . , f (γ s−1 X)) = 0 for some
low-degree nonzero multivariate polynomial Q. The high degree q > n of this identity,
coupled with s ≈ 1/ε, led to the large bounds on list-size and decoding complexity in [11].
One possible approach to reduce q (as a function of the code length) in this construction would be to work with algebraic-geometric codes based on function fields K
1We use the O (·) notation to hide constant factors that depend on ε.
ε

AG CODES & NEAR-OPTIMAL LIST DECODING

5

over Fq with more rational points. However, an automorphism σ of K that can play the
role of the automorphism f (X) 7→ f (γX) of Fq (X) is only known (or even possible) for
very special function fields. This approach was used in [6] to construct list-decodable
codes based on cyclotomic function fields using as σ certain Frobenius automorphisms.
These codes improved the alphabet size to polylogarithmic in N , but the bound on listsize and decoding complexity remained N Ω(1/ε) . Recently, a linear-algebraic approach to
list decoding folded RS codes was discovered in [27, 7]. Here, in the interpolation stage,
which is common to all list decoding algorithms for algebraic codes [26, 13, 21, 11], one
finds a linear multivariate polynomial Q(X, Y1 , . . . , Ys ) whose total degree in the Yi ’s is
1. The simple but key observation driving the linear-algebraic approach is that the equation Q(X, f (X), . . . , f (γ s−1 X)) = 0 now becomes a linear system in the coefficients of f .
Further, it is shown that the solution space has dimension less than s, which again gives
a list-size upper bound of q s−1 . Finally, since the list of candidate messages fall in an
affine space, it was noted in [7] that one can bring down the list size by carefully “precoding” the message polynomials so that their k coefficients belong to a “subspace-evasive
set” (which has small intersection with every s-dimensional subspace of Fkq ). This idea
was used in [14] to give a randomized construction of (1 − R − ε, O(1/ε))-list decodable
codes of rate R. However, the alphabet size and runtime of the decoding algorithm both
remained N Ω(1/ε) . Similar results were also shown in [14] for derivative codes, where the
encoding of a polynomial f consists of the evaluations of f and its first m − 1 derivatives
at distinct field elements.
Concurrently with our work reported in [16], Dvir and Lovett gave an elegant construction of explicit subspace evasive sets based on certain algebraic varieties [1]. This
yields an explicit version of the codes from [7], albeit with a worse list size bound of
(1/ε)O(1/ε) . This work and [1] are incomparable in terms of results. The big advantage
of [1] is the deterministic construction of the code. The benefits in our work are: (i)
both constructions give codes over an alphabet size that is a constant independent of N ,
2
whereas in [1] the N Ω(1/ε ) alphabet size of folded RS codes is inherited; (ii) our first
Monte Carlo construction ensures list-decodability with a list-size of O(1/ε) that is much
better and in fact matches the full random construction up to constant factors,2 and (iii)
our second construction gives a deterministic algorithm as well with almost constant list
size (and constant alphabet size). Another important feature is that both our work and
[1] achieve a decoding complexity of Oε (N c ) with exponent independent of ε.
Our paper presents two class of codes: folded algebraic-geometric codes and usual
algebraic-geometric codes with evaluation points over subfields. For both the classes of
codes, we can apply hierarchical subspace-evasive sets as well as subspace design to prune
down the list size by taking certain subcodes. This is because of the “periodic” structure of
the subspace in which the candidate messages are pinned down by the linear-algebraic list
decoder is similar in both cases. Thus, we can obtain both randomized and deterministic
algorithms from each of the two classes of codes. In total, we have four combinations
of constructions. To illustrate both algebraic approaches, we decide to focus on two
combinations, i.e., (i) folded algebraic-geometric codes with hierarchical subspace-evasive
sets; and (ii) usual algebraic-geometric codes with evaluation points over subfields with
subspace designs. These are listed in Figure 1. We note that the other two combinations
are also possible, as the pruning of the subspace of solutions is “black-box” with respect
to its periodic structure.
2As mentioned above, the bound in [1] is (1/ε)O(1/ε) and it seems very difficult to get a sub-exponential

dependence on 1/ε with the algebraic approach relying on Bezout’s theorem to construct subspace-evasive
sets.

6

V. GURUSWAMI AND C. XING

Code
Construction Alphabet size List size Decoding time
2
Folded RS/derivative
Explicit
N O(1/ε )
N O(1/ε)
N O(1/ε)
2)
O(1/ε
Folded RS subcode
Monte Carlo
N
O(1/ε)
N O(1/ε)
2
O(1)
Folded RS subcode
Explicit
N O(1/ε )
(1/ε)O(1/ε) N O(1) 21/ε
2
2
2
Folded cyclotomic
Las Vegas
(log N )O(1/ε ) N O(1/ε )
N O(1/ε )
O(1)
Folded AG subcode Monte Carlo exp(Õ(1/ε2 ))
O(1/ε)
N O(1) 21/ε
AG subcode

Explicit

exp(Õ(1/ε2 ))

∗
2
2(log N)

22

Reference
[11, 14]
[14]
[1]
[6]
Thm. 1.1(i)

N O(1) (1/ε)O(ℓ) Thm. 1.1(ii)

Figure 1. Parameters of various constructions of codes that enable list decoding
(1 − R − ε) fraction of errors, with rate R. The last two lines are from this work.
“Explicit” means the code can be constructed in deterministic polynomial time.
The rows with first column in boldface are not dominated by other constructions.
The last line gives the first deterministic construction of algebraic codes for efficient
optimal rate list decoding over constant-sized alphabets.

In the table presented in Figure 1, we list previous results and those in this paper.
The major improvement of this work is to bring down the alphabet size to constant, while
at the same time ensuring small list size and low decoding complexity where the exponent
of the polynomial run time does not depend on ε. Our folded algebraic-geometric subcodes
achieve a list size matching the fully random constructions up to constant factors, together
with alphabet size not much worse than the lower bound exp(Ω(1/ε)). On the last line,
our algebraic-geometric subcodes give a deterministic list decoding with almost constant
list size and optimal decoding radius.
1.2. Open questions. The challenge of decoding up to radius approaching the optimal
bound (1 − R) with rate R along with good list and alphabet size is, for the most part,
solved by our work. There are still some goals that have not been met. One is to get
a fully deterministic construction with constant list-size and alphabet size (as a function
of ε), and construction/decoding complexity Oε (N c ). In this regard, in a recent personal
communication, Kopparty, Ron-Zewi, and Saraf [19] report a construction that achieves
constant list and alphabet size with complexity N c (log log N )O(1/ε) (the list size, while a
constant, grows doubly exponentially in 1/ε). Another challenge is to construct a (1 − R −
ε, L)-list decodable code of rate R (for list size L bounded by a polynomial in the block
length), over an alphabet of size exp(O(1/ε)), which is the asymptotically optimal size.
Note that all constructions over a constant-sized alphabet known so far have alphabet
size at least exp(Ω(1/ε2 )). Finally, the various algebraic and expander-based techiques
that have led to progress on list decoding only work over large alphabets. The challenge
of efficient optimal rate list decoding over say the binary alphabet, even for the simpler
model of erasures, remains wide open. The best known constructions are obtained via
concatenation, and are list-decodable up to the so-called Blokh-Zyablov bound [12].

1.3. Organization. The paper is organized as follows. In Section 2, we describe the
detailed techniques of our paper including algebraic approaches and pseudorandomness.
Following the section on techniques, in Section 3 we introduce periodic and ultra-periodic
subspaces, give definitions and basic properties. In Section 4, we recall some basis results
on function fields and algebraic-geometric codes. To illustrate our ideas in an algebraically
simpler (and perhaps more practical) setting, in Section 5 we give a construction based

AG CODES & NEAR-OPTIMAL LIST DECODING

7

on a tower of Hermitian field extensions [22]. This is capable of giving a similar result
to our best ones based on the Garcia-Stichtenoth tower, albeit with alphabet size and
list-size upper bound polylogarithmic in the code length. In Section 6 we first introduce
hierarchical subspace-evasive sets, then show that random sets are hierarchical subspaceevasive with high probability. We also present a pseudorandom construction of hierarchical
subspace-evasive sets, which also allow for efficient encoding and efficient computation of
intersection with periodic subspaces.
Folded algebraic-geometric codes from the Garcia-Stichtenoth tower are studied in
Section 7. The list size, decoding radius and decoding algorithm via local expansion are
also discussed in this section. Section 8 is devoted to the discussion of pruning down the
list size for folded codes from both the Hermitian and the Garcia-Stichtenoth towers using
hierarchical subspace-evasive sets. The second class of our codes, namely usual algebraicgeometric codes with evaluation points over subfields is presented in Section 9. In this
section, we first discuss list decoding for the simpler Reed-Solomon case, and then generalize it to list decoding of arbitrary algebraic geometric codes and finally instantiate the
approach with the codes from the Garcia-Stichtenoth tower. In Section 10, we introduce
subspace designs and cascaded subspace designs, and discuss parameters of random and
explicit constructions of those. In the last section, the explicit construction of subcodes
of RS and AG subcodes based on subspace designs is presented.
2. Our techniques
We describe some of the main new ingredients that go into our work. We need both
new algebraic insights and constructions, as well as ideas in pseudorandomness relating
to (variants of) subspace-evasive sets. We describe these in turn below.
2.1. Algebraic ideas. It is shown in [13] that one can list decode the usual algebraicgeometric codes up to the Johnson bound. Thus, to list decode the algebraic-geometric
codes beyond the Johnson bound, we have to consider some variants of usual algebraicgeometric codes. In this work, we present two variants of algebraic-geometric codes–folded
algebraic geometric codes and usual algebraic geometric codes with evaluation points over
subfields. We describe these in turn.
2.1.1. Folding AG codes. The first approach is to use suitable automorphisms of function
fields to fold the code. This approach was used for Reed-Solomon codes in [11] and for
cyclotomic function field in [6], though this was done using the original approach in [11]
where the messages to be list decoded were pinned down to the roots of a higher degree
polynomial over a large residue field. As mentioned earlier, effecting this “non-linear”
approach in [11, 6] with automorphisms of more general function fields seems intricate at
best. In this work we employ the linear-algebraic list decoding method of [14]. However,
the correct generalization of the linear-algebraic list decoding approach to the function
field case is also not obvious. One of the main algebraic insights in this work is noting
that the right way to generalize the linear-algebraic approach to codes based on algebraic
function fields is to rely on the local power series expansion of functions from the message
space at a suitable rational point. (The case for Reed-Solomon codes being the expansion
around 0, which is a finite polynomial form.)
Working with a suitable automorphism which has a “diagonal” action on the local
expansion lets us extend the linear-algebraic decoding method to AG codes. Implementing
this for specific AG codes requires an explicit specification of a basis for an associated
message (Riemann-Roch) space, and the efficient computation of the local expansion of

8

V. GURUSWAMI AND C. XING

the basis elements at a special rational point on the curve. We show how to do this for two
towers of function fields: the Hermitian tower [22] and the asymptotically optimal GarciaStichtenoth tower [4, 5]. The former tower is quite simple to handle — it has an easily
written down explicit basis, and we show how to compute the local expansion of functions
around the point with all zero coordinates. However, the Hermitian tower does not have
bounded ratio of the genus to number of rational points, and so does not give constant
alphabet codes (we can get codes over an alphabet size that is polylogarithmic in the
block length though). Explicit basis for Riemann-Roch spaces of the Garcia-Stichtenoth
tower were constructed in [23]. Regarding local expansions, one major difference is that
we work with local expansion of functions at the point at infinity, which is fully “ramified”
in the tower. For both these towers, we find and work with a nice automorphism that acts
diagonally on the local expansion, and use it for folding the codes and decoding them by
solving a linear system.

2.1.2. Restricting evaluation points to a subfield. The second approach is to work with
“normal” algebraic-geometric codes, based on evaluating functions from a Riemann-Roch
space at some rational places, except we use a constant field extension of the function
field for the function space, but restrict to evaluating at rational places over the original
base field. Let use give a brief idea why restricting evaluation points to a subfield enables
correcting more errors. The idea behind list decoding results for folded RS (or derivative)
codes in [11, 14] is that the encoding of a message polynomial f ∈ FQ [X] includes the values
of f and closely related polynomials at the evaluation points. Given a string not too far
from the encoding of f , one can use this property together with the “interpolation method”
to find an algebraic condition that f (and its closely related polynomials) must satisfy, eg.
A0 (X) + A1 (X)f (X) + A2 (X)f ′ (X) + · · · + As (X)f (s−1) (X) = 0 in the case of derivative
codes [14] (here f (i) denotes the i’th formal derivative of f , and the A0 , A1 , . . . , As are
low-degree polynomials found by the decoder). The solutions f (X) to this equation form
an affine space, which can be efficiently found (and later pruned for list size reduction
when we pre-code messages into a subspace-evasive set).
For Reed-Solomon codes as in Definition 12, the encoding only includes the values of
f at α1 , α2 , . . . , αn . But since αi ∈ Fq , we have f (αi )q = f σ (αi ) where f σ is the polynomial
obtained by the action of the Frobenius automorphism that maps y 7→ y q on f (formally,
Pk−1
Pk−1 q j
f σ (X) = j=0
fj X if f (X) = j=1
fj X j ). Thus the decoder can “manufacture” the
2

3

values of f σ (and similarly f σ , f σ , etc.) at the αi . Applying the above approach then
s−1
enables finding a relation A0 (X) + A1 (X)f (X) + A2 (X)f σ (X) + · · · + As (X)f σ (X) = 0,
which is again an Fq -linear condition on f that can be used to solve for f . We remark
here that this approach can also be applied effectively to linearized polynomials, and can
be used to construct variants of Gabidulin codes that are list-decodable up to the optimal
1 − R fraction of errors (where R is the rate) in the rank metric [15].

To extend this idea to algebraic-geometric codes, we work with constant extensions
Fqm · F of algebraic function fields F/Fq . The messages belong to a Riemann-Roch space
over Fqm , but they are encoded via their evaluations at Fq -rational points. For decoding,
we recover the message function f in terms of the coefficients of its local expansion at
some rational point P . (The Reed-Solomon setting is a special case when F = Fq (X),
and P is 0, i.e., the zero of X.) To get the best trade-offs, we use AG codes based on
a tower of function fields due to Garcia and Stichtenoth [4, 5] which achieve the optimal
trade-off between the number of Fq -rational points and the genus. For this case, we recover
messages in terms of their local expansion around the point at infinity P∞ which is also

AG CODES & NEAR-OPTIMAL LIST DECODING

9

used to define the Riemann-Roch space of messages. So we treat this setting separately
(Section 9.3), after describing the framework for general AG codes first (Section 9.2).
2.2. Pseudorandomness. The above algebraic ideas enable us to pin down the messages
into a structured subspace of dimension linear in the message length. The specific structure
of the subspace is a certain “periodicity” — there is a subspace W ⊂ Fm
q such that once
f0 , f1 , . . . , fi−1 (the first i coefficients of the message polynomial) are fixed, fi belongs to a
coset of W . We now describe our ideas to prune this list, by restricting (or “pre-coding”)
the message polynomials to belong to carefully constructed pseudorandom subsets that
have small intersection with any periodic subspace.
2.2.1. Hierarchical subspace-evasive sets. The first approach to follows along the lines
of [14] and only encode messages in a subspace-evasive set which has small intersection
with low-dimensional subspaces. Implementing this in our case, however, leads to several
problems. First, since the subspace we like to avoid intersecting much has large dimension,
the list size bound will be linear in the code length and not a constant like in our final
result. More severely, we cannot go over the elements of this subspace to prune the list
as that would take exponential time. To solve the latter problem, we observe that the
subspace has a special “periodic” structure, and exploit this to show the existence of
large “hierarchically subspace evasive” (h.s.e) subsets which have small intersection with
the projection of the subspace on certain prefixes. Isolating the periodic property of the
subspaces, and formulating the right notion of evasiveness w.r.t to such subspaces, is an
important aspect of this work.
We also give a pseudorandom construction of good h.s.e sets using limited wise independent sample spaces, in a manner enabling the efficient iterative computation of the
final list of intersecting elements. Further our construction allows for efficient indexing
into the h.s.e set which leads to an efficient encoding algorithm for our code). As a further
ingredient, we note that the number of possible subspaces that arise in the decoding is
much smaller than the total number of possibilities. Using this together with an added
trick in the h.s.e set construction, we are able to reduce the list size to a constant.
2.2.2. Subspace designs. The approach based on h.s.e sets leads to excellent list size; however, we only know randomized constructions of h.s.e sets with the required properties.
Our second approach to prune the subspace of possible solutions is based on subspace
designs and leads to deterministic subcode constructions. Recall that the coefficients
f0 , f1 , . . . , fk−1 of the message polynomial (which belong to the extension field Fqm ) are
pinned down by the linear-algebraic list decoder to a periodic subspace with the property that there is an Fq -subspace W ⊂ Fqm such that once f0 , f1 , . . . , fi−1 are fixed, fi
belongs to a coset of W . Our idea then is to restrict fi to belong to a subspace Hi
where H1 , H2 , . . . , Hk are a collection of subspaces in Fm
q such that for any s-dimensional
m
subspace W ⊂ Fq , only a small number of them have non-trivial intersection with W .
P
More precisely, we require that ki=1 dim(W ∩ Hi ) is small. We call such a collection as
a subspace design in Fm
q . We feel that the concept of subspace designs is interesting in its
own right, and view the introduction of this notion in Section 10 as a key contribution in
this work. Indeed, subsequent work by Forbes and Guruswami [3] highlighted the central
role played by subspace designs in “linear-algebraic pseudorandomness” and in particular
how they lead to rank condensers and dimension expanders.
A simple probabilistic argument shows the existence of q Ω(εm) random subspaces of
dimension (1 − ε)m have small total intersection with every s-dimensional W . This construction can also be derandomized, though the construction complexity of the resulting

10

V. GURUSWAMI AND C. XING

codes becomes quasi-polynomial with this approach for the parameter choices needed in
the construction.
Fortunately, in a follow-on to [17], Guruswami and Kopparty gave explicit constructions of subspace designs with parameters nearly matching the random constructions [8].
One can pre-code with this subspace design to get explicit list-decodable sub-codes of
Reed-Solomon codes whose evaluation points are in a subfield (Section 11.1). However,
this construction inherits the large field size of Reed-Solomon codes.
For explicit subcodes of algebraic-geometric codes using subspace designs we need
additional ideas. The dimension k in the case of AG codes is much larger than the
alphabet size q m (in fact that is the whole point of generalizing to AG codes). So we
cannot have a subspace design in Fm
q with k subspaces. We therefore use several “layers”
of subspace designs in a cascaded fashion (Section 10.2) — the first one in Fm
q , the next
√
√
m
m
m
m
2
1
1
and so on. Since the mi ’s
one in Fq for m1 ≫ q , the third one in Fq for m2 ≫ q
increase exponentially, we only need about log∗ k levels of subspace designs. Each level
incurs about a factor 1/ε increase in the dimension of the “periodic subspace” (W when
we begin) at the corresponding scale. With a careful technical argument and choice of
parameters, we are able to obtain the bounds of Theorem 1.1(ii).
3. Periodic subspaces
In this section we formalize a certain “periodic” property of affine subspaces that will
arise in our list decoding application.
We begin with some notation. For a vector y = (y1 , y2 , . . . , ym ) ∈ Fm
q and positive
t
−t
+1
2
1
its projection onto coordinates
integers t1 6 t2 6 m, we denote by proj[t1 ,t2 ] (y) ∈ Fq
t1 through t2 , i.e., proj[t1 ,t2 ] (y) = (yt1 , yt1 +1 , . . . , yt2 ). When t1 = 1, we use projt (y) to
denote proj[1,t] (y). These notions are extended to subsets of strings in the obvious way:
proj[t1 ,t2 ] (S) = {proj[t1 ,t2 ] (x) | x ∈ S}.

Definition 1 (Periodic subspaces). For positive integers r, b, ∆ and κ := b∆, an affine
subspace H ⊂ Fκq is said to be (r, ∆, b)-periodic if there exists a subspace W ⊆ F∆
q of
(j−1)∆

dimension at most r such that for every j = 1, 2, . . . , b, and every “prefix” a ∈ Fq
the projected affine subspace of F∆
q defined as

,

{proj[(j−1)∆+1,j∆] (x) | x ∈ H and proj(j−1)∆ (x) = a}

∆
is contained in an affine subspace of F∆
q given by W + va for some vector va ∈ F
dependent on a.3

The motivation of the above definition will be clear when we present our linearalgebraic list decoders, which will pin down the messages that must be output within an
(where q m will be the alphabet size of the
(s − 1, m, k)-periodic (affine) subspace of Fmk
q
code, k its dimension, and s a parameter of the algorithm that governs how close the
decoding performance approaches the Singleton bound).
The following properties of periodic affine spaces follow from the definition.
Claim 3.1. Let H be an (r, ∆, b)-periodic affine subspace. Then for each j = 1, 2, . . . , b,
(1) the projection of H to the first j blocks of ∆ coordinates, projj∆ (H) = {projj∆ (x) |
x ∈ H}, has dimension at most jr. (In particular H has dimension at most br.)
3In fact, in our applications this affine space will either be empty or equal to a coset of W , but for a
simpler definition we just require that it is always contained in a coset of W .

AG CODES & NEAR-OPTIMAL LIST DECODING
(j−1)∆

(2) for each a ∈ Fq
proj(j−1)∆ (y) = a.

11

, there are at most q r extensions y ∈ projj∆ (H) such that

For an affine space H, its underlying subspace is the subspace S such that H is a
coset of S.
Definition 2 (Representing periodic affine subspaces). The canonical representation of
an (r, ∆, b)-periodic subspace H consists of a matrix B ∈ Fq∆×∆ such that ker(B) has
∆×∆ for 1 6 i 6 b and
dimension at most r, and vectors ai ∈ F∆
q and matrices Ai,j ∈ Fq
1 6 j < i, such that x ∈ H if and only if for every i = 1, 2, . . . , b the following holds:
i−1
X

ai +
Ai,j · proj[(j−1)∆+1,j∆] (x) + B · proj[(i−1)∆+1,i∆] (x) = 0 .
j=1

Ultra-periodic subspaces. For our result on pre-coding algebraic-geometric codes with
subspace designs, we will exploit an even stronger property that holds for the subspaces
output by the linear-algebraic list decoder. We formalize this notion below.
Definition 3. An affine subspace H of Fκq is said to be (r, ∆)-ultra periodic if for every
κ
κ
, setting bℓ = ℓ∆
, we have projbℓ ·ℓ∆ (H) is (ℓr, ℓ∆, bℓ )-periodic.
integer ℓ, 1 6 ℓ 6 ∆

The definition captures the fact that the subspace is periodic not only for blocks of
size ∆, but also for block sizes that are multiples of ∆. Thus the subspace looks periodic
in all “scales” simultaneously.
4. Preliminaries on function fields and algebraic-geometric codes

For convenience of the reader, we start with some background on global function fields
over finite fields. The reader may refer to [25, 20] for detailed background on function
fields and algebraic-geometric codes.
For a prime power q, let Fq be the finite field of q elements. An algebraic function
field over Fq in one variable is a field extension F ⊃ Fq such that F is a finite algebraic
extension of Fq (x) for some x ∈ F that is transcendental over Fq . The field Fq is called the
full constant field of F if the algebraic closure of Fq in F is Fq itself. Such a function field
is also called a global function field. From now on, we always denote by F/Fq a function
field F with the full constant field Fq .
Let PF denote the set of places of F . The divisor group, denoted
P by Div(F ), is the
free abelian group generated by all places in PF . An element G = P ∈PF nP P of Div(F )
is called a divisor of F , where nP = 0 for almost all P ∈ PF . We denote np by νP (G).
The support, denoted by Supp(G), of G is the set {P ∈ PF : nPP6= 0}. For a nonzero
function z ∈ F , the principal divisor of z is defined to be div(z) = P ∈PF νP (z)P , where
νP denotes the normalized
P and pole divisors of z are
P discrete valuation at P . The zero
defined to be div(z)0 = νP (z)>0 νP (z)P and div(z)∞ = − νP (z)<0 νP (z)P , respectively.

Riemann-Roch space. For a divisor G of F , we define the Riemann-Roch space associated with G by
L(G) := {f ∈ F ∗ : div(f ) + G > 0} ∪ {0},
where F ∗ denotes the set of nonzero elements of F . Then L(G) is a finite dimensional
space over Fq and its dimension ℓ(G) is determined by the Riemann-Roch theorem which
gives
ℓ(G) = deg(G) + 1 − g + ℓ(W − G),

12

V. GURUSWAMI AND C. XING

where g is the genus of F and W is a canonical divisor of degree 2g − 2. Therefore, we
always have that ℓ(G) > deg(G) + 1 − g and the equality holds if deg(G) > 2g − 1.

Consider finite extension Fqm over Fq and the constant extension Fm := Fqm · F
over F . A divisor G of F can be viewed as a divisor of Fm . Thus, we can consider the
Riemann-Roch space in Fm given by
∗
Lm (G) := {f ∈ Fm
: div(f ) + G > 0} ∪ {0}.

Then it is clear that Lm (G) contains L(G) and Lm (G) is a finite dimensional vector
space over Fqm . Furthermore, Lm (G) is the tensor product of L(G) with Fqm (see [24,
Proposition 5.8 of Chapter II]). This implies that
dimFqm (Lm (G)) = dimFq (L(G))
and an Fq -basis of L(G) is also an Fqm -basis of Lm (G).
Automorphism. For a function f and a place P ∈ PF with νP (f ) > 0, we denote
by f (P ) the residue class of f in the residue class field FP at P . For an automorphism
φ ∈ Aut(F/Fq ) and a place P , we denote by P φ the place {φ(x) : x ∈ P }. For a function
f ∈ F , we denote by f φ the action of φ on f . If νP (f ) > 0 and νP φ (f ) > 0, then one has
P
−1
−1
that νP (f φ ) > 0 and f (P φ ) = f φ (P ). Furthermore, for a divisor G = P ∈PF mP P
P
we denote by Gφ the divisor P ∈PF mP P φ . Therefore, we have
φ(L(G)) := {f φ : f ∈ L(G)} = L(Gφ ).

Assume that E/Fq is a subfield of F and φ is an automorphism of Aut(F/E). Then
for a divisor G of F that is invariant under φ, then we have φ(L(G)) = L(G). Next we
consider the constant extension Fm = Fqm · F . Let σ be the Frobenius automorphism
Fqm , i.e., σ(α) = αq for any α ∈ Fqm . Then σ can be extended to an automorphism of
Aut(Fm /F ).
Local expansion (or power series). Let F/Fq be a function field and let P be a
rational place. An element t of F is called a local parameter at P if νp (t) = 1 (such a
local
alwaysexists).
For a nonzero function f ∈ F with νP (f ) > v, we have


 parameter
f
f
νP tv > 0. Put av = tv (P ), i.e., av is the value of the function f /tv at P . Note that




v
vt
the function f /tv − av satisfies νP tfv − av > 1, hence we know that νP f −a
> 0.
v+1
t


v
vt
(P ). Then νP (f − av tv − av+1 tv+1 ) > v + 2.
Put av+1 = f −a
tv+1

Assume that we have obtained a sequence {ar }m
r=v (m > v)
 of Pelements
 of Fq such
r
Pk
f− m
r
r=v ar t
that νP (f − r=v ar t ) > k + 1 for all v 6 k 6 m. Put am+1 =
(P ). Then
tm+1
Pm+1
νP (f − r=v ar tr ) > m + 2. In this way we continue our construction
Pmof ar .r Then we
obtain an infinite sequence {ar }∞
of
elements
of
F
such
that
ν
(f
−
q
P
r=v
r=v ar t ) > m + 1
for all m > v. We summarize the above construction in the formal expansion
∞
X
ar t r ,
(1)
f=
r=v

which is called the local expansion of f at P .

It is clear that the local expansions P
of a function depends on P
the choice of the local
m
i satisfies ν (f −
i
parameters t. Note that if a power series ∞
a
t
i
P
i=v
i=v ai t ) > m + 1 for
all m > v, then it is a local expansion of f . The above procedure shows that finding a local
expansion at a rational place is very efficient as long as the computation of evaluations of
functions at this place is easy.

AG CODES & NEAR-OPTIMAL LIST DECODING

13

If f belongs to a Riemann-Roch space L(G) with deg(G) = d. Denote νP (G) by v,
then the first d + 1 coefficients av , av+1 , . . . , av+d in (1) determines the function f . To see
this, assume that g is a function of L(G) with the same first d + 1 coefficients in its local
expansion. Then we have f − g ∈ L(G − (d + 1)P ) which is the zero vector space. This
implies that f = g.
Algebraic-geometric codes. Let P + {P1 , P2 , . . . , PN } be a set of N distinct rational
places of a function field F/Fq of genus g. Let G be a divisor of F with Supp(G) ∩ P = ∅.
Then the algebraic-geometric codes defined by
C(P, G) := {(f (P1 ), f (P2 ), . . . , f (PN )) : f ∈ L(G)}
is an Fq -linear code of length N . Furthermore, the dimensions of C(P, G) is equal to ℓ(G)
if N > deg(G).
The codes considered in this paper are variations of the above algebraic-geometric
codes, namely, folded algebraic-geometric codes and algebraic-geometric codes with evaluation points in a subfield.
5. Folded codes from the Hermitian tower
In this section, we will describe a family of folded codes based on the Hermitian
function field (or rather a tower of such fields).
5.1. Background on Hermitian tower. In what follows, let r be a prime power and
let q = r 2 . We denote by Fq the finite field with q elements. The Hermitian function
tower that we are going to use for our code construction was discussed in [22]. The
reader may refer to [22] for the detailed background on the Hermitian function tower, and
Stichtenoth’s book [25] for general background on algebraic function fields and their use in
constructing algebraic-geometric codes. The Hermitian tower is defined by the following
recursive equations
xri+1 + xi+1 = xr+1
,
i

i = 1, 2, . . . , e − 1.

Put Fe = Fq (x1 , x2 , . . . , xe ) for e > 2. We will assume that r > 2e.
Rational places. The function field Fe has r e+1 + 1 rational places. One of these is the
“point at infinity” which is the unique pole P∞ of x1 (and is fully ramified). The other r e+1
come from the rational places lying over the unique zero Pα of x1 −α for each α ∈ Fq . Note
that for every α ∈ Fq , Pα splits completely in Fe , i.e., there are r e−1 rational places lying
over Pα . Intuitively, one can think of the rational places of Fe (besides P∞ ) as being given
for i = 1, 2, . . . , e − 1. For
by e-tuples (α1 , α2 , . . . , αe ) ∈ Feq that satisfy αri+1 + αi+1 = αr+1
i
each value of α ∈ Fq , there are precisely r solutions to β ∈ Fq satisfying β r + β = αr+1 ,
so the number of such e-tuples is r e+1 (q = r 2 choices for α1 , and then r choices for each
successive αi , 2 6 i 6 e).
Riemann-Roch spaces. For a place P of Fe , we denote by νP the discrete valuation of
P : for a function h ∈ Fe , if h has a zero at P , then νP (h) gives the number (multiplicity)
of zeroes, if h has a pole at P , then −νP (h) gives the pole order of h at P , and νP (h) = 0
if h has neither a zero or a pole at P .
For an integer l, we consider the Riemann-Roch space defined by
L(lP∞ ) := {h ∈ Fe \ {0} : νP∞ (h) > −l} ∪ {0}.

14

V. GURUSWAMI AND C. XING

Then the dimension ℓ(lP∞ ) is at least l − ge + 1 and furthermore, ℓ(lP∞ ) = l − ge + 1 if
l > 2ge − 1. A basis over Fq of L(lP∞ ) can be explicitly constructed as follows
)
(
e
X
j1
e−i
i−1
e
je
ji r (r + 1)
6l .
(2)
x1 · · · xe : (j1 , . . . , je ) ∈ Z>0 ,
i=1

We stress that evaluating elements of L(lP∞ ) at the rational places of Fe (other than
P∞ ) is easy: we simply have to evaluate a linear combination of the monomials allowed
in (2) at the tuples (α1 , α2 , . . . , αe ) ∈ Feq mentioned above. In other words, it is just
evaluating an e-variate polynomial at a specific subset of r e+1 points of Feq , and can be
accomplished in polynomial time.
Genus. The genus ge of the function field Fe is given by
(3)
!


e−1
e  
e
1 i−1
er e X  e i−1
re X e 1
1 X e
e−1
r 1+
6 er e
6
− (r + 1)
+1 6
ge =
2
r
2
2
r
i r i−1
i=1

i=1

i=1

where the last step used r > 2e.

A useful automorphism. Let γ be a primitive element of Fq and consider the automorphism σ ∈ Aut(Fe /Fq ) defined by
i−1

σ : xi 7→ γ (r+1)

xi

for i = 1, 2, . . . , e.

The order of σ is q − 1 and furthermore, we have the following facts:
(i) Let P0 be the unique common zero of x1 , x2 , . . . , xe (this corresponds to the e-tuple
(0, 0, . . . , 0)), and P∞ the unique pole of x1 . The automorphism σ keeps P0 and
P∞ unchanged, i.e., P0σ = P0 and P∞ σ = P∞ ,
(ii) Let P be the set of all the rational places which are neither P∞ nor zeros of x1 . Then
|P| = (q − 1)r e−1 . Moreover, σ divides P into r e−1 orbits and each orbit has q − 1
places. For an integer m with 1 6 m 6 q − 1, we can label N m distinct
k
j elements
m−1
m−1
q−1
σ
σ
σ
e−1
σ
, . . . , PN , PN , . . . , PN
in P, as long as N 6 r
P1 , P1 , . . . , P1
m .

Definition 4 (Folded codes from the Hermitian tower). Assume
j
k that m, l, N are positive
q−1
e−1
integers satisfying 1 6 m 6 q − 1 and l/m 6 N 6 r
m . The folded code from
f
Fe with parameters N, l, q, e, m, denoted by FH(N,
l, q, e, m), encodes a message function
f ∈ L(lP∞ ) as




 
f (PN )
f (P2 )
f (P1 )
 f (PNσ ) 
 f (P1σ )   f (P2σ ) 
N




 
(4)
f 7→ 
.
..
..
,...,
 ∈ Fm
..
,
q




 
.
.
.
m−1
m−1
m−1
f (PNσ
)
)
f (P2σ
)
f (P1σ

f
Lemma 5.1. The above code FH(N,
l, q, e, m) is an Fq -linear code over alphabet size q m ,
l−ge +1
rate at least N m , and minimum distance at least N − ml .

Proof. It is clear that the map (4) is an Fq -linear map. The dimension over Fq of the
message space L(lP∞ ) is at least l − ge + 1 by the Riemann-Roch theorem, which gives the
claimed lower bound on rate. For the distance property, observe that if the i-th column
is zero, then f has m zeros. This implies that the encoding of a nonzero function f can
have at most l/m zero columns since f ∈ L(lP∞ ).


AG CODES & NEAR-OPTIMAL LIST DECODING

15

5.2. Redefining the code in terms of local expansion at P0 . For our decoding, we
will actually recover the message f ∈ L(lP∞ ) in terms of the coefficients of its power series
expansion around P0
f = f 0 + f 1 x + f 2 x2 + · · ·
where x := x1 is the local parameter at P0 (which means that x1 has exactly one zero at P0 ,
i.e., νP0 (x1 ) = 1). In fact, realizing that one must work in this power series representation
is one of the key insights in this work.
Let us first show that one can efficiently move back-and-forth between the representation of f ∈ L(lP∞ ) in terms of a basis for L(lP∞ ) and its power series representation
(f0 , f1 , . . . ) around P0 . Since the mapping f 7→ (f0 , f1 , . . . ) is Fq -linear, it suffices to
compute the local expansion at P0 of a basis for L(lP∞ ).
Lemma 5.2. For any n, one can compute the first n terms of the local expansion of the
basis elements (2) at P0 using poly(n) operations over Fq .
Proof. By the structure of the basis functions in (2), it is sufficient to find an algorithm of
efficiently finding local expansions of xi at P0 for every i = 1, 2, . . . , e. We can inductively
find the local expansions of xi at P0 as follows.

ci,j

For i = 1, x1 is the local parameter x of P0 , so x is the local expansion of x1 at P0 .
P
j
Now assume that we know the local expansion of xi = ∞
j=1 ci,j x at P0 for some
∈ Fq . Then we have



∞
∞
∞
∞
X
X
X
X
ci+1,j xj = xri+1 + xi+1 = xr+1
=
cri,j xjr  
ci,j xj  .
cri+1,j xjr +
i
j=1

j=1

j=1

j=1

By comparing the coefficients of xj in the above identity, we can easily solve ci+1,j ’s from
ci,j ’s. More specifically, the coefficient of xj at the left of the identity is

ci+1,j
if r 6 |j
ci+1,j + cri+1,j/r if r|j.
Thus, all ci+1,j ’s can be easily solved recursively.



To keep the list output by the algorithm at a controllable size, we will combine the
code with certain special subspace evasive sets. For this purpose, we will actually need
to index the messages of the code by the first k coefficients (f0 , f1 , . . . , fk−1 ) of the local
expansion of the function f at P0 . This requires that for every (f0 , f1 , . . . , fk−1 ) there is
a f ∈ L(lP∞ ) whose power series expansion has the fi as the first k coefficients. This is
easy to ensure by taking l = k + 2ge − 1 as we argue below. Note that to ensure that
L(lP∞ ) has dimension k, it suffices to pick l = k + ge − 1 by the Riemann-Roch theorem.
We pick l to be ge more than this bound. Since the genus will be much smaller than the
code length, we can afford this small loss in parameters.
Let us define the local expansion map evP0 : L((k + 2ge − 1)P∞ ) → Fkq that maps f
to (f0 , f1 , . . . , fk−1 ) where f = f0 + f1 x + f2 x2 + · · · is the local expansion of f at P0 .
Claim 5.3. evP0 is an Fq -linear surjective map. Further, we can compute evP0 using
poly(k, ge ) operations over Fq given a representation of the input f ∈ L((k + 2ge − 1)P∞ )
in terms of the basis (2).
Proof. The Fq -linearity of evP0 is clear. The kernel of evP0 is L((k+2ge −1)P∞ −kP0 ) which
has dimension exactly ge by the Riemann-Roch theorem. By the rank-nullity theorem,

16

V. GURUSWAMI AND C. XING

the image must have dimension k, and so the map is surjective. The claimed complexity
of computation follows immediately from Lemma 5.2.

For each (f0 , f1 , . . . , fk−1 ) ∈ Fkq , we can therefore pick a pre-image in L((k + 2ge −
1)P∞ ). For convenience, we will denote an injective map making such a unique choice by
κP0 : Fkq → L((k + 2ge − 1)P∞ ). By picking the pre-images of a basis of Fkq and extending
it by linearity, we can assume κP0 to be Fq -linear, and thus specify it by a (k + ge ) × k
matrix. We record this fact for easy reference below.
Claim 5.4. The map κP0 : Fkq → L((k + 2ge − 1)P∞ ) is Fq -linear and injective. We can
compute a representation of this linear transformation using poly(k, ge ) operations over
Fq , and the map itself can be evaluated using poly(k, ge ) operations over Fq .
N by
We will now redefine a version of the folded Hermitian code that maps Fkq to (Fm
q )
composing the folded encoding (4) from the original Definition 4 with κP0 .

Definition 5 (Folded Hermitian code using local expansion). The folded Hermitian code
f
k + 2ge − 1, q, e, m)(κP0 (f ))
FH(N, k, q, e, m) maps f = (f0 , f1 , . . . , fk−1 ) ∈ Fkq to FH(N,
N
m
∈ (Fq ) .

The rate of the above code equals k/(N m) and its distance is at least N − (k + 2ge −
1)/m.

5.3. List decoding folded codes from the Hermitian tower. We now present a list
decoding algorithm for the above codes. The algorithm follows the linear-algebraic list
decoding algorithm for folded Reed-Solomon codes. Suppose a codeword (4) encoding
f ∈ Im(κP0 ) ⊆ L((k + 2ge − 1)P∞ ) is transmitted and received as


y1,1 y2,1
yN,1
.. 

y2,2
. 
 y
(5)
y =  1,2

..


.
y1,m · · ·
yN,m
where some columns are erroneous. Let s > 1 be an integer parameter associated with
the decoder.
Lemma 5.5. Given a received word as in (5), using poly(N ) operations over Fq , we can
find a nonzero linear polynomial in Fe [Y1 , Y2 , . . . , Ys ] of the form
(6)
satisfying
(7)

Q(Y1 , Y2 , . . . , Ys ) = A0 + A1 Y1 + A2 Y2 + · · · + As Ys
j

j

j

Q(yi,j , yi,j+1 , · · · , yi,j+s−1 ) = A0 (Piσ ) + As (Piσ )yi,j+1 + · · · + As (Piσ )yi,j+s = 0

for i = 1, 2, . . . , N and j = 0, 1, . . . , m−s. The coefficients Ai of Q satisfy Ai ∈ L(DP∞ )
for i = 1, 2, . . . , s and A0 ∈ L((D + k + 2ge − 1)P∞ ) for a “degree” parameter D chosen as


N (m − s + 1) − k + (s − 1)ge + 1
(8)
D=
.
s+1
Proof. If we fix a basis of L(DP∞ ) (of the form (2)) and extend it to a basis of L((D +
k + 2ge − 1)P∞ ), then the number of freedoms of A0 is at least D + k + ge and the number
of freedoms of Ai is at least D − ge + 1 for i > 1. Thus, the total number of freedoms in
the polynomial Q equals
(9)

s(D − ge + 1) + D + k + ge = (s + 1)(D + 1) − (s − 1)ge − 1 + k > N (m − s + 1)

AG CODES & NEAR-OPTIMAL LIST DECODING

17

for the above choice (8) of D. The interpolation requirements on Q ∈ Fe [Y1 , . . . , Ys ] are
the following:
(10)

j

j

j

Q(yi,j , yi,j+1 , · · · , yi,j+s−1 ) = A0 (Piσ ) + As (Piσ )yi,j+1 + · · · + As (Piσ )yi,j+s = 0

for i = 1, 2, . . . , N and j = 0, 1, . . . , m − s. The interpolation requirements on Q give
a total of N (m − s + 1) homogeneous linear equations that the coefficients of the Ai ’s
w.r.t the chosen basis of L((D + k + 2ge − 1)P∞ ) must satisfy. Since the number of such
coefficients (degrees of freedom in Q) exceeds N (m − s + 1), we can conclude that such a
linear polynomial Q as required by the lemma must exist, and can be found by solving a
homogeneous linear system over Fq with about N (m − s + 1) variables and constraints. 
Similar to earlier interpolation based list decoding algorithms, the following lemma gives
an algebraic condition that the message functions f ∈ L((k +2ge −1)P∞ ) we are interested
in list decoding must satisfy. The proof is a standard argument comparing the pole order
to the number of zeroes.
Lemma 5.6. If f is a function in L((k + 2ge − 1)P∞ ) whose encoding (4) agrees with the
e −1
received word y in at least t columns with t > D+k+2g
m−s+1 , then
−1

Q(f, f σ , . . . , f σ

(11)

−(s−1)

) = A0 + A1 f + A2 f σ

−1

+ · · · + As f σ

−(s−1)

= 0.
−1

Proof. The proof proceeds by comparing the number of zeros of the function Q(f, f σ ,
−(s−1)
−1
−(s−1)
with D + k + 2ge − 1. Note that
) = A0 + A1 f + A2 f σ + · · · + As f σ
. . . , fσ
−(s−1)
−1
σ
σ
) is a function in L((D+k+2ge −1)P∞ ). If column i of the encoding
,...,f
Q(f, f
(4) of f agrees with y, then for all j = 0, 1, . . . , m − s, we have
j

j

j

j

j

j

0 = A0 (Piσ ) + A1 (Piσ )yi,j+1 + A2 (Piσ )yi,j+2 + · · · + As (Piσ )yi,j+s
j

j

= A0 (Piσ ) + A1 (Piσ )f (Piσ ) + A2 (Piσ )f (Piσ
=

j

) + · · · + As (Piσ )f (Piσ

j+s−1

)

j
j
j
−(s−1)
j
j
j
−1
(Piσ )
+ A1 (Piσ )f (Piσ ) + A2 (Piσ )f σ (Piσ ) + · · · + As (Piσ )f σ
j
−(s−1)
−1
)(Piσ ) .
A1 f + A2 f σ + · · · + As f σ
we use the fact that f σ (P σ ) = f (P )σ = f (P ), or equivalently f (P σ )

j
A0 (Piσ )

= (A0 +

j+1

Note that here
=
−(s−1)
−1
−1
) has (m − s + 1) distinct zeros from this
f σ (P ). In other words, Q(f, f σ , . . . , f σ
agreeing column. Thus, there are a total of at least t(m − s + 1) zeros for all the agreeing
−(s−1)
−1
) must be the zero function when t(m − s − 1) >
columns. Hence, Q(f, f σ , . . . , f σ
D + k + 2ge − 1.

Solving the functional equation for f . Our goal next is to recover the list of solutions
f to the functional equation (11). Recall that our message functions lie in Im(κP0 ), so we
can recover
f by recovering the top k coefficients (f0 , f1 , . . . , fk−1 ) of its local expansion
P
j
f= ∞
f
j=0 j x at P0 . We now prove that (f0 , f1 , . . . , fk−1 ) for f satisfying Equation (11)
belong to a “periodic” subspace (in the sense of Definition 1) of not too large dimension.
Lemma 5.7. The set of solutions (f0 , f1 , . . . , fk−1 ) ∈ Fkq such that f = f0 + f1 x + f2 x2 +
· · · ∈ L((k + 2ge − 1)P∞ ) obeys equation
(12)

A0 + A1 f + A2 f σ

−1

+ · · · + As f σ

−(s−1)

=0,

when the Ai ’s obey the pole order restrictions of Lemma 5.5 and at least one Ai is nonzero,
k
⌉)-periodic subspace (note that we do not require (q − 1)|k here and
is an (s − 1, q − 1, ⌈ q−1
k
⌉ by padding with 0’s). Further, there
one could extend the subspace to length (q − 1)⌈ q−1
are at most q N m+s+1 possible choices of this subspace over varying choices of the Ai ’s.

18

V. GURUSWAMI AND C. XING

Proof. Let u = min{νP0 (Ai ) : i = 1, 2, . . . , s}. Then it is clear that u > 0 and νP0 (A0 ) > u.
Each Ai has a local expansion at P0 :
Ai = xu

∞
X

ai,j xj

j=0

for i = 0, 1, . . . , s − 1, which can be efficiently computed from the basis representation of
the Ai ’s. From the definition of u, one knows that the polynomial
B0 (X) := a1,0 + a2,0 X + · · · + as,0 X s−1
is nonzero. Assume that at P0 , the function f has a local expansion
f

σ−i

has a local expansion at P0 as follows
f

σ−i

=

∞
X

P∞

j=0 fj x

j.

Then

ξ ij fj xj ,

j=0

−1

where ξ = 1/γ. The coefficient of xd+u in the local expansion of Q(f, f σ , . . . , f σ
is
(13)

0 = B0 (ξ d )fd +

d−1
X

−(s−1)

)

bi fi + a0,d ,

i=0

where bi ∈ Fq is a linear combination of ai,j which does not involve fj . Hence, fd is uniquely
determined by f0 , . . . , fd−1 as long as B0 (ξ d ) 6= 0. Let S := {0 6 d 6 q − 2 : B0 (ξ d ) = 0}.
Then it is clear that |S| 6 s − 1 since the order of ξ is q − 1 and B0 (X) has degree at most
s − 1. Thus, B0 (ξ j ) 6= 0 if and only if j mod (q − 1) ∈
/ S; and in this case fj is a fixed
affine linear combination of fi for 0 6 i < j.
k
)Let W be the set of solutions (f0 , f1 , . . . , fk−1 ). The fact that W is (s, q − 1, q−1
periodic follows from (13). Note that the coefficients bd−j for j > 1 in that equation are
given by Bj (ξ d−j ) where Bj (X) := a1,j + a2,j X + · · · + as,j X s−1 . Therefore, once the
values of fi , 0 6 i < (j − 1)(q − 1) are fixed, the possible choices for the next block
of (q − 1) coordinates, f(j−1)(q−1) , · · · , fj(q−1)−1 , lie in an affine shift of a fixed subspace
of dimension at most (s − 1). Further, this shift is an easily computed affine linear
combination of the fi ’s in the previous blocks. This implies the efficient computability of
the claimed representation of W .

Finally, by the choice of D in (8), the total number of possible (A0 , A1 , . . . , As )
and hence the number of possible functional equations (12), is at most q N (m−s+1)+s+1 6
q N m+s+1 . Therefore, the number of possible candidate subspaces W is also at most
q N m+s+1 .

Combining Lemmas 5.6 and 5.7, we conclude, after some simple calculations, that
one can find a representation of the (s, q − 1)-periodic subspace containing all candidate
messages (f0 , f1 , . . . , fk−1 ) in polynomial time, when the fraction of errors τ = 1 − t/N
satisfies
k
ge
s
3m
s
−
−
.
(14)
τ6
s + 1 s + 1 N (m − s + 1) m − s + 1 mN
Pruning the subspace. Applying Lemma 9.8 directly we would get a list size bound of
≈ q sk/q which would be super-polynomial in the code length unless k = O(q). Thus this
idea does not directly allow us to get good list decodable codes while keeping the base
field size small or achieve a list size that grows polynomially in s. Instead what we show

AG CODES & NEAR-OPTIMAL LIST DECODING

19

is that by only encoding (f0 , f1 , . . . , fk−1 ) ∈ Fkq that are restricted to belong to a special
subspace-evasive set, we can (i) bring down the list size, and (ii) find this list efficiently
in polynomial time (and further the exponent of the polynomial is independent of ε, the
gap to capacity). To this end, we develop the necessary machinery concerning subspace
evasive sets next. Later, in Section 8.1, we combine these subspace evasive sets with our
folded Hermitian codes to get good list-decodable codes.
6. Subspace evasive sets with additional structure
Let us first recall the notion of “ordinary” subspace-evasive sets from [7].
Definition 6. A subset S ⊂ Fkq is said to be (d, ℓ)-subspace-evasive if for all d-dimensional
affine subspaces W of Fkq , we have |S ∩ W | 6 ℓ.
We next define the notion of evasiveness w.r.t a collection of subspaces instead of all
subspaces of a particular dimension.
Definition 7. Let F be a family of (affine) subspaces of Fkq , each of dimension at most
d. A subset S ⊂ Fkq is said to be (F, d, ℓ)-evasive if for all W ∈ F, we have |S ∩ W | 6 ℓ.
6.1. Hierarchical subspace-evasive sets. The key to pruning the list to a small size is
the notion of a hierarchical subspace-evasive set, which is defined as a subset of Fkq with the
property that some of its prefixes are subspace-evasive with respect to (s, ∆, b)-periodic
subspaces. We will show how the special subspace-evasive sets help towards pruning the
list in our list decoding context in Section 6.4.
Definition 8. Let F be a family of (s, ∆, b)-periodic subspaces of Fkq with k = b∆. A subset
S ⊂ Fkq is said to be (F, s, ∆, b, L)-h.s.e (for hierarchically subspace evasive for block size
∆) if for every affine subspace W ∈ F, the following bound holds for j = 1, 2, . . . , b:
|projj∆ (S) ∩ projj∆ (W )| 6 L .
6.2. Random sets are hierarchically subspace evasive. Our goal is to give a randomized construction of large h.s.e sets that works with high probability, with the further
properties that one can index into elements of this set efficiently (necessary for efficient
encoding), and one can check membership in the set efficiently (which is important for
efficient decoding).
An easy probabilistic argument, see [7], shows that a random subset of Fkq of size
about q (1−ζ)k is (d, O(d/ζ))-subspace evasive with high probability. As a warmup, let us
work out the similar proof for the case when we have only to avoid a not too large family
F of all possible d-dimensional affine subspaces. The advantage is that the guarantee on
the intersection size is now O(1/ζ) and independent of the dimension d of the subspaces
one is trying to evade.
Lemma 6.1. Let ζ ∈ (0, 1) and k be a large enough positive integer. Let F be a family
of affine subspaces of Fkq , each of dimension at most d 6 ζk/2, with |F| 6 q ck for some
positive constant c.
Let W be a random subset of Fkq chosen by including each x ∈ Fkq in W with probability
q −ζk . Then with probability at least 1 − q −ck , W satisfies both the following conditions: (i)
|W| > q (1−2ζ)k , and (ii) W is (F, d, 4c/ζ)-evasive.

20

V. GURUSWAMI AND C. XING

Proof. The first part follows by noting that the expected size of W equals q (1−ζ)k and a
standard Chernoff bound calculation. For the second part, fix an affine subspace S ⊆ F
of dimension at most d, and a subset T ⊆ S of size t, for some parameter t to be specified
shortly. The probability that W ⊇ T equals q −ζkt. By a union bound over the at most q ck
choices for the affine subspace S ∈ F, and the at most q dt choices of t-element subsets T
of S, we get that the probability that W is not (F, d, t)-evasive is at most q ck+dt · q −ζkt 6
q ck q −ζkt/2 since d 6 ζk/2. Choosing t = ⌈4c/ζ⌉, this quantity is bounded from above by
q −ck .

6.3. Pseudorandom construction of large h.s.e subsets. We next turn to the pseudorandom construction of large h.s.e subsets. Suppose, for some fixed subset F of (s, ∆, b)periodic subspaces of Fkq with k = b∆, we are interested in an (F, s, ∆, b, L)-h.s.e subset
of Fkq of size ≈ q (1−ζ)k for a constant ζ, 1/∆ < ζ < 1/3. For simplicity, let us assume
that the block size ∆ divides k, though arbitrary k can be easily handled. (We will also
ignore floors and ceilings in the description to avoid notational clutter; those are easy to
accommodate and do not affect any of the claims.) The parameters b, ∆, k and field size
q will be considered fixed for the rest of the discussion in this section.
Denote ∆′ = (1 − ζ)∆, b′ = (1 − ζ)b, and k′ = b′ ∆ = (1 − ζ)k.

The random part of the construction will consist of mutually independent, random
univariate polynomials P1 , P2 , . . . , Pb′ and Q, where Pj ∈ Fqj∆′ [T ] for 1 6 j 6 b′ and
Q ∈ Fqk′ [T ] are random polynomials of degree λ.4 The degree parameter will be chosen
to be λ = Θ(k).5
The key fact we will use about random polynomials is the following, which follows
by virtue of the λ-wise independence of the values of a random degree λ polynomial.
Fact 6.2. Let P ∈ K[T ] be a polynomial of degree λ whose coefficients are picked uniformly
and independently at random from the field K. For a fixed subset T ⊆ K with |T | 6 λ, the
values {P (α)}α∈T are independent random values in K.
We remark that this property of low-degree polynomials was also the basis of the
pseudorandom construction of subspace evasive sets in [14]. However, since we require the
h.s.e property, and need to exploit the periodicity of the subspaces we are trying to evade
(which can have large dimension), the construction here is more complicated, and needs
to use several polynomials Pj ’s evaluated in a nested fashion, and one further polynomial
Q to further bring down the list size to a constant (this final use of Q is similar in spirit
to the construction in [14]). We remark that the construction presented here is a bit
simpler and cleaner than the one in the conference version [16], and comes with efficient
encoding automatically by construction. In contrast, the construction in [16] required
some additional work in order to allow for efficient encoding.
In what follows we assume that, for j = 1, 2, . . . , b′ , some fixed bases of the fields
Fqj∆′ have been chosen, giving us some canonical Fq -linear injective maps
′

ρj : Fj∆
→ Fqj∆′ .
q
4We will assume that representations of the necessary extension fields Fi∆′ are all available. For this
q

purpose, we only need irreducible polynomials over Fq of appropriate degrees, which can be constructed
by picking random polynomials and checking them for irreducibility. Our final construction is anyway
randomized, so the randomized nature of this step does not affect the results.
5The degree of Q can in fact be just O(1/ζ), but for uniformity we fix the degree of all polynomials to
be the same.

AG CODES & NEAR-OPTIMAL LIST DECODING

Also, for j = 1, 2, . . . , b′ , let

21

ξj : Fqj∆′ → Fζ∆
q

be some arbitrary Fq -linear surjective map (thus ξj just outputs the first ζ∆ coordinates of
′
w.r.t some fixed basis). Finally,
the representation of elements of Fqj∆′ as vectors in Fj∆
q
let ρ : Fkq → Fqk′ be some fixed Fq -linear injective map, and ξ : Fqk′ → Fζk
q be an arbitrary
Fq -linear surjective map.
′

We are now ready to describe our construction of h.s.e set based on the random
polynomials P1 , P2 , . . . , Pb′ , Q.
Definition 9 (h.s.e set construction). Given the polynomials Pj ∈ Fqj∆′ [T ] for i =
1, 2, . . . , b′ and Q ∈ Fqk′ [T ], define the subset Γ(P1 , P2 , . . . , Pb ; Q) by
n
′
(y1 , z1 , y2 , z2 , . . . , yb′ , zb′ ; w) ∈ Fkq for j = 1, 2, . . . , b′ : yj ∈ F∆
q ,
zj = ξj (Pj (ρj (y1 ◦ y2 ◦ · · · ◦ yj ))) ∈ Fζ∆
q ; and
o
.
w = ξ(Q(ρ(y1 , z1 , . . . , yb′ , zb′ ))) ∈ Fζk
q

By construction, once suitable representations of the extension fields are available
by pre-processing and the choice of P1 , . . . , Pb′ , Q is made, we can efficiently compute
(1−ζ)2 k
a bijective encoding map HSE : Fq
→ Γ(P1 , P2 , . . . , Pb ; Q). Indeed, we can view
′
′ ∆′
b
as (y1 , y2 , . . . , yb′ ) with yj ∈ F∆
the input y ∈ Fq
q and then compute the zj ’s and w
efficiently using poly(k) operations over Fq (recall that the degree of the polynomials is
λ = Θ(k)).
We now move on to the main claim about the h.s.e property of our construction.
Theorem 6.3. Let ζ ∈ (0, 1/3) and s be a positive integer satisfying s < ζ∆/10. Let F
be a subset of at most q ck (s, ∆, b)-periodic subspaces of Fkq for k = b∆ and some positive
constant c. Suppose that the parameters satisfy the condition q ζ∆ > (2q 2 ck)10/9 . Then
with probability 1 − q(−Ω(k)) over the choice of random polynomials {Pi }16i6b and Q each
of degree λ = ⌈ck⌉, the set Γ(P1 , P2 , . . . , Pb ; Q) from Definition 9 is
(F, s, ∆, b, L)-h.s.e and (F, sb, ℓ)-evasive

for L = ⌈ck⌉ and ℓ = ⌈4c/ζ⌉.
Proof. Note that the first k′ = (1− ζ)k symbols of vectors in Γ(P1 , . . . , Pb′ ; Q) only depend
on the Pj ’s. We will first prove that with high probability over the choice of the Pj ’s the
following holds (call such a choice of Pj ’s as good):
For every W ∈ F, |projk′ (W ) ∩ projk′ (Γ)| < L, where we denote Γ as
shorthand for Γ(P1 , . . . , Pb′ ; Q).
Then, conditioned on a good choice of Pj ’s, we will prove that with high probability over
the choice of the random polynomial Q, |W ∩ Γ| < ℓ. Together, these steps will imply
that the set Γ(P1 , P2 , . . . , Pb′ ; Q) is (F, sb, ℓ)-evasive. (Note that every subspace in F has
dimension at most sb by Claim 3.1.) We will return to the (F, s, ∆, b, L)-h.s.e property at
the end of the proof.
Let us first establish the second step. Fix a good choice of P1 , . . . , Pb′ , and suppose
we pick Q randomly. Fix a subspace W ∈ F. Since |projk′ (W )∩projk′ (Γ)| < L (recall that
projk′ (Γ) only depends on the Pj ’s and thus is already determined), the number of elements
′
of W that could possibly belong to Γ (after the choice of Q) is at most L · q s(b−b ) = Lq ζsb ;

22

V. GURUSWAMI AND C. XING
′

indeed for each prefix belonging to projk′ (Γ)∩projk′ (W ), there are most q s(b−b ) extensions
that can fall in W since W is (s, ∆, b)-periodic. Further, the probability over the choice
of Q that any such fixed extension belongs to Γ is at most q −ζk , and any ℓ of these events
are independent. (Note that for a fixed prefix, there can be at most extension that falls in
Γ, so for ℓ different strings to fall in Γ, their prefixes must be distinct and are mapped to
independent locations by the random polynomial Γ.) Therefore, the probability over the
choice of Q that |W ∩ Γ| > ℓ is at most (Lq ζsb )ℓ q −ζkℓ . By a union bound over all W ∈ F,
we conclude that |W ∩ Γ| < ℓ for every W ∈ F simultaneously, except with probability at
most
q ck Lℓ q ζ(s−∆)bℓ 6 q ck (ck)ℓ q −ζ∆bℓ/2 = q ck q −ζkℓ/2
where in the first inequality we used s 6 ∆/2 and in the next one ck 6 q ζk both of which
hold comfortably. For ℓ > 4c/ζ, the above probability upper bound is at most q −ck .
We now turn to the first step, on the Pj ’s being good with high probability. Fix some
W ∈ F; we will prove by induction on j that
(15)

|projj∆ (W ) ∩ projj∆ (Γ)| < L

w.h.p over the choice of P1 , P2 , . . . , Pj , for 1 6 j 6 b′ (note that projj∆ (Γ) only depends
on P1 , . . . , Pj , so this event is well defined). For the base case j = 1, |proj∆ (W )| 6 q s
as W is (s, ∆, b)-periodic, and the probability that some L of these q s elements belong to
proj∆ (Γ) is at most q sL times the probability that L distinct elements in Fq∆′ are mapped

−ζ∆ L . So the overall probability
to specific values in Fζ∆
q by ξ1 ◦ P1 , which is at most q
that |proj∆ (W ) ∩ proj∆ (Γ)| > L is at most q (s−ζ∆)L .

Now let j > 2 and assume |proj(j−1)∆ (W ) ∩ proj(j−1)∆ (Γ)| < L. By the (s, ∆, b)periodicity of W , for each of the (less than L) prefixes in proj(j−1)∆ (W ) ∩ proj(j−1)∆ (Γ),
there are at most q s extensions that fall in projj∆ (W ). Similarly to the argument used
for second step above, the probability that some L of these belong to projj∆ (Γ) is at
most (Lq s )L · q −ζ∆L . Thus, the probability that |projj∆ (W ) ∩ projj∆ (Γ)| > L is at most
L
L · q (s−ζ∆) .
Combining these arguments, we conclude that the probability over the choice of the
Pj ’s that |projb′ ∆ (W ) ∩ projb′ ∆ (Γ)| > L is at most
b′ (L · q (s−ζ∆))L 6 (2ckq −0.9ζ∆ )L 6 q −2L

where the last step used the assumption that q ζ∆ > (2q 2 ck)10/9 .

Finally, since there are at most q ck subspaces W ∈ F, by a union bound we have
that for all W ∈ F simultaneously, |projk′ (W ) ∩ projk′ (Γ)| < L with probability at least
1 − q ck q −L = 1 − q −ck over the choice of P1 , . . . , Pb′ .

To finish the proof, we need to verify the (F, s, ∆, b, L)-h.s.e property. That is, we
need to prove that w.h.p, |projj∆ (W )∩projj∆ (Γ)| 6 L for every W ∈ F and j = 1, 2, . . . , b.
By (15), this holds for j = 1, 2, . . . , b′ . By construction, the last ζk symbols of any vector
in Γ is a function of the first (1 − ζ)k = b′ ∆ symbols, so |projj∆ (W ) ∩ projj∆ (Γ)| 6 L also
holds for b′ < j 6 b.

6.4. Efficient computation of intersection with h.s.e. subsets. The key aspect
which makes h.s.e subsets useful in our context to prune the affine space of candidate
messages, and indeed motivated the exact specifics of the definition and aspects of its
construction, is the following claim which shows that intersection of a (s, ∆, b)-periodic
subspace with our h.s.e set can found efficiently.

AG CODES & NEAR-OPTIMAL LIST DECODING

23

Lemma 6.4. There is an algorithm running in time poly(k, q ζ∆ ) that provides the following guarantee. Given as input the polynomials P1 , . . . , Pb′ and Q underlying the construction of an (F, s, ∆, b, L)-h.s.e and (F, sb, ℓ)-evasive set Γ = Γ(P1 , . . . , Pb′ ; Q) and an
(s, ∆, b)-periodic subspace W ⊆ Fkq belonging to F, the algorithm computes the at most ℓ
elements of W ∩ Γ.
Proof. The proof essentially follows from the observations made in the proof of Theorem 6.3. First note that claim that |W ∩ Γ(P1 , . . . , Pb′ ; Q) 6 ℓ just follows from the
(F, sb, ℓ)-evasiveness of Γ. To compute W ∩ Γ, the algorithm iteratively computes the
intersections projj∆ (W ) ∩ projj∆ (Γ) for 1 6 j 6 b′ . As Γ is (F, s, ∆, b, L)-h.s.e, this intersection has size at most L. To compute projj∆ (W )∩projj∆ (Γ), the algorithm runs over the
at most q s possible extensions of each element of proj(j−1)∆ (W ) ∩ proj(j−1)∆ (Γ) that can
belong to projj∆ (W ) (due to the (s, ∆, b)-periodicity of W ), and checks which ones also
belong to projj∆ (Γ). The complexity amounts to q O(s) evaluations of degree O(k) polynomials, and thus takes q O(ζ∆) poly(k) time. To compute W ∩Γ from projb′ ∆ (W )∩projb′ ∆ (Γ),
we recall the earlier observation that the construction of Γ implies that there is a unique
extension of an element in projb′ ∆ (Γ) that belongs to Γ.

We conclude this section by recording in convenient form all necessary properties of
our h.s.e set construction, which follow from Theorem 6.3 and Lemma 6.4.
Theorem 6.5. Let ζ ∈ (0, 1), and b, ∆, s, and k = b∆ be positive integers satisfying
s < ζ∆/10. Let F be a family of at most q ck (s, ∆, b)-periodic subspaces of Fkq . Then
the poly(k, log q) time randomized construction from Definition 9 of the injective map
(1−ζ)2 k
HSE : Fq
→ Fkq satisfies the following properties:
(1−ζ)2 k

(1) Given x ∈ Fq

, HSE(x) can be computed using poly(k) operations over Fq .
(1−ζ)2 k

(2) For every W ∈ F, the set {x ∈ Fq
| HSE(x) ∈ W } has size at most O(c/ζ),
and can be computed in poly(k, q ζ∆ ) time.
7. Folded codes from the Garcia-Stichtenoth tower
Compared with the Hermitian tower of function fields, the Garcia-Stichtenoth tower
of function fields yields folded codes with better parameters due to the fact that the GarciaStichtenoth tower is an optimal one in the sense that the ratio of number of rational places
against genus achieves the maximal possible value. The construction of folded codes from
the Garcia-Stichtenoth tower is almost identical to the one from the Hermitian tower
except for one major difference: the redefined code from the Garcia-Stichtenoth tower is
constructed in terms of the local expansion at point P∞ , while in the Hermitian case local
expansion at P0 is considered. For convenience of the reader, we give a parallel description
of folded codes from the Garcia-Stichtenoth tower, while only sketching the identical parts.
7.1. Background on Garcia-Stichtenoth tower. Again let r be a prime power and let
q = r 2 . We denote by Fq the finite field with q elements. The Garcia-Stichtenoth towers
that we are going to use for our code construction were discussed in [4, 5]. The reader
may refer to [4, 5] for the detailed background on the Garcia-Stichtenoth function tower.
There are two optimal Garcia-Stichtenoth towers that are equivalent. For simplicity, we
introduce the tower defined by the following recursive equations [5]
xr
, i = 1, 2, . . . , e − 1.
(16)
xri+1 + xi+1 = r−1i
xi + 1

24

V. GURUSWAMI AND C. XING

Put Ke = Fq (x1 , x2 , . . . , xe ) for e > 2.
Rational places. The function field Ke has at least r e−1 (r 2 − r) + 1 rational places. One
of these is the “point at infinity” which is the unique pole P∞ of x1 (and is fully ramified).
The other r e−1 (r 2 − r) come from the rational places lying over the unique zero of x1 − α
for each α ∈ Fq with αr + α 6= 0. Note that for every α ∈ Fq with αr + α 6= 0, the unique
zero of x1 − α splits completely in Ke , i.e., there are r e−1 rational places lying over the
zero of x1 − α. Let P be the set of all the rational places lying over the zero of x1 − α for all
α ∈ Fq with αr + α 6= 0. Then, intuitively, one can think of the r e−1 (r 2 − r) rational places
αr
in P as being given by e-tuples (α1 , α2 , . . . , αe ) ∈ Feq that satisfy αri+1 + αi+1 = αr−1i +1 for
i

i = 1, 2, . . . , e − 1 and αr1 + α1 6= 0. For each value of α ∈ Fq , there are precisely r solutions
αr
to β ∈ Fq satisfying β r + β = αr−1
, so the number of such e-tuples is r e−1 (r 2 − r) (r 2 − r
+1
choices for α1 , and then r choices for each successive αi , 2 6 i 6 e).

Riemann-Roch spaces. As shown in [23], every function of Ke with a pole only at P∞
has an expression of the form


(e−2)r+1 r−1
r−1
i1 i2
i
e
X
X X
x x · · · xe 
,
ci h1 1 2
(17)
xa1 
···
π2 . . . πe−1
i1 =0

ie =0

i2 =0

where a > 0, ci ∈ Fq , and for 1 6 j < e, hj = xjr−1 + 1 and πj = h1 h2 . . . hj . Moreover,
Shum et al. [23] present an algorithm running in time polynomial in l that outputs a basis
of over Fq of L(lP∞ ) explicitly in the above form.

We stress that evaluating elements of L(lP∞ ) at the rational places of P is easy: we
simply have to evaluate a linear combination of the monomials allowed in (17) at the tuples
(α1 , α2 , . . . , αe ) ∈ Feq mentioned above. In other words, it is just evaluating an e-variate
polynomial at a specific subset of r e−1 (r 2 − r) points of Feq , and can be accomplished in
polynomial time.
Genus. The genus ge of the function field Ke is given by
 e/2
(r − 1)2
if e is even
ge =
(e−1)/2
(e+1)/2
(r
− 1)(r
− 1) if e is odd.

Thus the genus ge is at most r e . (Compare this with the er e bound for the Hermitian tower;
this smaller genus is what allows to pick e as large as we want in the Garcia-Stichtenoth
tower, while keeping the field size q fixed.)
A useful automorphism. Let γ be a primitive element of Fr and consider the automorphism σ ∈ Aut(Ke /Fq ) defined by
σ : xi 7→ γ (r+1)r

i−1

xi

for i = 1, 2, . . . , e.

Then the order of σ is r − 1 and furthermore, we have the following facts:

(i) σ keeps P∞ unchanged, i.e., P∞ σ = P∞ ;
(ii) Let P be the set of all the rational places lying over x1 − α for all α ∈ Fq with
αr + α 6= 0. Then |P| = (r − 1)r e . Moreover, σ divides P into r e orbits and each
orbit has r − 1 places. For an integer m with 1 6 m 6 r − 1, we can label N m
distinct elements
P1 , P1σ , . . . , P1σ


in P, as long as N 6 r e r−1
m .

m−1

m−1

, . . . , PN , PNσ , . . . , PNσ

AG CODES & NEAR-OPTIMAL LIST DECODING

25

The folded codes from the Garcia-Stichtenoth tower are defined similarly to the Hermitian case.
Definition 10 (Folded codes from the Garcia-Stichtenoth tower).
that m, k, N
 Assume

are positive integers satisfying 1 6 m 6 r − 1 and l/m < N 6 r e r−1
.
The
folded code
m
g
from Ke with parameters N, l, q, e, m, denoted by FGS(N,
l, q, e, m), encodes a message
function f ∈ L(lP∞ ) as




 
f (PN )
f (P2 )
f (P1 )
 f (PNσ ) 
 f (P1σ )   f (P2σ ) 
N




 
.
(18)
f 7→ 
..
 ∈ Fm
..
,...,
..
,
q




 
.
.
.
m−1
m−1
m−1
f (PNσ
)
)
f (P2σ
)
f (P1σ
g
Then we have a similar result on parameters of FGS(N,
l, q, e, m).

g
Lemma 7.1. The above code FGS(N,
l, q, e, m) is an Fq -linear code over alphabet size q m ,
l−ge +1
rate at least N m , and minimum distance at least N − ml .
7.2. Redefining the code in terms of local expansion at P∞ . In the Hermitian
case, we use coefficients of its power series expansion around P0 . However, for the GarciaStichtenoth tower we do not have such a nice point P0 . Fortunately, we can use point P∞
to achieve our mission.
Again for our decoding, we will actually recover the message f ∈ L(lP∞ ) in terms of
the coefficients of its power series expansion around P∞
f = T −l (f0 + f1 T + f2 T 2 + · · · )

where T := x1e is the local parameter at P∞ (which means that xe has exactly one pole at
P∞ , i.e., νP∞ (xe ) = −1).

In this case we can also show that one can efficiently move back-and-forth between
the representation of f ∈ L(lP∞ ) in terms of a basis for L(lP∞ ) and its power series
representation (f0 , f1 , . . . ) around P∞ . Since the mapping f 7→ (f0 , f1 , . . . ) is Fq -linear, it
suffices to compute the local expansion at P∞ of a basis for L(lP∞ ).
Lemma 7.2. For any n, one can compute the first n terms of the local expansion of the
basis elements (17) at P∞ using poly(n) operations over Fq .
Proof. First let h be a nonzero function
P∞ in Fqj(x1 , x2 , . . . , xe ) with νP∞ (h) = v ∈ Z. Assume
1
v
that the local expansion h = T
j=0 aj T is known. To find the local expansion h =
P∞
−v
j
T
j=0 cj T . Consider the identity



∞
∞
X
X
1=
cj T j  
aj T j  .
j=0

j=0

Then by comparing the coefficients of T i in the above identity, one has c0 = a−1
and
0
ci = −a−1
(c
a
+
·
·
·
+
c
a
)
can
be
easily
computed
recursively
for
all
i
>
1.
i−1 1
0 i
0
Thus, by the structure of the basis functions in (17), it is sufficient to find an algorithm of efficiently finding local expansions of xi at P∞ for every i = 1, 2, . . . , e. We can
inductively find the local expansions of xi at P∞ as follows. We note that νP∞ (xi ) = −r e−i
for i = 1, 2, . . . , e.
For i = e, xe has the local expansion

1
T

at P∞ .

26

V. GURUSWAMI AND C. XING

Now assume that we know the local expansion of xi . Then we can easily compute the
local expansion of xri + xi and hence the local expansion of 1/(xri + xi ). Let us assume that
e−i+1 P∞
j
1/(xri + xi ) has local expansion 1/(xri + xi ) = T r
j=0 αj T at P∞ for some αi ∈ Fq .
P
e−i+1
∞
j
Assume that 1/xi−1 has the local expansion 1/xi−1 = T r
j=0 βj T . To find βj , we
consider the identity

r
∞
∞
∞
X
X
X
1
1
1
e−i+1
r rj
j
r e−i+2
r e−i+1
αj T j .
= r
+
= Tr
βj T =
βj T + T
T
xi−1
xi−1
xi + xi
j=0

j=0

j=0

e−i+1

in the above identity, we have that β0 = α0
By comparing the coefficients of T j+r
and βj can be easily computed recursively by the following formula for all i > 1.

αj
if r 6 |j
βj = α − β r
if r|j.
j

j/r−1

Therefore, the local expansion of xi−1 at P∞ can be easily computed.



As in the Hermitian case, we will actually need to index the messages of the code by
the first k coefficients (f0 , f1 , . . . , fk−1 ) of the local expansion of the function f at P∞ .

Let us define the local expansion map evP∞ : L((k + 2ge − 1)P∞ ) → Fkq that maps f
to (f0 , f1 , . . . , fk−1 ) where f = T −(k+2ge−1) (f0 + f1 T + f2 T 2 + · · · ) is the local expansion
of f at P∞ .

Claim 7.3. evP∞ is an Fq -linear surjective map. Further, we can compute evP∞ using
poly(k, ge ) operations over Fq given a representation of the input f ∈ L((k + 2ge − 1)P∞ )
in terms of the basis (17).
The proof of this claim is similar to Claim 5.3. Note that the kernel of evP∞ is
L((2ge − 1)P∞ ) which has dimension exactly ge by the Riemann-Roch theorem.

For each (f0 , f1 , . . . , fk−1 ) ∈ Fkq , we can therefore pick a pre-image in L((k + 2ge −
1)P∞ ). For convenience, we will denote an injective map making such a unique choice by
κP∞ : Fkq → L((k + 2ge − 1)P∞ ). By picking the pre-images of a basis of Fkq and extending
it by linearity, we can assume κP∞ to be Fq -linear, and thus specify it by a (k + ge ) × k
matrix. We record this fact for easy reference below.
Claim 7.4. The map κP∞ : Fkq → L((k + 2ge − 1)P∞ ) is Fq -linear and injective. We can
compute a representation of this linear transformation using poly(k, ge ) operations over
Fq , and the map itself can be evaluated using poly(k, ge ) operations over Fq .
N
Now we redefine a version of the folded Garcia-Stichtenoth code that maps Fkq to (Fm
q )
by composing the folded encoding (18) from the original Definition 10 with κP∞ .

Definition 11 (Folded Garcia-Stichtenoth code using local expansion). The folded GarciaStichtenoth code (FGS code for short) FGS(N, k, q, e, m) maps f = (f0 , f1 , . . . , fk−1 ) ∈ Fkq
N
g
to FGS(N,
k + 2ge − 1, q, e, m)(κP∞ (f )) ∈ (Fm
q ) .

The rate of the above code equals k/(N m) and its distance is at least N − (k + 2ge −
1)/m.
7.3. List decoding FGS codes. The list decoding part for the codes from the GarciaStichtenoth tower is almost identical to the Hermitian tower. We only sketch this part
briefly.

AG CODES & NEAR-OPTIMAL LIST DECODING

27

If f is a function in L((k + 2ge − 1)P∞ ) whose encoding (18) agrees with the received
e −1
and
word y in at least t columns with t > D+k+2g
m−s+1


N (m − s + 1) − k + (s − 1)ge + 1
D=
,
s+1

then there exist Ai ∈ L(DP∞ ) for i = 1, 2, . . . , s and A0 ∈ L((D + k + 2ge − 1)P∞ ) such
that they are not all zero and
(19)

−1

Q(f, f σ , . . . , f σ

−(s−1)

) = A0 + A1 f + A2 f σ

−1

+ · · · + As f σ

−(s−1)

= 0.

Solving the functional equation for f . As in the Hermitian case, our goal next
is to recover the list of solutions f to the functional equation (19). Recall that our
message functions lie in Im(κP∞ ), so we can recover f by recovering the top k coefficients
(f0 , f1 , . . . , fk−1 ) of its local expansion.
(20)

f =T

−(k+2ge −1)

∞
X

fj T j

j=0

at P∞ . We now prove that (f0 , f1 , . . . , fk−1 ) for f satisfying Equation (19) belong to a
“periodic” subspace (in the sense of Definition 1) of not too large dimension.
Lemma 7.5. The set of solutions (f0 , f1 , . . . , fk−1 ) ∈ Fkq such that
f =T

−(k+2ge −1)

∞
X
j=0

obeys equation

A0 + A1 f + A2 f σ

(21)

fj T j ∈ L((k + 2ge − 1)P∞ )

−1

+ · · · + As f σ

−(s−1)

=0

k
⌉)-periodic subspace.
when at least one Ai is nonzero is an (s − 1, r − 1, ⌈ r−1

Further, there are at most q N m+s+1 possible choices of this subspace over varying
choices of the Ai ’s.

Proof. Let u = min{νP∞ (Ai ) : i = 1, 2, . . . , s}. Then it is clear that u 6 0 and νP∞ (A0 ) >
u − (k + 2ge − 1). Each Ai has a local expansion at P∞ :
Ai = T u

∞
X

ai,j T j

j=0

for i = 1, . . . , s − 1 and A0 has a local expansion at P∞ :
∞
X
a0,j T j
A0 = T u−(k+2ge−1)
j=0

From the definition of u, one knows that the polynomial
is nonzero.

B0 (X) := a1,0 + a2,0 X + · · · + as,0 X s−1

Assume that at P∞ , the function f has a local expansion (20). Then f σ
expansion at P∞ as follows
∞
X
σ−i
−(k+2ge −1)i −(k+2ge −1)
ξ ji fj T j ,
f
=ξ
T
j=0

−i

has a local

28

V. GURUSWAMI AND C. XING

where ξ = 1/γ.
−1

The coefficient of T d+u−(k+2ge−1) in the local expansion of Q(f, f σ , . . . , f σ
(22)

0 = B(ξ

d−(k+2ge −1)

)fd +

d−1
X

−(s−1)

) is

bi fi + a0,d ,

i=0

where bi ∈ Fq is a linear combination of ai,j which does not involve fj . Hence, fd is
uniquely determined by f0 , . . . , fd−1 as long as B(ξ d−(k+ge −1) ) 6= 0.

Let S := {0 6 d 6 r − 2 : B(ξ d−(k+ge −1) ) = 0}. Then it is clear that |S| 6 s − 1 since
the order of ξ is r −1 and B0 (X) has degree at most s−1. Thus, B(ξ d−(k+ge −1) ) 6= 0 if and
only if j mod (r − 1) ∈
/ S; and in this case fj lis a fixed
affine linear combination of fi for
m

0 6 i < j. Note that B0 (X) has at most (s−1)

k
r−1

roots among {ξ i : i = 0, 1, . . . , k−1}.

It follows that the set of solutions (f0 , f1 , . . . , fk−1 ) is an affine space W ⊂ Fkq , and the
l
m
k
dimension of W is at most (s − 1) r−1
.

k
The fact that W is (s, r − 1, ⌈ r−1
⌉)-periodic subspace follows from (22). Note that
the coefficients bd−j for j > 1 in that equation are given by Bj (ξ d−j−(k+2ge −1) ), where
Bj (X) := a1,j + a2,j X + · · · + as,j X s−1 . Therefore, once the values of fi , 0 6 i <
(j − 1)(r − 1) are fixed, the possible choices for the next block of (r − 1) coordinates,
f(j−1)(r−1) , · · · , fj(r−1)−1 , lie in an affine shift of a fixed subspace of dimension at most
(s − 1). Further, the affine shift is an affine linear combination of the fi ’s in the previous
blocks.

Finally, by the choice of D, the total number of possible (A0 , A1 , . . . , As ) and hence
the number of possible functional equations (21), is at most q N (m−s+1)+s+1 6 q N m+s+1 .
Therefore, the number of possible candidate subspaces W is also at most q N m+s+1 .

Similar to the bound (14) for the Hermitian case, we conclude, after some simple
calculations and using the upper bound on genus ge 6 r e , that one can find a representation
of the (s, r − 1)-periodic subspace containing all candidate messages (f0 , f1 , . . . , fk−1 ) in
polynomial time, when the fraction of errors τ = 1 − t/N satisfies


re
k
3m
s
.
1−
−
(23)
τ6
s+1
N (m − s + 1)
m − s + 1 mN
8. Pruning list for folded AG codes using h.s.e sets
8.1. Combining folded Hermitian codes and h.s.e sets. Instead of encoding arbitrary f ∈ Fkq by the folded Hermitian code (Definition 5), we can restrict the messages f
to belong to the range of our h.s.e set, so that the affine space of solutions guaranteed by
Lemma 5.7 can be efficiently pruned to a small list. The formal claim is below.
Theorem 8.1. Let e > 2 be an integer, r > 2e be a large enough prime power, q = r 2 ,
and ζ ∈ (1/q, 1). Let k 6 q ζq/2 be a positive integer. Let s, m be positive integers satisfying
1 6 s 6 m 6 q − 1 and s < ζq/12. Finally let N be an integer satisfying k + 2er e 6 N m 6
(q − 1)r e .
(1−ζ)2 k

Consider the code C1 with encoding E1 : Fq

N defined as
→ (Fm
q )

E1 (x) = FH(N, k, q, e, m)(HSE(x)) ,

AG CODES & NEAR-OPTIMAL LIST DECODING

29

(1−ζ)2 k

for a random map HSE : Fq
→ Fkq as constructed in Definition 9 for a period size
k
∆ = q − 1 and b = ⌈ q−1 ⌉ (where technically we pad the input Fkq with 0’s to make its length
b∆ to feed into HSE).
Then, the code C1 code has rate R = (1−ζ)2 k/(N m), can be encoded in poly(N mq ζq )
time, and with high probability over the choice of HSE, it is (τ, ℓ)-list decodable in time
poly(N mq ζq ) for ℓ 6 O(1/(Rζ)) and


s
er e
k
3m
τ=
.
1−
−
s+1
N (m − s + 1)
m − s + 1 mN
Proof. The claim about the rate is clear, and the encoding time follows from the time to
compute HSE recorded in Theorem 6.5.
By (3), the genus ge 6 er e , and so the condition on N, m meets the requirement for
the construction of the folded Hermitian tower based code in Definition 4, and the claimed
value of the error fraction τ satisfies (14). By Lemma 5.7, we know that the candidate
k
⌉)-periodic
messages found by the decoder lie in one of at most q 2N m possible (s, q −1, ⌈ q−1
6
subspaces.
One can check that the conditions of Theorem 6.5 are met for our choice of ζ, s, q, k, ∆.
Appealing to Theorem 6.5 with the choice c = 2N m/k = O(1/R), we conclude that, with
high probability over the choice of HSE, there is a decoding algorithm running in time
poly(N mq ζq ) to list decode C1 from a fraction τ of errors, outputting at most O(1/(Rζ))
messages in the worst-case.

Let ε > 0 be a small positive constant, and a family of codes of length N (assumed
large enough) and rate R ∈ (0, 1) is sought. Pick n to be a growing parameter.

By picking s = Θ(1/ε), m = Θ(1/ε2 ), r = ⌊log n⌋, e = ⌈ logloglogn n ⌉, ζ = (log n log log n)−1 ,

N = ⌊ (r

2 −1)r e

m

⌋, and k proportional to N m in Theorem 8.1, we can conclude the following.

Corollary 8.2. For any R ∈ (0, 1) and positive constant ε ∈ (0, 1), there is a Monte Carlo
2
construction of a family of codes of rate at least R over an alphabet size (log N )O(1/ε ) that
are encodable and (1 − R − ε, O(R−1 log N log log N ))-list decodable in poly(N, 1/ε) time,
where N is the block length of the code.
Our promised main result (Theorem 1.1) achieves better parameters than the above
— an alphabet size of exp(Õ(1/ε2 )) and list-size of O(1/(Rε)). This is based on the
Garcia-Stichtenoth tower and is described next.
8.2. Combining folded Garcia-Stichtenoth codes and h.s.e sets. Similarly to Section 8.1, we now show how to pre-code the messages of the FGS code with a h.s.e subset.
The approach is similar, though we need one additional idea to ensure that we can pick
parameters so that the base field Fq can be constant-sized and obtain a final list-size
bound that is a constant independent of the code length. This idea is to work with a
larger “period size” ∆ for the periodic subspaces, based on the following observation.
Observation 8.3. Let W be an (s, ∆, b)-periodic subspace of Fkq for k = b∆. Then W is
also (su, ∆u, b)-periodic for every integer u, 1 6 u 6 b.
6Technically, it will belong to proj (W ) of such a periodic subspace W , but we may pretend that there
k

are (q−1)⌈k/(q−1)⌉−k extra dummy coordinates which we decode. Or we can just assume for convenience
that k is divisible by (q − 1).

30

V. GURUSWAMI AND C. XING

As in the Hermitian case, instead of encoding arbitrary f ∈ Fkq by the folded GarciaStichtenoth code (Definition 18), we will restrict the messages f to belong to the range of
our h.s.e set. This will ensure that the affine space of solutions guaranteed by Lemma 7.5
can be efficiently pruned to a small list.
Theorem 8.4. Let r be a prime power, q = r 2 , and e > 2 be an integer, and ζ ∈ (0, 1).
Let k 6 q ζ∆/2 be a positive integer. Let ∆ 6 k be a multiple of (r − 1), say ∆ = u(r − 1)
for a positive integer u.
Let s, m be positive integers satisfying 1 6 s 6 m 6 r − 1 and s < ζr/12. Finally let
N be an integer satisfying k + 2r e 6 N m 6 (r − 1)r e .
(1−ζ)2 k

Consider the code C2 with encoding E2 : Fq

N defined as
→ (Fm
q )

E2 (x) = FGS(N, k, q, e, m)(HSE(x)) ,
(1−ζ)2 k

for a random map HSE : Fq
→ Fkq as constructed in Definition 9 for a period size ∆
k
and b = ⌈ ∆ ⌉ (where we pad the input Fkq with 0’s to make its length b∆ to feed into HSE).

The code C2 has rate R = (1 − ζ)2 k/(N m), can be encoded in poly(N mq ζ∆ ) time,
and w.h.p over the choice of HSE, it is (τ, ℓ)-list decodable in time poly(N mq ζ∆ ) for
ℓ 6 O(1/(Rζ)) and


re
k
3m
s
.
1−
−
(24)
τ=
s+1
N (m − s + 1)
m − s + 1 mN
Proof. The proof is very similar to that of Theorem 8.1. The claim about the rate is clear,
and the encoding time follows from the time to compute HSE recorded in Theorem 6.5.

The genus ge is now upper bounded by r e , and so the condition on N, m meets the
requirement for the construction of the folded Hermitian tower based code in Definition
4, and the claimed value of the error fraction τ satisfies (14). By Lemma 5.7, we know
that the candidate messages found by the decoder lie in one of at most q 2N m possible
k
(s, r − 1, ⌈ r−1
⌉)-periodic subspaces.7 Now by Observation 8.3, each of these subspaces is
k
⌉)-periodic. One can check that the conditions of Theorem 6.5 are met for
also (su, ∆, ⌈ ∆
our choice of ζ, s, q, k, ∆ and taking su to play the role of s (since s < ζr/12, we have
su < ζ∆/10).
Appealing to Theorem 6.5 with the choice c = 2N m/k = O(1/R), we conclude that
there is a decoding algorithm running in time poly(N mq ζ∆ ) to list decode C2 from a
fraction τ of errors, outputting at most O(1/(Rζ)) messages in the worst-case.

Finally, all that is left to be done is to pick parameters to show how the above can
lead to optimal rate list-decodable codes over a constant-sized alphabet which further
achieve very good list-size.
Let ε > 0 be a small positive constant, and a family of codes of length N (assumed
large enough) and rate R ∈ (0, 1) is sought. Pick n to be a growing parameter.
n
Let us pick s = Θ(1/ε), m = Θ(1/ε2 ), ζ = ε/12, r = Θ(1/ε), q = r 2 , and e = ⌈ log
log r ⌉,
e

N = ⌊ (r−1)r
⌋, and k = RN m(1 + ε). This ensures that (i) there are at least n = N m
m
rational places and so we get a code of length at least n/m = N , (ii) the rate of the code
C2 is at least R, and (iii) the error fraction (24) is at least 1 − R − ε.
7Technically, it will belong to proj (W ) of such a periodic subspace W , but we may pretend that there
k

are (r−1)⌈k/(r−1)⌉−k extra dummy coordinates which we decode. Or we can just assume for convenience
that r − 1 divides k.

AG CODES & NEAR-OPTIMAL LIST DECODING

31

The remaining part is to pick a multiple ∆ of (r − 1) so that the k 6 q ζ∆/2 condition
log n
⌉ and ∆ = (r − 1)u. With these
is met. This can be achieved by choosing u = ⌈ log(1/ε)
choices, we can conclude the following, which is one of the main end goals of this paper.
Theorem 8.5 (Main; Corollary to Theorem 8.4 with above choice of parameters). For
any R ∈ (0, 1) and positive constant ε ∈ (0, 1), there is a Monte Carlo construction of
a family of codes of rate at least R over an alphabet size exp(O(log(1/ε)/ε2 )) that are
encodable and (1 − R − ε, O(1/(Rε))-list decodable in poly(N ) time, where N is the block
length of the code.
It may be instructive to recap why the Hermitian tower could not give a result like
the above one. In the Hermitian case, the ratio ge /n of the genus to the number of rational
√
places was about e/r = e/ q, and thus we needed q > e2 . Since the period ∆ was about
q, the running time
of the decoder was bigger than q Ω(ζq) , whereas the length of the code
√
O(
q)
was at most q
. This dictated the choice of q ≈ log2 n, and then to keep the running
time polynomial, we had to take ζ ≈ (log n log log n)−1 .
9. List decoding AG codes with subfield evaluation points
In this section, we will present a linear-algebraic list decoding algorithm for algebraicgeometric (AG) codes based on evaluations of functions at rational points over a subfield.
The algorithm will manage to correct a large fraction of errors, and pin down the possible
messages to a well-structured affine subspace of dimension much smaller than that of the
code. For simplicity, we begin with the case of Reed-Solomon codes in Section 9.1. We
then extend it to a general framework for decoding AG codes based on constant field
extensions in Section 9.2. Finally, in Section 9.1, we instantiate the general framework
(with a slight twist) to codes based on the Garcia-Stichtenoth tower.
9.1. Decoding Reed-Solomon codes. Our list decoding algorithm will apply to ReedSolomon codes with evaluation points in a subfield, defined below.
Definition 12. [Reed-Solomon code with evaluations in a subfield] Let Fq be a finite
field with q elements, and m a positive integer. Let n, k be positive integers satisfying
1 6 k < n 6 q. The Reed-Solomon code RS(q,m) [n, k] is a code over alphabet Fqm that
encodes a polynomial f ∈ Fqm [X] of degree at most k − 1 as
f (X) 7→ (f (α1 ), f (α2 ), · · · , f (αn ))
where α1 , α2 , . . . , αn are an arbitrary sequence of n distinct elements of Fq .
Note that while the message polynomial has coefficients from Fqm , the encoding only
contains its evaluations at points in the subfield Fq . The above code has rate k/n, and
minimum distance (n − k + 1).

We now present a list decoding algorithm for the above Reed-Solomon codes. Suppose
the codeword (f (α1 ), f (α2 ), · · · , f (αn )) is received as (y1 , y2 , . . . , yn ) ∈ Fnqm with at most
e = τ n errors (i.e., yi 6= f (αi ) for at most e values of i ∈ {1, 2, . . . , n}). The goal is to
recover the list of all polynomials of degree less than k whose encoding is within Hamming
distance e from y. As is common in algebraic list decoders, the algorithm will have two
steps: (i) interpolation to find an algebraic equation the message polynomials must satisfy,
and (ii) solving the equation for the candidate message polynomials.

32

V. GURUSWAMI AND C. XING

Interpolation step. Let 1 6 s 6 m be an integer parameter of the algorithm. Choose
the “degree parameter” D to be


n−k+1
.
(25)
D=
s+1
Definition 13 (Space of interpolation polynomials). Let P be the space of polynomials
Q ∈ Fqm [X, Y1 , Y2 , . . . , Ys ] of the form

(26)

Q(X, Y1 , Y2 , . . . , Ys ) = A0 (X) + A1 (X)Y1 + A2 (X)Y2 + · · · + As (X)Ys ,

with each Ai ∈ Fqm [X] and deg(A0 ) 6 D + k − 1 and deg(Ai ) 6 D for i = 1, 2, . . . , s.
The lemma below follows because for our choice of D, the number of degrees of
freedom for polynomials in P exceeds the number n of interpolation conditions (27). We
include the easy proof for completeness.
Lemma 9.1. There exists a nonzero polynomial Q ∈ P such that
(27)

2

Q(αi , yi , yiq , yiq , · · · , yiq

s−1

)=0

for

i = 1, 2, . . . , n .

Further such a Q can be found using O(n3 ) operations over Fqm .
Proof. Note that P is an Fqm -vector space of dimension

(D + k) + s(D + 1) = (D + 1)(s + 1) + k − 1 > n,

where the last inequality follows from our choice (25). The interpolation conditions required in the lemma impose n homogeneous linear conditions on Q. Since this is smaller
than the dimension of P, there must exist a nonzero Q ∈ P that meets the interpolation
conditions
2
s−1
Q(αi , yi , yiq , yiq , · · · , yiq ) = 0 for i = 1, 2, . . . , n .
Finding such a Q amounts to solving a homogeneous linear system over Fqm with n
constraints and at most dim(P) 6 n + s + 2 unknowns, which can be done in O(n3 )
time.

Lemma 9.3 below shows that any polynomial Q given by Lemma 9.1 yields an algebraic condition that the message functions f we are interested in list decoding must
satisfy.
Definition 14 (Frobenius action on polynomials). For a polynomial f ∈ Fqm [X] with
f (X) = f0 + f1 X + · · · + fk−1 X k−1 , define the polynomial f σ ∈ Fqm [X] as f σ (X) =
q
f0q + f1q X + · · · + fk−1
X k−1 .
i

For i > 2, we define f σ recursively as (f σ

i−1

)σ .

The following simple fact is key to our analysis.
j

j

Fact 9.2. If α ∈ Fq , then f (α)q = (f σ )(α) for all j = 1, 2, . . . .
Lemma 9.3. Suppose Q ∈ P satisfies the interpolation conditions (27). Suppose f ∈
Fqm [X] of degree less than k satisfies f (αi ) 6= yi for at most e values of i ∈ {1, 2, . . . , n}
s−1
2
s
(n − k). Then Q(X, f (X), f σ (X), f σ (X), · · · , f σ (X)) = 0.
with e 6 s+1
2

Proof. Define the polynomial Φ ∈ Fqm [X] by Φ(X) := Q(X, f (X), f σ (X), f σ (X), · · · ,
s−1
f σ (X)). By the construction of Q and the fact that deg(f ) 6 k − 1, we have deg(Φ) 6
n
s
D + k − 1 6 n−k+1
s+1 + k − 1 = s+1 + s+1 (k − 1).

AG CODES & NEAR-OPTIMAL LIST DECODING

qj

yi

33

Suppose yi = f (αi ). By Fact 9.2, we have yiq = f (αi )q = (f σ )(αi ), and similarly
j
= (f σ )(αi ) for j = 2, 3, . . . . Thus for each i such that f (αi ) = yi , we have
Φ(αi ) = Q(αi , f (αi ), f σ (αi ), · · · , f σ

s−1

(αi )) = Q(αi , yi , yiq , · · · , yiq

s−1

)=0.

s
n
+ s+1
k zeroes. Since this exceeds the upper bound on
Thus Φ has at least n − e > s+1
the degree of Φ, Φ must be the zero polynomial.


Finding candidate solutions. The previous two lemmas imply that the polynomials
s
f whose encodings differ from (y1 , · · · , yn ) in at most s+1
(n − k) positions can be found
s−1
= 0.
amongst the solutions of the functional equation A0 + A1 f + A2 f σ + · · · + As f σ
We now prove that these solutions form a well-structured affine space over Fq .
Pk−1
Lemma 9.4. For integers 1 6 s 6 m, the set of solutions f = i=0
fi X i ∈ Fqm [X] to
the equation
(28)

A0 (X) + A1 (X)f (X) + A2 (X)f σ (X) + · · · + As (X)f σ

s−1

(X) = 0

when at least one of {A0 , A1 , . . . , As } is nonzero is an affine subspace over Fq of dimension
at most (s − 1)k. Further, fixing an Fq -basis of Fqm and viewing each fi as an element of
mk
Fm
q , the solutions are an (s − 1, m, k)-periodic subspace of Fq . A canonical representation
of this periodic subspace (in the sense of Definition 2) can be computed in poly(k, m, log q)
time.
Proof. If f, g are two solutions to (28), then so is αf + βg for any α, β ∈ Fq with α + β = 1.
So the solutions to (28) form an affine Fq -subspace. We now proceed to analyze the
structure of the subspace.
First, by factoring out a common powers of X that divide all of A0 (X), A1 (X), . . . , As (X),
we can assume that at least one Ai∗ (X) for some i∗ ∈ {0, 1, . . . , s} is not divisible by X,
and has nonzero constant term. Further, if A1 (X), . . . , As (X) are all divisible by X, then
so is A0 (X), so we can take i∗ > 0.
Let us denote Aι (X) = aι,0 + aι,1 X + aι,2 X 2 + · · · for ι = 0, 1, 2, . . . , s. For l =
0, 1, 2, . . . , k − 1, define the linearized polynomial
(29)

2

Bl (X) = a1,l X + a2,l X q + a3,l X q + · · · + as,l X q

s−1

.

We know that ai∗ ,0 6= 0, and therefore B0 6= 0. This implies that the solutions β ∈ Fqm to
B0 (β) = 0 is a subspace, say W , of Fqm of dimension at most s − 1.
Fix an i ∈ {0, 1, . . . , k − 1}. Expanding the equation (28) and equating the coefficient
of X i to be 0, we get
(30)

a0,i + Bi (f0 ) + Bi−1 (f1 ) + · · · + B1 (fi−1 ) + B0 (fi ) = 0 .

This implies fi ∈ W +θi for some θi ∈ Fqm that is determined by f0 , f1 , . . . , fi−1 . Therefore,
for each choice of f0 , f1 , . . . , fi−1 , fi must belong to a fixed coset of the subspace W of
dimension at most s − 1. Thus, the solutions belong to an (s − 1, m, k)-periodic subspace.
Also, it is clear from (30) that a canonical representation of the periodic subspace can be
computed in poly(k, m, log q) time.

Combining Lemmas 9.3 and 9.4, we see that one can find an affine space of dimension
(s − 1)k that contains the coefficients of all polynomials whose encodings differ from the
s
(1 − R) of the positions. Note the dimension
input (y1 , . . . , yn ) in at most a fraction s+1
of the message space of the Reed-Solomon code RS(q,m) [n, k] over Fq is km. The above
lemma pins down the candidate polynomials to a space of dimension (s − 1)k. For s ≪ m,

34

V. GURUSWAMI AND C. XING

this is a lot smaller. In particular, it implies one can list decode in time sub-linear in the
code size (the proof follows by taking s = ⌈1/ε⌉ and m > γs ).
Corollary 9.5. For every R ∈ (0, 1), and ε, γ > 0, there is a positive integer m such that
for all large enough prime powers q, the Reed-Solomon code C = RS(q,m) [q, Rq] can be list
decoded from a fraction (1 − R − ε) of errors in |C|γ time, outputting a list of size at most
|C|γ .
Since the dimension of the subspace guaranteed by Lemma 9.4 grows linearly in k,
we still cannot afford to list this subspace as the decoder’s output for polynomial time
decoding. Instead, we will use a “pre-code” that only allows polynomials with coefficients
in a carefully chosen subset that is guaranteed to have small intersection with the space
of solutions to any equation of the form (28). Further, this intersection can be found
quickly without going over all solutions to (28). In Section 10, we will see the approach
to accomplish this based on subspace designs.
9.2. Decoding algebraic-geometric codes. In this section we generalize the ReedSolomon algorithm to algebraic-geometric codes. The description in this section will be
for a general abstract AG code. So we will focus on the algebraic ideas, and not mention
complexity estimates. The next subsection will focus on a specific AG code based on
Garcia-Stichtenoth function fields, which will require a small change to the setup, and
where we will also mention computational aspects. We assume familiarity with the basic
setup of algebraic function fields and codes based on function fields, and use standard
terminology and notation; the reader is referred to Stichtenoth’s book for basic background
information [25].
Let F/Fq be a function field of genus g. Let P∞ , P1 , P2 , . . . , PN be N + 1 distinct
Fq -rational places. Let σ ∈ Gal(Fqm /Fq ) be the Frobenius automorphism, i.e, ασ = αq for
all α ∈ Fqm . Then we can extend σ to an automorphism in Gal(Fm /F ), where Fm is the
constant extension Fqm · F . Note that P σ = P for any place of F .

For a place P of F , we denote by νP the discrete valuation of P . For an integer l, we
consider the Riemann-Roch space over Fq defined by
L(lP∞ ) := {h ∈ F \ {0} : νP∞ (h) > −l} ∪ {0}.

Then the dimension ℓ(lP∞ ) is at least l−g+1 and equality holds if l > 2g−1. Furthermore,
we define the Riemann-Roch space over Fqm by
Lm (lP∞ ) := {h ∈ Fm \ {0} : νP∞ (h) > −l} ∪ {0}.
Consider the Goppa geometric code defined by
C(m; l) := {(f (P1 ), f (P2 ), . . . , f (PN )) : f ∈ Lm (lP∞ )}.
The following result is a fundamental fact about algebraic-geometric codes.
Lemma 9.6. The above code C(m; l) is an Fqm -linear code over Fqm , rate at least
and minimum distance at least N − l.

l−g+1
N ,

We now present a list decoding algorithm for the above codes. The algorithm follows
the linear-algebraic list decoding algorithm for RS codes. Suppose a codeword encoding
f ∈ Lm ((k + 2g − 1)P∞ ) is transmitted and received as y = (y1 , y2 , . . . , yN ).
Given such a received word, we will interpolate a nonzero linear polynomial over Fm

(31)

Q(Y1 , Y2 , . . . , Ys ) = A0 + A1 Y1 + A2 Y2 + · · · + As Ys

AG CODES & NEAR-OPTIMAL LIST DECODING

35

where Ai ∈ Lm (DP∞ ) for i = 1, 2, . . . , s and A0 ∈ Lm ((D + k + 2g − 1)P∞ ) with the
degree parameter D chosen to be


N − k + (s − 1)g + 1
.
(32)
D=
s+1
If we fix a basis of Lm (DP∞ ) and extend it to a basis of Lm ((D + k + 2g − 1)P∞ ), then
the number of freedoms of A0 is at least D + k + g and the number of freedoms of Ai is at
least D − g + 1 for i > 1. Thus, the total number of freedoms in the polynomial Q equals
(33)

s(D − g + 1) + D + k + g = (s + 1)(D + 1) − (s − 1)g − 1 + k > N.

for the above choice (32) of D. The interpolation requirements on Q ∈ Fm [Y1 , . . . , Ys ] are
the following:
(34)

Q(yi , yiσ , . . . , yiσ

s−1

) = A0 (Pi ) + A1 (Pi )yi + A2 (Pi )yiσ + · · · + As (Pi )yiσ

s−1

=0

for i = 1, 2, . . . , N . Thus, we have a total of N equations to satisfy. Since this number
is less than the number of freedoms in Q, we can conclude that a nonzero linear function
Q ∈ Fm [Y1 , . . . , Ys ] of the form (31) satisfying the interpolation conditions (34) can be
found by solving a homogeneous linear system over Fqm with at most N constraints and
at least s(D − g + 1) + D + k + g variables.
The following lemma gives the algebraic condition that the message functions f ∈
Lm ((k + 2g − 1)P∞ ) we are interested in list decoding must satisfy.

Lemma 9.7. If f is a function in Lm ((k + 2g − 1)P∞ ) whose encoding agrees with the
received word y in at least t positions with t > D + k + 2g − 1, then
(35)

Q(f, f σ , . . . , f σ

s−1

) = A0 + A1 f + A2 f σ + · · · + As f σ

s−1

= 0.

Proof. The proof proceeds by comparing the number of zeros of the function Q(f, f σ ,
s−1
s−1
with D + k + 2g − 1. Note that Q(f, f σ , . . . ,
. . . , f σ ) = A0 + A1 f + A2 f σ + · · · + As f σ
s−1
σ
) is a function in Lm ((D + k + 2g − 1)P∞ ). If position i of the encoding of f agrees
f
with y, then
0 = A0 (Pi ) + A1 (Pi )yi + A2 (Pi )yiσ + · · · + As (Pi )yiσ

s−1

= A0 (Pi ) + A1 (Pi )f (Pi ) + A2 (Pi )(f (Pi ))σ + · · · + As (Pi )(f (Pi ))σ
= A0 (Pi ) + A1 (Pi )f (Pi ) + A2 (Pi )f σ (Pi ) + · · · + As (Pi )f σ
σ

= (A0 + A1 f + A2 f + · · · + As f

σs−1

s−1

s−1

(Pi )

)(Pi )

s−1

i.e., Pi is a zero of Q(f, f σ , . . . , f σ ). Thus, there are at least t zeros for all the agreeing
s−1
positions. Hence, Q(f, f σ , . . . , f σ ) must be the zero function when t > D+k+2g−1. 
Let P be a rational place in F and let T ∈ F be a local parameter of P . Then T σ = T .
Here, we have two scenarios, i.e., P = P∞ or P 6= P∞ . In Subsection 9.3, we will consider
the case where P = P∞ for the Garcia-Stichtenoth tower. While in this subsection, we
only discuss the case where P 6= P∞ . This was the case with Reed-Solomon codes with
message polynomials in Fq [X] in Subsection 9.1 where P∞ was the pole of X, and P the
zero of X.
Assume that a function f ∈ Lm ((k + 2g − 1)P∞ ) has a local expansion at P
(36)

f=

∞
X
j=0

fj T j

36

V. GURUSWAMI AND C. XING

for some fj ∈ Fqm . Then f is uniquely determined by (f0 , f1 , . . . , fk+2g−1 ) since f has the
pole degree at most k + 2g − 1.
Lemma 9.8. The set of solutions f ∈ Lm ((k + 2g − 1)P∞ ) to the equation (34)
A0 + A1 f + A2 f σ + · · · + As f σ

s−1

=0

when at least one Ai is nonzero has size at most q (s−1)(k+2g−1) . Further, the possible
coefficients (f0 , f1 , . . . , fk+2g−1 ) of f ’s local expansion at P belong to an (s − 1, m)-ultra
(k+2g−1)m
periodic affine subspace of Fq
.
Proof. The argument is very similar to Lemma 9.4. Let u = min{νP∞ (Ai ) : i =
1, 2, . . . , s}. Then it is clear that u > 0 and νP (A0 ) > u. Each Ai has a local expansion at P :
∞
X
ai,j T j
Ai = T u
j=0

for i = 0, 1, . . . , s.

i

Assume that at P , the function f has a local expansion (36). Then f σ has a local
expansion at P as follows
∞
X
i
σi
fjq T j .
f =
j=0

For l = 0, 1, . . . , define the linearized polynomial
Bl (X) := a1,l X + a2,l X q + · · · + as,l X q

s−1

From the definition of u, one knows that B0 (X) is nonzero. Equating the coefficient of
s−1
to equal 0 gives us the condition
T d+u in A0 + A1 f + A2 f σ + · · · + As f σ

(37)

a0,d + Bd (f0 ) + Bd−1 (f1 ) + · · · + B0 (fd ) = 0 .

Let W = {α ∈ Fqm : B0 (α) = 0}. Then W is an Fq -subspace of Fqm of dimension at
most s − 1, since B0 is a nonzero linearized polynomial of q-degree at most s − 1. As
in Lemma 9.4, for each fixed f0 , f1 , . . . , fd−1 , the coefficient fd must belong to a coset
of the subspace W . This implies that the coefficients (f0 , f1 , . . . , fk+2g−1 ) belong to an
m(k+2g−1)
(s − 1, m, k + 2g − 1)-periodic subspace of Fq
. In particular, there are at most
q (s−1)(k+2g−1) solutions f ∈ Lm ((k + 2g − 1)P∞ ) to (34).

The equation (37) also shows that each group of ℓ successive coefficients fd−ℓ+1 ,
fd−ℓ+2 , · · · , fd belong to cosets of the same underlying ℓ(s − 1) dimensional subspace of
Fmℓ
q . This implies that (f0 , f1 , . . . , fk+2g−1 ) in fact belong to an (s − 1, m)-ultra periodic
subspace.8

Restricting message functions using local expansions. Using Lemma 9.8, we will
recover the message in terms of the coefficients of its local expansion at P . In order to prune
the subspace of possible solutions, we will pick a subcode that corresponds to restricting
the coefficients to a carefully constructed subset of all possibilities. This requires us to
index message functions in terms of the local expansion coefficients. However, not all
(k + 2g − 1) tuples over Fqm arise in the local expansion of functions in the k-dimensional
subspace Lm ((k + 2g − 1)P∞ ). Below we show that we can find a k-dimensional subspace
8This ultra-periodicity was also true for the Reed-Solomon case in Lemma 9.4, but we did not state it

there as we will not make use of this extra property for picking a subcode in the case of Reed-Solomon
codes.

AG CODES & NEAR-OPTIMAL LIST DECODING

37

of Lm ((k + 2g − 1)P∞ ) such that their top k local expansion coefficients give rise to all
k-tuples over Fqm .
Lemma 9.9. There exist a set of functions {g1 , g2 , . . . , gk } in Lm ((k + 2g − 1)P∞ ) such
that the k × k matrix A formed by taking the ith row of A to be the first k coefficients in
the local expansion (36) for gi at P is non-singular.
Proof. Let {ψ1 , ψ2 , . . . , ψg } be a basis of Lm ((k + 2g − 1)P∞ − kP ). Extend this basis to
a basis {ψ1 , ψ2 , . . . , ψg , g1 , g2 , . . . , gk } of Lm ((k + 2g − 1)P∞ ). We claim that the functions
{g1 , g2 , . . . , gk } are our desired functions.

Suppose that the matrix A is obtained from expansion of functions gi and it is
P
singular. This implies that there exists elements {λi }ki=1 such that the function ki=1 λi gi
P∞
P
k
i
has expansion
the function
i=k ai T at P for some ai ∈ Fq m . Therefore,
i=1 λi gi
Pk
belongs to the space Lm ((k + 2g − 1)P∞ − kP ), i.e.,
i=1 λi gi is a linear combination
of ψ1 , ψ2 , . . . , ψg . This forces that all λi are equal to 0 since {ψ1 , . . . , ψg , g1 , g2 , . . . , gk } is
linearly independent. This completes the proof.

With the above lemma in place, we now describe our AG code in a manner convenient
for pruning the possible local expansion coefficients.

Encoding. Assume that we have found a set of functions {g1 , g2 , . . . , gk } of Lm ((k +
2g − 1)P∞ ) as in Lemma 9.9. After elementary row operations on the matrix A defined
in Lemma 9.9, we may assume that A is the k × k P
identity matrix, i.e., we assume that,
j
for 1 6 i 6 k, the function gi has expansion T i−1 + ∞
j=k λij T for some λij ∈ Fq m .
Now for any subset M ⊆ Fkqm , we may assume that our messages belong to M ,
and encode each message (a1 , a2 , . . . , ak ) ∈ M to the codeword (f (P1 ), f (P2 ), . . . , f (PN )),
P
where f = ki=1 ai gi . Thus, our actual code is a subcode of C(m; k + 2g − 1) given by
(38)
k
X
def
ai gi , (a1 , a2 , . . . , ak ) ∈ M } .
C(m; k + 2g − 1 | M ) = {(f (P1 ), f (P2 ), . . . , f (PN )) : f =
i=1

Decoding. To decode, we first establish the equation (35) and solve this equation to
find the subspace of possible first k coefficients f0 , f1 , . . . , fk−1 in the local expansion of
Pk
the function f =
i=1 ai gi at P . The following claim implies that the message tuple
(a1 , a2 , . . . , ak ) belongs to this subspace.
Lemma 9.10. The first k coefficients f0 , f1 , . . . , fk−1 of the local expansion of f =
Pk
i=1 ai gi at P equal a1 , a2 , . . . , ak .

P
j
Proof. Since gi has local expansion T i−1 + ∞
j=k λij T , it is clear that the local expansion
Pk−1
P
∞
i
j
of f is
i=0 ai+1 T +
j=k aj+1 T for some ak+1 , ak+2 , . . . in Fq m . Thus the first k
coefficients of the local expansion of f are a1 , a2 , . . . , ak .

Combining Lemmas 9.7, 9.8, and 9.10, and recalling the choice of D in (32), we get
the following.
Corollary 9.11. For the code C(m; k + 2g − 1 | Fkqm ), we can find an (s − 1, m)-ultra
periodic subspace of Fmk
that includes all messages whose encoding differs from a received
q
3s+1
s
in
at
most
word y ∈ FN
m
q
s+1 (N − k) − s+1 g positions.

38

V. GURUSWAMI AND C. XING

9.3. Decoding the codes from the Garcia-Stichtenoth tower. Let r be a prime
power and let q = r 2 . For e > 2, let Ke be the function field Fq (x1 , x2 , . . . , xe ) given by
Garcia-Stichtenoth tower (16).
Put F = Ke and Fm = Fqm · Ke . The encoding and decoding is almost identical to
the algebraic geometric code described in the previous section except here we use P∞ for
local expansion.
Encoding. As in Lemma 9.9, we can find a set of functions {h1 , h2 , . . . , hk } of Lm ((k +
2ge −1)P∞ ) such that the k×k matrix A formed by taking the ith row of A to be the first k
coefficients in the expansion (40) for hi at P∞ is non-singular (note that in this case, the local expansion starts from T −(k+2ge−1) , while in the previous subsection the local expansion
starts from T 0 ). Furthermore, after some elementary row operations
 on A,Pwe may assume

j for
−(k+2g
e −1)
that, for 1 6 i 6 k, the function hi has expansion T
T i−1 + ∞
j=k λij T
some λij ∈ Fqm .

We encode a message k-tuple (a1 , a2 , . . . , ak ) ∈ Fkqm by the codeword (f (P1 ), f (P2 ), . . . ,
P
f (PN )) where f = ki=1 ai hi , and P1 , P2 , . . . , PN are arbitrary Fq -rational points (other
than P∞ ) in the function field. The block length N can be any integer satisfying k 6 N 6
r e−1 (r 2 − r). As in Section 9.2, for any subset M ⊆ Fkqm , we can consider the subcode
obtained by only encoding tuples in M :
(39)
k
X
def
ai hi , (a1 , a2 , . . . , ak ) ∈ M } .
CGS (m; k+2ge −1 | M ) = {(f (P1 ), f (P2 ), . . . , f (PN )) : f =
i=1

Computing the code. Note that an explicit specification of the code simply requires
the evaluations of the basis functions h1 , h2 , . . . , hk at the N rational points. One can find
a basis of Lm (lP∞ ) along with its evaluations at the rational points using poly(N, l, m)
operations over Fq [23] (see also [10, Sec. 7]). We can also compute the first l coefficients
of the local expansion of the basis functions at P∞ using poly(l, m) operations over Fq
as described in Section 4. The computation of the hi ’s following the method of Lemma
9.9 only requires elementary matrix operations, so we can compute its evaluations at the
rational points also in polynomial time.
List decoding. In order to list decode, we can find a functional equation A0 + A1 f +
s−1
exactly as in Lemma 9.7. To solve for f from this equation, we
A2 f σ + · · · + As f σ
consider the local expansions of the message functions f at P∞ . Let T ∈ Ke be a local
expansion of P∞ and suppose that a function f ∈ Lm ((k+2ge −1)P∞ ) has a local expansion
at P∞
(40)

f = T −(k+2ge −1)

∞
X

fj T j

j=0

Pk
for some fj ∈ Fqm . As in Lemma 9.10, if f =
i=1 ai hi , then the top k coefficients
f0 , f1 , . . . , fk−1 in the above local expansion equal a1 , a2 , . . . , ak . Thus we can determine
such f uniquely by finding f0 , f1 , . . . , fk−1 . The following lemma is similar to Lemma 9.8
and shows that the coefficients belong to an ultra-periodic subspace.
Lemma 9.12. Suppose f ∈ Lm ((k + 2ge − 1)P∞ ) satisfies the equation
A0 + A1 f + A2 f σ + · · · + As f σ

s−1

=0

AG CODES & NEAR-OPTIMAL LIST DECODING

39

when at least one Ai is nonzero. Then the possible first k coefficients (f0 , f1 , . . . , fk−1 )
of f ’s local expansion (40) at P∞ belong to an (s − 1, m)-ultra periodic affine subspace of
Fkm
q .
Proof. Let u = min{νP∞ (Ai ) : i = 1, 2, . . . , s} (so that −u is the maximum number of
poles any Ai , 1 6 i 6 s, has at P∞ ). Then it is clear that u > −D and νP∞ (A0 ) >
u − (k + 2ge − 1). Each Ai has a local expansion at P∞ :
A0 = T

u−(k+2ge −1)

∞
X

j

a0,j T ;

and Ai = T

u

∞
X

ai,j T j for i = 1, 2, . . . , s.

j=0

j=0

i

Assume that at P∞ , the function f has a local expansion (36). Then f σ has a local
expansion at P as follows
∞
X
i
i
fjq T j .
fσ =
j=0

For l = 0, 1, . . . , define the linearized polynomial

Bl (X) := a1,l X + a2,l X q + · · · + as,l X q

s−1

From the definition of u, one knows that B0 (X) is nonzero. Equating the coefficient of
s−1
to equal 0 gives us the condition
T d+u−(k+2ge −1) in A0 + A1 f + A2 f σ + · · · + As f σ
a0,d + Bd (f0 ) + Bd−1 (f1 ) + · · · + B0 (fd ) = 0 .

Arguing as in Lemma 9.8 this constrains (f0 , f1 , . . . , fk−1 ) to belong to an (s − 1, m)-ultra

periodic subspaces of Fmk
q .
Similar to Corollary 9.11, we can now conclude the following:
Corollary 9.13. The code CGS (m; k + 2ge − 1 | Fkqm ) can be list decoded from up to
s
3s+1
s+1 (N − k) − s+1 ge errors, pinning down the messages to an (s − 1, m)-ultra periodic
mk
subspace of Fq .
We conclude the section by incorporating the trade-off between ge and N , and stating
the rate vs. list decoding radius trade-off offered by these codes, in a form convenient for
improvements to the list size using subspace evasive sets and subspace designs (see Section
10). The claim about the number of possible solution subspaces follows since the subspace
is determined by A0 , A1 , . . . , As , and for our choice of parameter D, there are at most
q O(mN ) choices of those.
Theorem 9.14. Let q be the even power of a prime. Let 1 6 s 6 m be integers, and
√
let R ∈ (0, 1). Then for infinitely many N (all integers of the form q e/2 ( q − 1)), there
is a deterministic polynomial time construction of an Fqm -linear code GS(q,m) [N, k] of
block length N and dimension k = R · N that can be list decoded in poly(N, m, log q) time
s
O(mN ) possible
(N − k) − √3N
from s+1
q−1 errors, pinning down the messages to one of q
(s − 1, m)-ultra periodic Fq -affine subspaces of Fmk
q .

10. Subspace designs
The linear-algebraic list decoder discussed in the previous sections pins down the
coefficients of the message to a periodic subspace. This subspace has linear dimension, so
we need to restrict the coefficients further so that the subspace can be pruned to a small
list of solutions. We already saw, in Section 6, an approach using h.s.e. sets to prune the

40

V. GURUSWAMI AND C. XING

periodic subspace to a small list. In this section, we will develop an alternate approach
based a special collection of subspaces, which we call a subspace design, for pruning the
periodic subspaces. This will lead to explicit constructions with somewhat larger list size.
We begin with the definition of the central object of study in this section, subspace
designs.
Definition 15. Let Λ be a positive integer, and q a prime power. For positive integers
Λ
r < Λ and d, an (r, d)-subspace design in FΛ
q is a collection of subspaces of Fq such that
for every r-dimensional subspace W ⊂ FΛ
q , we have
X
(41)
dim(W ∩ H) 6 d .
H∈H

The cardinality of a subspace design H is the number of subspaces in its collection, i.e.,
|H|. If all subspaces in H have the same dimension t, then we refer to t as the dimension
of the subspace design H.
Note that the condition (41) in particular implies for every r-dimensional subspace W , at
most d of the subspaces in an (r, d)-subspace design non-trivially intersect it. This weaker
property is called a “weak subspace design” in [8] which gave explicit constructions of
subspace designs following our original definition in [17]. For our list decoding application,
the stronger property (41) is required. In particular, the usefulness of subspace designs
defined above, in the context of pruning periodic subspaces, is captured by the following
key lemma.
Lemma 10.1 (Periodic subspaces intersected with a subspace design). Suppose H1 , H2 ,
. . . , Hb are subspaces in an (r, d)-subspace design in FΛ
q , and T is a (r, Λ, b)-periodic affine
subspace of FΛb
with
underlying
subspace
S.
Then
the
set
q
T = {(f1 , f2 , . . . , fb ) ∈ T | fj ∈ Hj for j = 1, 2, . . . , b}

is an affine subspace of FΛb
q of dimension at most d. Also, the underlying subspace of T
def

is contained in S = S ∩ (H1 × H2 × · · · × Hb ).

Proof. It is clear that T is an affine subspace, since its elements are restricted by the set
of linear constraints defining T and the Hj ’s. Also, the difference of two elements in T
is contained in both the subspaces S and (H1 × H2 × · · · × Hb ), which implies that the
underlying subspace of T is contained in S.
We will prove the bound on dimension by proving that |T | 6 q d . To prove this, we
will imagine the elements of T as the leaves of a tree of depth b, with the nodes at level j
representing the possible projections of T onto the first j blocks. The root of this tree has
as children the elements of the affine space proj[1,Λ] (T ) ∩ H1 . Let W be the subspace of FΛ
q
of dimension at most r associated with the periodic subspace T (in the sense of Definition
1). Note that the underlying subspace of the affine space proj[1,Λ] (T ) ∩ H1 is contained in
the subspace W ∩ H1 .

Continuing this argument, the children of an element a ∈ FjΛ
q at level j will be a
followed by the possible extensions of a to the (j + 1)’th block, given by
{proj[j∆+1,(j+1)∆] (x) | x ∈ T and projj∆ (x) = a} ∩ Hj+1 .

The periodic property of T and the fact that Hj+1 is a subspace implies that the possible
extensions of a are given by a coset of a subspace of W ∩ Hj+1 . Thus the nodes at level
j have degree at most q dim(W ∩Hj+1 ) for j = 0, 1, . . . , b − 1. Since the Hj ’s belong to an

AG CODES & NEAR-OPTIMAL LIST DECODING

41

P
(r, d)-subspace design we have bj=1 dim(W ∩ Hj ) 6 d. Therefore, the tree has at most
q d leaves, which is also an upper bound on |T |.

10.1. Constructing subspace designs. We now turn to the construction of subspace
designs of large size and dimension. We first analyze the performance of a random collection of subspaces.
Lemma 10.2. Let η > 0 and q be a prime power. Let r, Λ be integers Λ > 8/η and
r 6 ηΛ/2. Consider a collection H of subspaces of FΛ
q obtained by picking, independently
at random, q ηΛ/8 subspaces of FΛ
of
dimension
(1
−
η)Λ each. Then, with probability at
q
−Λr
least 1 − q
, H is an (r, 8r/η)-subspace design.
Proof. Let ℓ = 8r/η, and let M = q ηΛ/8 denote the number of randomly chosen subspaces.9
Let H1 , H2 , . . . , HM be the subspaces in the collection H. Fix a subspace W of FΛ
q of
dimension r. Fix a tuple of non-negative integers (a1 , a2 , . . . , aM ) summing up to ℓ. For
each j ∈ {1, 2, . . . , M }, the probability that dim(W ∩Hj ) > aj is at most q raj q −ηΛaj . Since
the choice of the different Hj ’s are independent, the probability that dim(W ∩ Hj ) > aj
for every j is at most q (r−ηΛ)ℓ 6 q −ηΛℓ/2 (the last step uses r 6 ηΛ/2).
A union bound over the at most q Λr subspaces W ⊂ FΛ
q of dimension r, and the at

ℓ+M
ℓ
2ℓ
most ℓ 6 (M +ℓ) 6 M choices of the tuples (a1 , a2 , . . . , aM ), we get the probability
that H is not an (r, ℓ)-subspace design is at most
q Λr · q −ηΛℓ/2 · (q ηΛ/8 )2ℓ = q Λr · q −ηΛℓ/4 6 q −Λr

where the last step uses ℓ > 8r/η.



Note that given a collection H of subspaces, one can deterministically check if it is
O(Λr) |H| time by doing a brute-force check of all ran (r, d)-subspace design in FΛ
q in q
P
Λ
dimensional subspaces W of Fq , and for each computing H∈H dim(W ∩H) using |H|ΛO(1)
operations over Fq . Thus the above lemma gives a q O(Λr) time Las Vegas construction of
an (r, d)-subspace design with many subspaces each of large dimension (1 − η)m.
Lemma 10.3. For parameters η, r, Λ as in Lemma 10.2, for any b 6 q ηΛ/8 , one can
compute an (r, 8r/η)-subspace design in FΛ
q of dimension (1 − η)Λ and cardinality b in
O(Λr)
q
Las Vegas time.
As noted in the conference version [17] of this paper, the construction can be derandomized using the method of conditional expectations to successively find good subspaces
Hi to add to the subspace design. However, as each step involves searching over all
O(Λ2 ) even for con(1 − η)Λ-dimensional subspaces of FΛ
q , the construction time would be q
structing subspace designs with few subspaces. For our application to reducing the list size
for long algebraic-geometric codes (either folded or with rational points in a subfield), we
will need subspace designs for ambient dimension Λ growing at least logarithmically in the
2
code length. The q O(Λ ) complexity will thus lead to a quasi-polynomial code construction
time, as claimed in the conference version [17]. In fact, even the Las Vegas construction
time of q O(Λr) will be super-polynomial for the parameters used in the construction.
The question of explicit (polynomial time) constructions of subspace designs naturally arose following [17] and was addressed in the follow-up work by Guruswami and
Kopparty [8], who proved the following.
9For simplicity, we ignore the floor and ceil signs in defining integers; these can be easily incorporated.

42

V. GURUSWAMI AND C. XING

Theorem 10.4 (Explicit subspace designs [8]). For every η > 0, integers r, Λ with r 6
ηΛ/4, and prime powers q satisfying q ηΛ/(2r) > 2r/η, for any b 6 q ηΛ/(4r) , there exists
an explicit (r, r 2 /η)-subspace design of cardinality b and dimension (1 − η)Λ, that can be
constructed deterministically in time poly(b, q) time. In the case when q > Λ, one can
explicitly construct an (r, 2r/η)-subspace design with the same parameters.
We note a couple of senses in which the parameters offered by the explicit construction are weaker than those guaranteed by the probabilistic construction. First, the total
intersection dimension (41) is r 2 /η rather than O(r/η) (except when q is large). This is
because, for small fields, their construction yields only a weak subspace design, incurring
a factor r loss when passing to a subspace design. Second, the number of subspaces in the
design is smaller, roughly q Ω(ηΛ/r) instead of q Ω(ηΛ) . Finally, there is a modest restriction
the field size q, and we need to pick r, Λ suitably to allow for fixed q. Fortunately, all
these restrictions can be accommodated for our application. We remark that a recent
construction of subspace designs based on cyclotomic function fields [18] gives an analog of Theorem 10.4 over any field Fq with an (r, O(r logq Λ/η))-subspace design; for our
application, however, the r 2 /η bound is more useful as r ≪ Λ, and we can’t afford the
dependence on Λ in the bound.
Let us now record a construction of subspaces with low-dimensional intersection with
every periodic subspace based on the above subspace designs. This form will be convenient
for later use in pre-coding Reed-Solomon codes.
Theorem 10.5. Let η ∈ (0, 1) and q be a prime power, and r, Λ, b be integers such that
r 6 ηΛ/4 and b < q. Then, one can construct a subspace V of FbΛ
q of dimension at least
O(Λ)
(1 − η)bΛ in either deterministic q
time: For every (r, Λ, b)-periodic subspace T ⊂ FbΛ
q ,
V ∩ T is an Fq -affine subspace of dimension at most 2r/η.
Proof. We will take V = H1 × H2 × · · · Hb where the Hi ’s belong to a (r, 2r/η)-subspace
design in F∆
q of cardinality b and dimension at least (1−η)Λ as guaranteed by Theorem 10.4
when q > Λ. er Clearly dim(V ) > (1 − η)bΛ since each Hi has dimension at least (1 − η)Λ.
The claim now follows using Lemma 10.1.

10.2. Cascaded subspace designs. In preparation for our results about algebraic-geometric
codes, whose block length ≫ q m is much larger than the possible size of subspace designs
in Fm
q , we now formalize a notion that combines several “levels” of subspace designs. The
definition might seem somewhat technical, but it has a natural use in our application to
list-size reduction for AG codes. Note that there is no “consistency” requirement between
subspace designs at different levels other than the lengths and cardinalities matching.
Definition 16 (Subspace designs of increasing length). Let l be a positive integer. For
positive integers r0 6 r1 6 · · · 6 rl and m0 6 m1 6 · · · 6 ml such that mι−1 |mι for
1 6 ι 6 l, an (r0 , r1 , . . . , rl )-cascaded subspace design with length-vector (m0 , m1 , . . . , ml )
and dimension vector (d0 , d1 , . . . , dl−1 ) is a collection of l subspace designs, specifically an
(rι−1 , rι )-subspace design in Fqmι−1 of cardinality mι /mι−1 and dimension dι−1 for each
ι = 1, 2, . . . , l.
Note that the l = 1 case of the above definition corresponds to an (r0 , r1 )-subspace
0 of dimension d
design in Fm
0 and cardinality m1 /m0 . In Lemma 10.1, we used the
q
subspace H1 × H2 × · · · × Hb based on a subspace design consisting of the Hi ’s to prune a
periodic subspace. Generalizing this, we now define a subspace associated with a cascaded
subspace design based on the subspace designs comprising it.

AG CODES & NEAR-OPTIMAL LIST DECODING

43

Definition 17 (Canonical subspace). Let M be a cascaded subspace design with lengthvector (m0 , m1 , . . . , ml ) such that the ι’th subspace design in M has subspaces
(ι)

(ι)

(ι)

ι−1
H1 , H2 , · · · , Hmι /mι−1 ⊂ Fm
, for 1 6 ι 6 l .
q

The canonical subspace associated with such a cascaded subspace design, denoted U (M),
is a subspace of Fqml defined as follows:
l
A vector x ∈ Fm
q belongs to U (M) if and only if for every ι ∈ {1, 2, . . . , l},
each of the mι -sized blocks of x given proj[jmι +1,(j+1)mι ] (x) for 0 6 j <

(ι)

(ι)

(ι)

ml /mι ) belongs H1 × H2 × · · · × Hmι /mι−1 .
In other words, we apply the construction of Lemma 10.1 for (disjoint) intervals of
length mι at each level ι ∈ {1, 2, . . . , l}.

The following simple fact, which follows by counting number of linear constraints imposed,
gives a lower bound on the dimension of a canonical subspace.
Observation 10.6. For a cascaded subspace design M as above, if the ι’th subspace design
has dimension at least (1 −ξι−1 )mι−1 for 1 6 ι 6 l, then the dimension of the canonical
subspace U (M) is at least 1 − (ξ0 + ξ1 + · · · + ξl−1 ) ml .
The following is the crucial claim about pruning ultra-periodic subspaces using (the
canonical subspace of) a cascaded subspace design. It generalizes Lemma 10.1 which
corresponds to the l = 1 case.

Lemma 10.7. Suppose M is a (r0 , r1 , . . . , rl )-cascaded subspace design with length-vector
l
(m0 , m1 , . . . , ml ). Let T be a (r0 , m0 )-ultra periodic affine subspace of Fm
q . Then the
dimension of the affine space T ∩ U (M) is at most rl .
Proof. The idea will be to apply Lemma 10.1 inductively, for increasing periods m0 , m1 ,
. . . , ml−1 . Since T is (r0 , m0 )-ultra periodic, it is (r0 , m0 )-periodic and ((m1 /m0 )r0 , m1 )periodic. Using this together with Lemma 10.1, it follows that
(1)

(1)

(1)

l
T ∩ {x ∈ Fm
q | proj[jm1 +1,(j+1)m1 ] (x) ∈ H1 × H2 × · · · × Hm1 /m0 for 0 6 j < ml /m1 }

is an affine subspace that is (r1 , m1 )-periodic. Continuing this argument, the affine sub(ι)
(ι)
(ι)
space of T formed by restricting each mι -block to belong to H1 × H2 × · · · × Hmι /mι−1
l
for 1 6 ι 6 j is (rj , mj )-periodic. For j = l, we get the intersection T ∩ U (M) ⊂ Fm
q
will be (rl , ml )-periodic, which simply means that it is an rl -dimensional affine subspace
l

of Fm
q .
We conclude this section by constructing a canonical subspace that has low-dimensional
intersection with ultra-periodic subspaces based on the explicit subspace designs of Theorem 10.4. This statement will be used in Section 11.2 for pre-coding algebraic-geometric
codes based on the Garcia-Stichtenoth tower.
Theorem 10.8. Let q > 4 be a prime power. Let η ∈ (0, 1) and integers Λ, r > 2 satisfy
Λ > crη −1 log(r/η) for a large enough (absolute) constant c > 0. For all large enough
multiples κ of Λ, we can construct a subspace U of Fκq of dimension at least (1 − η)κ
such that for every (r, Λ)-ultra periodic affine subspace T ⊂ Fκq , the dimension of the
O(log∗ κ)

affine subspace U ∩ T is at most (r/η)2
deterministically in poly(κ, q) time.

. The subspace U can be constructed in

44

V. GURUSWAMI AND C. XING

Proof. We will take U to the canonical subspace U (M) of an appropriate cascaded subspace design M. To this end, given our work so far, the main remaining task is to pick
η
the parameters of M carefully. Let ηι = 4·2
ι for ι = 0, 1, 2, . . . .
√

Let m0 = Λ, m1 = m0 · ⌊(r/η)c/4 ⌋, and for ι > 0, mι+1 = mι · q ⌈ mι ⌉ . Let r0 = r,
and for ι > 0, rι+1 = ⌈rι2 /ηι ⌉. For this choice of parameters, one can verify that (i)
rι 6 ηι mι /4, and (ii) q ηι mι /(4rι ) > mι+1 /mι for all ι > 0. Indeed, to verify the first
condition by induction, one only needs to check that mι+1 > m2ι , which is true for ι = 0
√
for a large enough choice of c, and for ι > 1, mι+1 in fact grows exponentially in mι . For
the second condition, for ι = 0 it follows from our assumption that Λ > crη −1 log(r/η).
√
For ι > 1, it is implied by rι /ηι ≪ mι /4, which is true for ι = 1 for large enough c,
and for ι > 1 by induction since rι /ηι grows quadratically in each step, whereas mι grows
exponentially.
We can therefore conclude by Theorem 10.4 that we can construct a (rι , rι+1 )ι
subspace design of cardinality mι+1 /mι in Fm
q of dimension (1 − ηι )mι .

Pick l to the smallest integer so that ml−1 > (logq κ)2 . Since m0 = Λ > 2 and
√
mι+1 > q mι for 1 6 ι < l, it is easy to see that that l 6 O(log∗ κ). Redefine ml−1
to equal m′l−1 which is the smallest multiple of ml−2 that is at least (logq κ)2 . Since
ml−2 < (logq κ)2 , we have (logq κ)2 6 m′l−1 < 2(logq κ)2 . We also redefine ml to equal the
largest multiple m′l of m′l−1 that is at most κ. This implies κ − m′l < m′l−1 . Note that
√ ′
√
m′l−1 6 ml−2 q ⌈ ml−2 ⌉ and m′l 6 q ml−1 . For notational simplicity, let us re-denote m′l−1
and m′l by ml−1 and ml .
Thus for these parameters, we can construct an (r0 , r1 , . . . , rl )-cascaded subspace design Ml with length-vector (m0 , m1 , . . . , ml ) and dimension-vector (d0 , d1 , . . . , dl−1 ) where
dι > (1 − η/2ι+2 )mι .
The construction time for subspace designs guaranteed by Theorem 10.4 implies that
Ml can be constructed in poly(ml , q) time. We define the desired subspace U ⊂ Fκq as
l
U (Ml ) × 0κ−ml , i.e., U consists of the vectors in the canonical subspace U (Ml ) ⊂ Fm
q
padded with κ − ml zeroes at the end. By Observation 10.6, the dimension of U is at least
!
l−1
X
η
ml > (1 − η/2)ml > (1 − η/2)(κ − ml−1 )
1−
ι
4
·
2
ι=0
> (1 − η/2)κ − 2(logq κ)2 > (1 − η)κ

for large enough κ. This proves that the subspace U has dimension at least (1 − η)κ, and
can be constructed deterministically in poly(q, κ) time.
It remains to prove the claimed intersection property with ultra-periodic subspaces.
Let T be an arbitrary (r, Λ)-ultra periodic affine subspace of Fκq . By Lemma 10.7,
l of dimension at most r . Clearly, the
projml (T ) ∩ U (M) is an affine subspace of Fm
l
q
same dimension bound also holds for T ∩ U since the last κ − ml coordinates for vectors
in U are set to 0. The proof is complete by noting that for our choice of parameters,
l

rl 6 (2r/η)2 and l 6 O(log∗ κ).
11. Good list decodable subcodes of RS and AG codes
We now combine our code constructions in Section 9 with a pre-coding step that
restricts coefficients to belong to a subspace design, and thereby obtain subcodes that are
list decodable with smaller list-size in polynomial time.

AG CODES & NEAR-OPTIMAL LIST DECODING

45

11.1. Reed-Solomon codes. We begin with the case of Reed-Solomon codes. For a finite
field Fq , constant ε > 0, integers n, k, m, s satisfying 1 6 k < n 6 q and 1 6 s 6 εm/12, we
will define subcodes of RS(q,m) [n, k]. Below for a polynomial f ∈ Fqm [X] with k coefficients
f0 , f1 , . . . , fk−1 , we denote by f0 , f1 , . . . , fk−1 the representation of these coefficients as
vectors in Fm
q by fixing some Fq -basis of Fq m .
c of RS(q,m) [n, k] consisting of the encodings of f ∈ Fqm [X] such
Define the subcode RS
guaranteed by Theorem 10.5, when
that (f0 , f1 , . . . , fk−1 ) ∈ V for a subspace V ⊆ Fmk
q
applied with the parameter choices
Λ = m;

b = k;

r = s − 1;

η=ε.

c is an Fq -linear code over the alphabet Fqm of rate (1 − ε)k/n, and it can be
Note that RS
2
constructed in deterministic q O(m ) time, or Las Vegas q O(ms) time.10
Theorem 11.1. Given an input string y ∈ Fnqm , a basis of an affine subspace of dimension
at most O(s/ε) that includes all codewords of the above subcode within Hamming distance
s
s+1 (n − k) from y can be found in deterministic poly(n, log q, m) time.

Proof. By Lemma 9.4, we can compute the (s − 1, m, k)-periodic subspace T of messages
s
whose Reed-Solomon encodings can be within Hamming distance s+1
(n − k) from y.
By Theorem 10.5, the intersection T ∩ V is is an affine subspace over Fq of dimension
d = O(s/ε). Since both steps involve only basic linear algebra, they can be accomplished

using poly(n, m) operations over Fq .
By picking s = Θ(1/ε) and m = Θ(1/ε2 ) in the above construction, we can conclude
the following.
Corollary 11.2. For every R ∈ (0, 1) and ε > 0, and all large enough integers n < q
with q a prime power, one can construct a rate R Fq -linear subcode of a Reed-Solomon
code of length n over Fqm , such that the code can be (i) encoded in (n/ε)O(1) time and
(ii) list decoded from a fraction (1 − ε)(1 − R) of errors in (n/ε)O(1) time, outputting a
subspace over Fq of dimension O(1/ε2 ) including all close-by codewords. The code can be
constructed deterministically in poly(q) time.
We note that the above list decoding guarantee is in fact weaker than what is achieved
for folded Reed-Solomon codes in [14], where the codewords were pinned down to a dimension O(1/ε) subspace. We can improve the list size above to poly(1/ε) using pseudorandom
subspace-evasive sets as in [14], or to exp(ε−O(1) ) using the explicit subspace-evasive sets
from [1]. The main point of the above result is not the parameters but that an explicit
subcode of RS codes has optimal list decoding radius with polynomial complexity.
11.2. Subcodes of Garcia-Stichtenoth codes. We now pre-code the codes constructed
in Section 9.3. For a finite field Fq , constant ε > 0, and integers s, m satisfying 1 6 s 6
O(εm/ log(1/ε)) and m > Ω(1/ε2 ), we will define subcodes of GS(q,m) [N, k] guaranteed
by Theorem 9.14. Note that messages space of this code can be identified with Fmk
q .
d of GS(q,m) [N, k] consisting of the encodings of a subspace
Define the subcode GS
mk
U ⊆ Fq guaranteed by Theorem 10.8, when applied with the parameter choices
(42)

η = ε;

r = s − 1;

Λ = m;

κ = km .

10It can also be constructed in Monte Carlo (q/ε)O(1) time by randomly picking subspaces for the
subspace design used to construct V in Theorem 10.5.

46

V. GURUSWAMI AND C. XING

d is an Fq -linear code over the alphabet Fqm of rate (1 − ε)k/N . Also, it can
Note that GS
be constructed in poly(k, m, q) time by virtue of the construction complexity of U .

Lemma 11.3. Given an input string y ∈ FN
q m , a basis of an affine subspace of dimension
at most
O(log ∗ (km)
(s/ε)2
that includes all codewords of the above subcode within Hamming distance
√
3N/( q − 1) from y can be found in deterministic poly(n, log q, m) time.

s
s+1 (N

− k) −

Proof. By Theorem 9.14, we can compute the (s − 1, m)-ultra periodic subspace T of
√
s
(N − k) − 3N/( q − 1)
messages whose encodings can be within Hamming distance s+1
from y. By Theorem 10.8, for the above choice of parameters (42), the intersection T ∩ U
O(log ∗ (km)
. Since both steps involve only
is is an affine subspace over Fq of dimension (s/ε)2
basic linear algebra, they can be accomplished using poly(N, m) operations over Fq . 
By taking q = Θ(1/ε2 ), and choosing s = Θ(1/ε) and m = Θ(ε−2 log(1/ε)) in the
above lemma, we conclude the following main result concerning the explicit construction
of codes list decodable up to the Singleton bound.
Theorem 11.4 (Main deterministic code construction). For every R ∈ (0, 1) and ε > 0,
there is a deterministic polynomial time constructible family of error-correcting codes of
rate R over an alphabet of size exp(O(ε−2 log2 (1/ε))) that can be list decoded in polynomialtime from a fraction (1
 − R − ε) of errors, outputting a list of size at most
∗
exp1/ε exp1/ε (exp(O(log N ))) , where N is block length of the code.
References
[1] Zeev Dvir and Shachar Lovett, Subspace evasive sets, Proceedings of the 44th Symposium on Theory
of Computing Conference (STOC), 2012, pp. 351–358.
[2] Peter Elias, Error-correcting codes for list decoding, IEEE Transactions on Information Theory 37
(1991), 5–12.
[3] Michael A. Forbes and Venkatesan Guruswami, Dimension expanders via rank condensers, 19th International Workshop on Randomization and Computation (RANDOM), 2015, pp. 800–814.
[4] Arnaldo Garcia and Henning Stichtenoth, A tower of Artin-Schreier extensions of function fields
attaining the Drinfeld-Vlădut bound, Inventiones Mathematicae 121 (1995), 211–222.
[5]
, On the asymptotic behavior of some towers of function fields over finite fields, Journal of
Number Theory 61 (1996), no. 2, 248–273.
[6] Venkatesan Guruswami, Cyclotomic function fields, Artin-Frobenius automorphisms, and list errorcorrection with optimal rate, Algebra and Number Theory 4 (2010), no. 4, 433–463.
[7]
, Linear-algebraic list decoding of folded Reed-Solomon codes, Proceedings of the 26th IEEE
Conference on Computational Complexity, June 2011.
[8] Venkatesan Guruswami and Swastik Kopparty, Explicit subspace designs, Combinatorica 36 (2016),
no. 2, 161–185, Preliminary version in FOCS 2013.
[9] Venkatesan Guruswami and Srivatsan Narayanan, Combinatorial limitations of average-radius listdecoding, IEEE Transactions on Information Theory 60 (2014), no. 10, 5827–5842.
[10] Venkatesan Guruswami and Anindya Patthak, Correlated Algebraic-Geometric codes: Improved list
decoding over bounded alphabets, Mathematics of Computation 77 (2008), no. 261, 447–473.
[11] Venkatesan Guruswami and Atri Rudra, Explicit codes achieving list decoding capacity: Errorcorrection with optimal redundancy, IEEE Transactions on Information Theory 54 (2008), no. 1,
135–150.
[12]
, Better binary list decodable codes via multilevel concatenation, IEEE Trans. Information
Theory 55 (2009), no. 1, 19–26.
[13] Venkatesan Guruswami and Madhu Sudan, Improved decoding of Reed-Solomon and Algebraicgeometric codes, IEEE Transactions on Information Theory 45 (1999), no. 6, 1757–1767.

AG CODES & NEAR-OPTIMAL LIST DECODING

47

[14] Venkatesan Guruswami and Carol Wang, Linear-algebraic list decoding for variants of reed-solomon
codes, IEEE Transactions on Information Theory 59 (2013), no. 6, 3257–3268.
[15] Venkatesan Guruswami, Carol Wang, and Chaoping Xing, Explicit list-decodable rank-metric and
subspace codes via subspace designs, IEEE Trans. Information Theory 62 (2016), no. 5, 2707–2718.
[16] Venkatesan Guruswami and Chaoping Xing, Folded codes from function field towers and improved
optimal rate list decoding, Proceedings of the 44th Symposium on Theory of Computing Conference
(STOC), 2012, pp. 339–350.
[17]
, List decoding Reed-Solomon, algebraic-geometric, and Gabidulin subcodes up to the Singleton
bound, Proceedings of the ACM Symposium on Theory of Computing Conference (STOC), 2013,
pp. 843–852.
[18] Venkatesan Guruswami, Chaoping Xing, and Chen Yuan, Subspace designs based on algebraic function
fields, 44th International Colloquium on Automata, Languages, and Programming (ICALP), 2017,
pp. 86:1–86:10.
[19] Swastik Kopparty, Noga Ron-Zewi, and Shubhangi Saraf, Personal communication, 2017.
[20] Harald Niederreiter and Chaoping Xing, Rational points on curves over finite fields–theory and applications, Cambridge University Press, 2001.
[21] Farzad Parvaresh and Alexander Vardy, Correcting errors beyond the Guruswami-Sudan radius in
polynomial time, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer
Science, 2005, pp. 285–294.
[22] Ba-Zhong Shen, A Justesen construction of binary concatanated codes that asymptotically meet the
Zyablov bound for low rate, IEEE Transactions on Information Theory 39 (1993), 239–242.
[23] Kenneth Shum, Ilia Aleshnikov, P. Vijay Kumar, Henning Stichtenoth, and Vinay Deolalikar, A
low-complexity algorithm for the construction of algebraic-geometric codes better than the GilbertVarshamov bound, IEEE Transactions on Information Theory 47 (2001), no. 6, 2225–2241.
[24] Joseph H. Silverman, The arithmetic of elliptic curves, Springer, New York, 1985.
[25] Henning Stichtenoth, Algebraic function fields and codes, Universitext, Springer-Verlag, Berlin, 1993.
[26] Madhu Sudan, Decoding of Reed-Solomon codes beyond the error-correction bound, Journal of Complexity 13 (1997), no. 1, 180–193.
[27] Salil Vadhan, Pseudorandomness, Foundations and Trends in Theoretical Computer Science 7(1-3):
1-336 (2012)
Computer Science Department, Carnegie Mellon University, Pittsburgh, USA.
E-mail address: venkatg@cs.cmu.edu
Division of Mathematical Sciences, School of Physical & Mathematical Sciences, Nanyang
Technological University, Singapore.
E-mail address: xingcp@ntu.edu.sg

