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 g-ary entropy function) with high probability is a (ρ, 1/ε) -list decodable code (that is, every Hamming ball of radius at most pn 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(ρ) - ε.