Randomly punctured Reed–Solomon codes achieve list-decoding capacity over linear-sized fields

The techniques in our paper have already been influential. In follow-up work, Brakensiek, Dhar, Gopi, and Zhang [BDG⁺23b] used our argument to prove that Algebraic Geometry (AG) codes achieve list-decoding capacity over constant-sized alphbaets. They prove this by combining our techniques with a generalized GM-MDS theorem, proved by Brakensiek, Dhar, Gopi [BDG23a].

For positive integers $t$, let $[t]$ denote the set $\{1,2,\dots,t\}$. The Hamming distance $d(x,y)$ between two vectors $x,y\in\mathbb{F}_{q}^{n}$ is the number of indices $i$ where $x_{i}\neq y_{i}$. For a finite field $\mathbb{F}_{q}$, we follow the standard notation that $\mathbb{F}_{q}[X_{1},\dots,X_{n}]$ denotes the ring of multivariate polynomials with variables $X_{1},\dots,X_{n}$ over $\mathbb{F}_{q}$, and $\mathbb{F}_{q}(X_{1},\dots,X_{n})$ denotes the field of fractions of the polynomial ring $\mathbb{F}_{q}[X_{1},\dots,X_{n}]$. By abuse of notation, we let $X_{\leq i}$ or $X_{[i]}$ to denote the sequence $X_{1},\dots,X_{i}$, and we let, for example, $X_{\leq i}=\alpha_{\leq i}$ to denote $X_{1}=\alpha_{1},X_{2}=\alpha_{2},\dots,X_{i}=\alpha_{i}$. Given a matrix $M$ over the field of fractions $\mathbb{F}_{q}(X_{1},\dots,X_{n})$ and field elements $\alpha_{1},\dots,\alpha_{i}\in\mathbb{F}_{q}$, let $M(X_{\leq i}=\alpha_{\leq i})$ denote the matrix over $\mathbb{F}_{q}(X_{i+1},X_{i+2},\dots,X_{n})$ obtained by setting $X_{\leq i}=\alpha_{\leq i}$ in $M$.

In this work, we maintain a hypergraph perspective of the list-decoding problem, which was introduced in [GLS⁺22]. We describe a bad list-decoding instance with a hypergraph where the $L+1$ bad codewords identify the vertices and the $n$ evaluation points identify the hyperedges (Definition 2.1). While prior works described a bad list-decoding instance by $L+1$ sets indicating the agreements of the codewords with the received word, this hypergraph perspective gives us several advantages:

1. 1.

   The constraints imposed by a bad list-decoding configuration yield a hypergraph that is weakly-partition-connected. This is a natural notion of hypergraph connectivity, which is well-studied in combinatorics [FKK03b, FKK03a, Kir03] and optimization [JMS03, FK09, Fra11, CX18], and which generalizes a well-known notion ($k$-partition-connectivity) for graphs [NW61, Tut61].⁵⁵5The notion of weakly-partition-connected sits between two other well-studied notions: $k$-partition-connected implies $k$-weakly-partition-connected implies $k$-edge-connected [Kir03]. Each of these three notions generalizes an analogous notion on graphs. On graphs, $k$-partition-connected and $k$-weakly-partition-connected are equivalent. This connection allows us to have more compact notation, definitions, and lemma statements.

2. 2.

   Because we work with weakly-partition-connected hypergraphs, we save a factor of $L$ in Lemma 2.14 compared to the analogous lemma in [GZ23]. This allows us to improve the constant factor in alphabet size for Reed–Solomon codes from $2^{O(L^{2}/\varepsilon)}$ in [GZ23] to $2^{O(L/\varepsilon)}$ in Theorem 1.1.

3. 3.

   For similar reasons, for random linear codes, the hypergraph perspective saves a factor of $L$ in the alphabet size exponent, improving from $2^{O(L^{2}/\varepsilon)}$ to $2^{O(L/\varepsilon)}$ in Theorem 1.3.

