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-Hq(\rho )- \varepsilon (where 0< \rho < 1-1/q, \varepsilon >0 is small enough and Hq(\cdot ) is the q-ary entropy function) with high probability is a (\rho ,1/ \varepsilon )-list decodable code (that is, every Hamming ball of radius at most \rho n has at most 1/ \varepsilon codewords in it). In this paper, the “converse” result is proven. In particular, it is proven that for every 0< \rho < 1-1/q, a random code of rate 1-Hq(\rho )- \varepsilon , with high probability, is not a (\rho ,L)-list decodable code for any L \leqslant c\over \varepsilon , where c is some constant that depends only on \rho 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 \rho \geqslant 1-1/q-O(\sqrt \varepsilon ) for small enough \varepsilon >0 [Blinovsky, 1986, 2005, 2008; Guruswami and Vadhan, 2005]. A lower bound is known for all constant 0< \rho < 1-1/q independent of \varepsilon , 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-Hq(\rho )- \varepsilon . [ABSTRACT FROM PUBLISHER]