Limits to List Decoding of Random Codes
It has been known since [Zyablov and Pinsker, 1982] that a random 1 - H(q)(rho) - epsilon (where 0,   0 is small enough and H(q)(.) is the q-ary entropy function) with high probability is (rho, 1/epsilon)-list decodable code (that is, every Hamming ball of radius at most has at most 1/epsilon codewords in it). In this paper, the "converse" result is proven. In particular, it is proven that for every 0  = 1 - 1/q - O(root epsilon) for small enough epsilon > 0 [Blinovsky, 1986, 2005, 2008; Guruswami and Vadhan, 2005]. A lower bound is known for all constant 0 < rho < 1 - 1/q independent of epsilon, 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)(rho) - epsilon.
list decoding random codes lower bounds list size probabilistic method