Combinatorial Limitations of Average-Radius List-Decoding.

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 list decode up to error fraction \(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 that 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; for instance, the classical Johnson bound in fact implies average-radius list-decodability. The remaining results concern the standard notion of list-decoding, and help clarify the current state of affairs regarding combinatorial bounds for list-decoding as follows. First, we give a short simple proof, over all fixed alphabets, of the above-mentioned \(\Omega _{p}(\log (1/\gamma ))\) lower bound. Earlier, this bound followed from a complicated, more general result of Blinovsky. Second, we show that one 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 [this is a typical approach for negative results in coding theory, including the \(\Omega _{p} (\log (1/\gamma ))\) list-size lower bound]. On a positive note, our \(\Omega _{p}(1/\sqrt {\gamma })\) lower bound for average-radius list-decoding circumvents this barrier. Third, we exhibit a reverse connection between the existence of constant-weight and general codes for list-decoding, showing that the best possible list-size, as a function of the gap \(\gamma \) of the rate to the capacity limit, is the same up to constant factors for both constant-weight codes (with weight bounded away from \(p\) ) and general codes. Fourth, we give simple second moment-based proofs that w.h.p. a list-size of \(\Omega _{p} (1/\gamma )\) is needed for list-decoding random codes from errors as well as erasures. For random linear codes, the corresponding list-size bounds are \(\Omega _{p} (1/\gamma )\) for errors and \(\exp (\Omega _{p}(1/\gamma ))\) for erasures. [ABSTRACT FROM AUTHOR]