A simple, recently observed generalization of the classical Singleton bound to list-decoding asserts that rateRcodes are not list-decodable using list-sizeLbeyond an error fractionL/L+1 (1-R) (the Singleton bound being the case ofL= 1, i.e., unique decoding). We prove that in order to approach this bound for any fixedL> 1, one needs exponential alphabets. Specifically, for everyL> 1 andR∈ (0, 1), if a rateRcode can be list-of-Ldecoded up to error fractionL/L+1 (1 -R- ε), then its alphabet must have size at least exp(ΩL,R(1/ε)). This is in sharp contrast to the situation for unique decoding where certain families of rateRalgebraic-geometry (AG) codes over an alphabet of sizeO(1/ε2) are unique-decodable up to error fraction (1 -R- ε)/2. Our bounds hold even for subconstant ε ≥ 1/n, implying that any code exactly achieving theL-th generalized Singleton bound requires alphabet size 2ΩL,R(n). Previously this was only known only forL= 2 under the additional assumptions that the code is both linear and MDS. Our lower bound is tight up to constant factors in the exponent—with high probability random codes (or, as shown recently, even random linear codes) over exp(OL(1/ε))-sized alphabets, can be list-of-Ldecoded up to error fractionL/L+1 (1-R- ε).

We prove that a binary linear code of block length$n$that is locally correctable with 3 queries against a fraction$\delta > 0$of adversarial errors must have dimension at most$o_{\delta} ( >\log^{2}n$. log log$n$). This is almost tight in view of quadratic Reed-Muller codes being a 3-query locally correctable code (LCC) with dimension$\Theta^{-}(\log^{2}n)$. Our result improves, for the binary field case, the$O_{\delta}(\text{lo}\overline{\mathrm{g}}^{8}n)$bound obtained in the recent breakthrough of [1] (and the more recent improvement to$O_{\delta}(\log^{4}n)$for binary linear codes announced in [2]). Previous bounds for 3-query linear LCCs proceed by constructing a 2-query locally decodable code (LDC) from the 3-query linear LCC/LDC and applying the strong bounds known for the former. Our approach is more direct and proceeds by bounding the covering radius of the dual code, borrowing inspiration from [3]. That is, we show that if$x\rightarrow(v_{1}\cdot x,\ v_{2}\cdot x,\ \ldots,\ v_{n}\cdot x)$is an arbitrary encoding map$\mathbb{F}_{2}^{k}\rightarrow \mathbb{F}_{\underline{2}}^{n}$for the 3-query LCC, then all vectors in$\mathbb{F}_{2}^{k}$can be written as a$O_{\delta}(\log n)$-sparse linear com-bination of the$v_{i}{\prime}s$, which immediately implies$\overline{k}\leq\overline{O}_{\delta}((\log n)^{2})$. The proof of this fact proceeds by iteratively∼reducing the size of any arbitrary linear combination of at least$\Omega_{\delta}(\log n)$of the$v_{i}{\prime}s$. We achieve this using the recent breakthrough result of [4] on the existence of rainbow cycles in properly edge-colored graphs, applied to graphs capturing the linear dependencies underlying the local correction property.

A simple, recently observed generalization of the classical Singleton bound to list-decoding asserts that rate R codes are not list-decodable using list-size L beyond an error fraction (the Singleton bound being the case of L = 1, i.e., unique decoding). We prove that in order to approach this bound for any fixed L > 1, one needs exponential alphabets. Specifically, for every L > 1 and R ∈ (0,1), if a rate R code can be list-of-L decoded up to error fraction , then its alphabet must have size at least exp(ΩL,R(1/ɛ)). This is in sharp contrast to the situation for unique decoding where certain families of rate R algebraic-geometry (AG) codes over an alphabet of size O(1/ɛ2) are unique-decodable up to error fraction (1 — R — ɛ)/2.

Reed–Solomon codes are a classic family of error-correcting codes consisting of evaluations of low-degree polynomials over a finite field on some sequence of distinct field elements. They are widely known for their optimal unique-decoding capabilities, but their list-decoding capabilities are not fully understood. Given the prevalence of Reed-Solomon codes, a fundamental question in coding theory is determining if Reed–Solomon codes can optimally achieve list-decoding capacity. A recent breakthrough by Brakensiek, Gopi, and Makam, established that Reed–Solomon codes are combinatorially list-decodable all the way to capacity. However, their results hold for randomly-punctured Reed–Solomon codes over an exponentially large field size 2O(n), where n is the block length of the code. A natural question is whether Reed–Solomon codes can still achieve capacity over smaller fields. Recently, Guo and Zhang showed that Reed–Solomon codes are list-decodable to capacity with field size O(n2). We show that Reed–Solomon codes are list-decodable to capacity with linear field size O(n), which is optimal up to the constant factor. We also give evidence that the ratio between the alphabet size q and code length n cannot be bounded by an absolute constant. Our techniques also show that random linear codes are list-decodable up to (the alphabet-independent) capacity with optimal list-size O(1/ε) and near-optimal alphabet size 2O(1/ε2), where ε is the gap to capacity. As far as we are aware, list-decoding up to capacity with optimal list-size O(1/ε) was not known to be achievable with any linear code over a constant alphabet size (even non-constructively), and it was also not known to be achievable for random linear codes over any alphabet size. Our proofs are based on the ideas of Guo and Zhang, and we additionally exploit symmetries of reduced intersection matrices. With our proof, which maintains a hypergraph perspective of the list-decoding problem, we include an alternate presentation of ideas from Brakensiek, Gopi, and Makam that more directly connects the list-decoding problem to the GM-MDS theorem via a hypergraph orientation theorem.

