AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets
Omar Alrabiah, Venkatesan Guruswami, Ray Li · Society for Industrial and Applied Mathematics eBooks · 2024
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.