Limits to list decoding of Random codes

It has been known since [Zyablov and Pinsker, 1982] that a random q-ary code of rate 1-H_q(ρ )- ε (where 0 < ρ < 1-1/q, ε > 0 is small enough and H_q(̇) is the q-ary entropy function) with high probability is a (ρ, 1/ε )-list decodable code (that is, every Hamming ball of radius at most ρn has at most 1/ε codewords in it). In this paper, the "converse" result is proven. In particular, it is proven that for every 0 < ρ < 1-1/q, a random code of rate 1-H_q(ρ)- ε, with high probability, is not a (ρ, L)-list decodable code for any L ≤ c/ε, where c is some constant that depends only on ρ and q. A similar lower bound is also shown for random linear codes. Previously, such a tight lower bound on the list size was only known for the case when ρ ≥ 1-1/q-O(√ε) for small enough ε < 0 [Blinovsky, 1986, 2005, 2008; Guruswami and Vadhan, 2005]. A lower bound is known for all constant 0 < ρ < 1-1/q independent of ε, though the lower bound is asymptotically weaker than our bound [Blinovsky, 1986, 2005, 2008]. These results, however, are not subsumed by ours as these other results hold for arbitrary codes of rate 1-H_q(ρ)- ε.