A code C ∶ {0,1}k → {0,1}n is a q-locally decodable code (q-LDC) if one can recover any chosen bit bi of the message b ∈ {0,1}k with good confidence by randomly querying the encoding x = C(b) on at most q coordinates. Existing constructions of 2-LDCs achieve n = exp(O(k)), and lower bounds show that this is in fact tight. However, when q = 3, far less is known: the best constructions achieve n = exp(ko(1)), while the best known results only show a quadratic lower bound n ≥ Ω(k2/log(k)) on the blocklength.

We propose a framework to study the effect of local recovery requirements of codeword symbols on the dimension of linear codes, based on a combinatorial proxy that we call visible rank. The locality constraints of a linear code are stipulated by a matrix H of ⋆’s and 0’s (which we call a "stencil"), whose rows correspond to the local parity checks (with the ⋆’s indicating the support of the check). The visible rank of H is the largest r for which there is a r × r submatrix in H with a unique generalized diagonal of ⋆’s. The visible rank yields a field-independent combinatorial lower bound on the rank of H and thus the co-dimension of the code. We point out connections of the visible rank to other notions in the literature such as unique restricted graph matchings, matroids, spanoids, and min-rank. In particular, we prove a rank-nullity type theorem relating visible rank to the rank of an associated construct called symmetric spanoid, which was introduced by Dvir, Gopi, Gu, and Wigderson [Zeev Dvir et al., 2020]. Using this connection and a construction of appropriate stencils, we answer a question posed in [Zeev Dvir et al., 2020] and demonstrate that symmetric spanoid rank cannot improve the currently best known Õ(n^{(q-2)/(q-1)}) upper bound on the dimension of q-query locally correctable codes (LCCs) of length n. This also pins down the efficacy of visible rank as a proxy for the dimension of LCCs. We also study the t-Disjoint Repair Group Property (t-DRGP) of codes where each codeword symbol must belong to t disjoint check equations. It is known that linear codes with 2-DRGP must have co-dimension Ω(√n) (which is matched by a simple product code construction). We show that there are stencils corresponding to 2-DRGP with visible rank as small as O(log n). However, we show the second tensor of any 2-DRGP stencil has visible rank Ω(n), thus recovering the Ω(√n) lower bound for 2-DRGP. For q-LCC, however, the k'th tensor power for k ⩽ n^{o(1)} is unable to improve the Õ(n^{(q-2)/(q-1)}) upper bound on the dimension of q-LCCs by a polynomial factor.Inspired by this and as a notion of intrinsic interest, we define the notion of visible capacity of a stencil as the limiting visible rank of high tensor powers, analogous to Shannon capacity, and pose the question whether there can be large gaps between visible capacity and algebraic rank.

An$(n,k,\ell)$-vector MDS code over a field$\mathbb {F}$is a$\mathbb {F}$-linear subspace of$(\mathbb {F}^\ell)^{n}$of dimension$k\ell $, such that any$k$(vector) symbols of the codeword suffice to determine the remaining$r=n-k$(vector) symbols. The length$\ell $of each codeword symbol is called thesub-packetizationof the code. Such a code is called minimum storage regenerating (MSR), if any single symbol of a codeword can be recovered by downloading$\ell /r$field elements (which is known to be the minimum possible) from each of the other symbols. MSR codes are attractive for use in distributed storage systems, and by now a variety of ingenious constructions of MSR codes are available. However, they all suffer from exponentially large sub-packetization$\ell \gtrsim r^{k/r}$. Our main result is an almost tight lower bound showing that for an MSR code, one must have$\ell \geqslant \exp (\Omega (k/r))$. Previously, a lower bound of$\approx \exp (\sqrt {k/r})$, and a tight lower bound for a restricted class of “optimal access” MSR codes, were known.

An (n,k,ℓ)-vector MDS code is a F-linear subspace of (Fℓ)n (for some field F) of dimension kℓ, such that any k (vector) symbols of the codeword suffice to determine the remaining r=n−k (vector) symbols. The length ℓ of each codeword symbol is called the Sub-Packetization of the code. Such a code is called minimum storage regenerating (MSR), if any single symbol of a codeword can be recovered by downloading ℓ/r field elements (which is known to be the least possible) from each of the other symbols.