AG Codes Have No List-decoding Friends: Approaching the Generalized Singleton Bound Requires Exponential Alphabets

• Published in: IEEE transactions on information theory 2024-05, p.1-1
• Main Authors: Alrabiah, Omar, Guruswami, Venkatesan, Li, Ray
• Format: Article
• Language: English
• Subjects: Algebraic-geometric codes; Codes; Convergence; Decoding; Entropy; Exponential alphabets; Generalized Singleton bound; Hamming distances; Higher order MDS codes; Linear codes; Linearity; List-decoding
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2024.3405392

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 L -th 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 - ε).