AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets

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 L L+1 (1-R) (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 L 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 rate R algebraic-geometry (AG) codes over an alphabet of size O(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 the Lth generalized Singleton bound requires alphabet size 2 ΩL,R(n) . Previously this was only known only for L = 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(O L (1/ε))-sized alphabets, can be list-of-L decoded up to error fraction L L+1 (1 -R -ε).

• This paper was presented in part at SODA 2024.