  List-decoding and list-recovery are important generalizations of unique
decoding that received considerable attention over the years. However, the
optimal trade-off among list-decoding (resp. list-recovery) radius, list size,
and the code rate are not fully understood in both problems. This paper takes a
step towards this direction when the list size is a given constant and the
alphabet size is large (as a function of the code length). We prove a new
Singleton-type upper bound for list-decodable codes, which improves upon the
previously known bound by roughly a factor of $1/L$, where $L$ is the list
size. We also prove a Singleton-type upper bound for list-recoverable codes,
which is to the best of our knowledge, the first such bound for list-recovery.
We apply these results to obtain new lower bounds that are optimal up to a
multiplicative constant on the list size for list-decodable and
list-recoverable codes with rates approaching capacity.
  Moreover, we show that list-decodable \emph{nonlinear} codes can strictly
outperform list-decodable linear codes. More precisely, we show that there is a
gap for a wide range of parameters, which grows fast with the alphabet size,
between the size of the largest list-decodable nonlinear code and the size of
the largest list-decodable linear codes. This is achieved by a novel connection
between list-decoding and the notion of sparse hypergraphs in extremal
combinatorics. We remark that such a gap is not known to exist in the problem
of unique decoding.
  Lastly, we show that list-decodability or recoverability of codes implies in
some sense good unique decodability.
