  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 $\frac{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\in(0,1)$, if a rate $R$ code can be
list-of-$L$ decoded up to error fraction $\frac{L}{L+1} (1-R -\varepsilon)$,
then its alphabet must have size at least $\exp(\Omega_{L,R}(1/\varepsilon))$.
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/\varepsilon^2)$ are unique-decodable up to error fraction
$(1-R-\varepsilon)/2$. Our bounds hold even for subconstant $\varepsilon\ge
1/n$, implying that any code exactly achieving the $L$-th generalized Singleton
bound requires alphabet size $2^{\Omega_{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/\varepsilon))$-sized alphabets, can be list-of-$L$ decoded up to
error fraction $\frac{L}{L+1} (1-R -\varepsilon)$.
