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.
Versions