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, ie, 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 …

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 $\tfrac {L}{L+ 1}(1-R) $(the Singleton bound being the case of $ L= 1$, ie, 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\in (0, 1) $, if a rate $ R $ code
can be list-of-$ L $ decoded up to error fraction $\tfrac {L}{L+ 1}(1-R-\varepsilon) $, then its …