Atri Rudra

Limits to List Decoding Random Codes

Abstract : It has been known since [Zyablov and Pinsker 1982] that a random q-ary code of rate 1-Hq(r)-e (where 0<r<1-1/q, e>0 and Hq(.) is the q-ary entropy function) with high probability is an (r,1/e)-list decodable code. (That is, every Hamming ball of radius at most rn has at most 1/e codewords in it.) In this paper we prove the ``converse" result. In particular, we prove that for every 0<r<1-1/q, a random code of rate 1-Hq(r)-e, with high probability, is not an (r,L)-list decodable code for any L≤ c/e, where c is a constant that depends only on r and q. We also prove a similar lower bound for random linear codes.

Previously, such a tight lower bound on the list size was only known for the case when r≥ 1-1/q-O(e1/2) [Guruswami and Vadhan, 2005]. For binary codes a lower bound is known for all 0<r<1/2, though the lower bound is asymptotically weaker than our bound [Blinovsky, 1986]. These results however are not subsumed by ours as they hold for arbitrary codes of rate 1-Hq(r)-e.