Combinatorial limitations of a strong form of list decoding

We prove the following results concerning the combinatorics of list decoding, motivated by the exponential gap between the known upper bound (of O(1/γ)) and lower bound (of Ωp(log(1/γ))) for the list-size needed to decode up to radius p with rate γ away from capacity, i.e., 1 − h(p) − γ (here p ∈ (0, 1/2) and γ> 0). • We prove that in any binary code C ⊆ {0, 1}n of rate 1 − h(p) − γ, there must exist a set L ⊂ C of Ωp(1/√γ) codewords such that the average distance of the points in L from their centroid is at most pn. In other words, there must exist Ωp(1/ γ) codewords with low “average radius”. The motivation for this result is that it gives a list-size lower bound for a strong notion of list decoding; this strong form has been implicitly been used in the previous negative results for list decoding. (The usual notion of list decoding corresponds to replacing average radius by the minimum radius of an enclosing Hamming ball.) The remaining results are for the usual notion of list decoding: • We give a short simple proof, over all fixed alphabets, of the above-mentioned Ωp(log(1/γ)) lower bound due to Blinovsky. • We show that one cannot improve the Ωp(log(1/γ)) 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 Ωp(log(1/γ)) list size lower bound). On a positive note, our Ωp(1/ γ) lower bound for the strong form of list decoding does circumvent this barrier. • We show a “reverse connection ” showing that constant-weight codes for list decoding imply general codes for list decoding with higher rate. This shows that the best possible list-size, as a function of the gap γ of the rate to the capacity limit, is the same up to constant factors for both constant-weight codes and general codes. • We give simple second moment based proofs that w.h.p. a list-size of Ωp(1/γ) is needed for list decoding random codes from errors as well as erasures, at rates which are γ away from the corresponding capacities. For random linear codes, the corresponding list size bounds are Ωp(1/γ) for errors and exp(Ωp(1/γ)) for erasures