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}(rho )- varepsilon $ (where $00$ is small enough and $H_{q}(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 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-H_{q}(rho )- varepsilon $.