4. 4.

   With the hypergraph perspective, we can give a new presentation of the results in [BGM23] and more directly connect the list-decoding problem to the GM-MDS theorem [DSY14, Lov18, YH19], as the heavy-lifting in the combinatorics is done using known results on hypergraph orientations. This is done in Appendix A.

A hypergraph $\mathcal{H}=(V,\mathcal{E})$ is given by a set of vertices $V$ and a set $\mathcal{E}$ of (hyper)edges, which are subsets of the vertices $V$. In this work, all hypergraphs have labeled edges, meaning we enumerate our edges $e_{i}$ by distinct indices $i$ from some set, typically $[n]$, in which case we may also think of $\mathcal{E}$ as a tuple $(e_{1},\dots,e_{n})$. Throughout this paper, the vertex set $V$ is typically $[t]$ for some positive integer $t$. The weight of a hyperedge $e$ is $\operatorname*{wt}(e)\stackrel{{\scriptstyle\rm def}}{{=}}\max(0,|e|-1)$, and the weight of a set of hyperedges $\mathcal{E}$ is simply $\operatorname*{wt}(\mathcal{E})\stackrel{{\scriptstyle\rm def}}{{=}}\sum_{e\in\mathcal{E}}{\operatorname*{wt}(e)}$.

All hypergraphs that we will consider in this work are agreement hypergraphs for a bad list-decoding configuration. See Figure 1 for an illustration.

A key property of hypergraphs that we are concerned with is weak-partition-connectivity.

To give some intuition for weak partition connectivity, we state two of its combinatorial implications. First, if a graph is $k$-weakly-partition-connected, then it is $k$-edge-connected [Kir03], which, by the Hypergraph Menger’s (Max-Flow-Min-Cut) theorem [Kir03, Theorem 1.11], equivalently means that every pair of vertices has $k$ edge-disjoint (hyper)paths between them.⁶⁶6In general the converse is not true. Second, suppose we replace every hyperedge $e$ with an arbitrary spanning tree of its vertices (which we effectively do in Definition 2.6). The resulting (non-hyper)graph is $k$-partition-connected,⁷⁷7In (non-hyper)graphs, $k$-partition-connectivity and $k$-weak-partition-connectivity are equivalent. which, by the Nash-Williams-Tutte Tree-Packing theorem [NW61, Tut61], equivalently means there are $k$ edge-disjoint spanning trees (this connection was used in [GLS⁺22]).

The key reason we consider weak-partition-connectivity is that a bad list-decoding configuration yields a $k$-weakly-partition-connected agreement hypergraph.

Lemma 2.3 follows from the following result about weakly-particion-connected hypergraphs

As in [GZ23], we work with the reduced intersection matrix, though our proof should work essentially the same with a different matrix called the (non-reduced) intersection matrix, which was considered in [ST20, GLS⁺22, BGM23].

Reduced intersection matrices arise by encoding all agreements from a bad list-decoding configuration into linear constraints on the message symbols (the polynomial coefficients). These constraints are placed into one matrix that we call the reduced intersection matrix. The following lemma implies that, if every reduced intersection matrix arising from a possible bad list-decoding configuration has full column rank when $X_{1}=\alpha_{1},\dots,X_{n}=\alpha_{n}$, the corresponding Reed–Solomon code is list-decodable.

The following theorem shows that reduced intersection matrices of $k$-weakly-partition-connected hypergraphs are nonsingular when viewed as a matrix over $\mathbb{F}_{q}(X_{1},\dots,X_{n})$. This was essentially conjectured by Shangguan and Tamo [ST20] and essentially established by Brakensiek, Gopi, and Makam [BGM23], who conjectured and showed, respectively, nonsingularity of the (non-reduced) intersection matrix under similar conditions. By the same union bound argument as in [ST20, Theorem 5.8], Theorem 2.11 already implies list-decodability of Reed–Solomon codes up to the generalized Singleton bound over exponentially large fields sizes, which is [BGM23, Theorem 1.5]. For completeness, and to demonstrate how the hypergraph perspective more directly connects the list-decoding problem to the GM-MDS theorem, we include a proof of Theorem 2.11 in Appendix A.

