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-H*_{q}(r)-e
(where *0<r<1-1/q*, *e>0* and
*H*_{q}(.) 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-H*_{q}(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(e*^{1/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-H*_{q}(r)-e.

** Versions**