  We study certain combinatorial aspects of list-decoding, motivated by the
exponential gap between the known upper bound (of $O(1/\gamma)$) and lower
bound (of $\Omega_p(\log (1/\gamma))$) for the list-size needed to decode up to
radius $p$ with rate $\gamma$ away from capacity, i.e., $1-\h(p)-\gamma$ (here
$p\in (0,1/2)$ and $\gamma > 0$). Our main result is the following:
  We prove that in any binary code $C \subseteq \{0,1\}^n$ of rate
$1-\h(p)-\gamma$, there must exist a set $\mathcal{L} \subset C$ of
$\Omega_p(1/\sqrt{\gamma})$ codewords such that the average distance of the
points in $\mathcal{L}$ from their centroid is at most $pn$. In other words,
there must exist $\Omega_p(1/\sqrt{\gamma})$ codewords with low "average
radius." The standard notion of list-decoding corresponds to working with the
maximum distance of a collection of codewords from a center instead of average
distance. The average-radius form is in itself quite natural and is implied by
the classical Johnson bound.
  The remaining results concern the standard notion of list-decoding, and help
clarify the combinatorial landscape of list-decoding:
  1. We give a short simple proof, over all fixed alphabets, of the
above-mentioned $\Omega_p(\log (\gamma))$ lower bound. Earlier, this bound
followed from a complicated, more general result of Blinovsky.
  2. We show that one {\em cannot} improve the $\Omega_p(\log (1/\gamma))$
lower bound via techniques based on identifying the zero-rate regime for list
decoding of constant-weight codes.
  3. We show a "reverse connection" showing that constant-weight codes for list
decoding imply general codes for list decoding with higher rate.
  4. We give simple second moment based proofs of tight (up to constant
factors) lower bounds on the list-size needed for list decoding random codes
and random linear codes from errors as well as erasures.