As in [GZ23], we consider row deletions from the reduced intersection matrix. The goal of this section is to establish Lemma 2.14, that the full-column-rank-ness of reduced intersection matrices are robust to row deletions.

The next lemma appears in a weaker form in [GZ23]. It roughly says that, given a reduced intersection matrix $\mathsf{RIM}_{\mathcal{H}}$ with some constant factor “slack” in the combinatorial constraints, we can omit a constant fraction of the rows without compromising the full-column-rank-ness of the matrix. Our version of this lemma saves roughly a factor of $t\sim L$ compared to the analogous lemma [GZ23, Lemma 3.11]. The reason is that the $k$-weakly-partition-connected condition is more robust to these row deletions (by a factor of roughly $t$) than the condition in [GZ23]. As such, our proof is also more direct.

By Lemma 2.8 and Lemma 2.3, every bad list-decoding configuration admits a weakly-partition-connected agreement hypergraph whose reduced intersection matrix does not have full column rank. Thus, to prove Theorem 1.1, it suffices to show that, with high probability, every such reduced intersection matrix has full column rank. The main technical lemma for this section is the one stated below. Our main result, Theorem 1.1, follows by applying Lemma 2.3 and Lemma 2.8 with Lemma 3.1, and taking a union bound over all $\sum_{t=2}^{L+1}{2^{tn}}$ possible agreement hypergraphs.

At the highest level, the proof of Lemma 3.1 follows the same outline as [GZ23]. For every sequence of evaluation points $(\alpha_{1},\dots,\alpha_{n})\in\mathbb{F}_{q}^{n}$ for which $\mathsf{RIM}_{\mathcal{H}}$ does not have full column rank, we show that there is a certificate $(i_{1},\dots,i_{r})\in[n]^{r}$ consisting of distinct indices in $[n]$ (Lemma 3.8), which intuitively “attests” to the failure of the matrix $\mathsf{RIM}_{\mathcal{H}}$ to be full column rank. We then show that, for any certificate $(i_{1},\dots,i_{r})$, the probability that $(\alpha_{1},\dots,\alpha_{n})$ has certificate $(i_{1},\dots,i_{r})$ is exponentially small. (More precisely, it will at most be $(\frac{(t-1)k}{q-n})^{r}$. See Corollary 3.12). We then show that there are not too many certificates (Corollary 3.10), and then union bound over the number of possible certificates to obtain the desired result (Lemma 3.1).

Our argument differs from [GZ23] in how we choose our certificates. The argument of [GZ23] allowed for up to $n^{r}$ certificates. Our argument instead only needs $\binom{n}{r}2^{tr}$ many certificates, which is much smaller when $r=\Omega(n)$ (the parameter regime of interest here) and overall allows us to save a factor of $n$ in the alphabet size. Our savings comes from leveraging that there are at most $2^{t}$ different “types” of hyperedges (see Remark 2.9), and thus at most $2^{t}$ different types of variables $X_{i}$ in the reduced intersection matrix $\mathsf{RIM}_{\mathcal{H}}$. This observation was alluded to in [GZ23].⁸⁸8Guo and Zhang [GZ23] write “It is possible that achieving an alphabet size linear in n would require establishing and exploiting other properties of intersection matrices or reduced intersection matrices, such as an appropriate notion of exchangeability.” We found this prediction to be insightful and true. With this observation in mind, we assume, without loss of generality, that the edges of $\mathcal{H}$ are ordered by their respective type (we can relabel the edges of $\mathcal{H}$, which effectively permutes the rows of $\mathsf{RIM}_{\mathcal{H}}$).

Our method of generating a certificate $(i_{1},\dots,i_{r})$ for the evaluation sequence $(\alpha_{1},\dots,\alpha_{n})$ (Algorithm 2) is similar to that of [GZ23] at a high level—with each certificate $i_{1},\dots,i_{r}$, we associate a sequence of $(t-1)k\times(t-1)k$ submatrices $M_{1},\dots,M_{r}$ of $\mathsf{RIM}_{\mathcal{H}}$ (Algorithm 1) that are entirely specified by $i_{1},\dots,i_{r}$ as follows: since evaluating $X_{[n]}=\alpha_{[n]}$ forces $\mathsf{RIM}_{\mathcal{H}}$ to not be full rank, then so will all of its $(t-1)k\times(t-1)k$ submatrices. Thus if we sequentially ’reveal’ $X_{1}=\alpha_{1},X_{2}=\alpha_{2},\dots$, then at some point, $M_{j}$ becomes singular exactly when we set $X_{i_{j}}=\alpha_{i_{j}}$ — in fact, $i_{j}$ is defined as such, so that we select $M_{1},i_{1},M_{2},i_{2},\dots,$ in that order, but we emphasize that $M_{j}$ can be computed from $i_{1},\dots,i_{j-1}$ without knowing $\alpha_{1},\dots,\alpha_{n}$. Conditioned on $M_{j}$ being non-singular with $X_{1}=\alpha_{1},\dots,X_{i_{j}-1}=\alpha_{i_{j}-1}$, the probability that $M_{j}$ becomes singular when setting $X_{i_{j}}=\alpha_{i_{j}}$ is at most $\frac{(t-1)k}{q-n}$: $\alpha_{i_{j}}$ is uniformly random over at least $q-n$ field elements, and the degree of $X_{i_{j}}$ in the determinant of $M_{j}$ is at most $(t-1)k$ (and the determinant is nonzero by definition). Running conditional probabilities in the correct order, we conclude that the probability that a particular certificate $i_{1},\dots,i_{r}$ is generated is at most $(\frac{(t-1)k}{q-n})^{r}$, just as in [GZ23].

Whereas [GZ23] pick any matrix $M_{j}$ that is obtained after removing the variables $X_{i_{1}},\ldots,X_{i_{j-1}}$, we do a more deliberate choice of matrices by leveraging the symmetries of $\mathsf{RIM}_{\mathcal{H}}$ (Remark 2.9). First, we ensure that we can keep a “bank” of $\Omega_{t}(r)$ unused variables of each of the $O_{t}(1)$ types. Then, starting with a full column rank submatrix $M$ of $\mathsf{RIM}_{\mathcal{H}}$ devoid of all variables in the “bank,” we start sequentially applying the evaluations $X_{1}=\alpha_{1},X_{2}=\alpha_{2},\ldots$. Whenever $M(X_{\leq i_{1}}=\alpha_{\leq i_{1}})$ turns singular, we find that the evaluation $X_{i_{1}}=\alpha_{i_{1}}$ is what ’caused’ it to become singular. We then go to the “bank” to find a variable $X_{i_{1}^{\prime}}$ of the same type as $X_{i_{1}}$ and “re-indeterminate” $M$ by replacing all instances of $X_{i_{1}}$ in $M$ with $X_{i_{1}^{\prime}}$. That way, we ensure that $M$ is, in a sense, “reused.” Furthermore, we ensure $i_{1}^{\prime}>i_{1}$, so that the matrix $M(X_{\leq i_{1}}=\alpha_{\leq i_{1}})$ is now nonsingular, so we can keep going. Of course, if we end up reaching the end (i.e. $M(X_{[n]}=\alpha_{[n]})$ is full column rank), then in fact, $\mathsf{RIM}_{\mathcal{H}}(X_{[n]}=\alpha_{[n]})$ is full column rank, and so the evaluations $(\alpha_{1},\ldots,\alpha_{n})$ were ‘good’ after all.