ECCC-Report TR09-013https://eccc.weizmann.ac.il/report/2009/013Comments and Revisions published for TR09-013en-usTue, 10 Feb 2009 15:22:23 +0200
Paper TR09-013
| Limits to List Decoding Random Codes |
Atri Rudra
https://eccc.weizmann.ac.il/report/2009/013It has been known since [Zyablov and Pinsker 1982] that a random $q$-ary code of rate $1-H_q(\rho)-\eps$ (where $0<\rho<1-1/q$, $\eps>0$ and $H_q(\cdot)$ is the $q$-ary entropy function) with high probability is a $(\rho,1/\eps)$-list decodable code. (That is, every Hamming ball of radius at most $\rho n$ has at most $1/\eps$ codewords in it.) In this paper we prove the ``converse" result. In particular, we prove that for \emph{every} $0<\rho<1-1/q$, a random code of rate $1-H_q(\rho)-\eps$, with high probability, is not a $(\rho,L)$-list decodable code for any $L\le \frac{c}{\eps}$, where $c$ is a constant that depends only on $\rho$ 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 $\rho\ge 1-1/q-O(\sqrt{\eps})$ [Guruswami and Vadhan, 2005]. For binary codes a lower bound is known for all $0<\rho<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(\rho)-\eps$.
Tue, 10 Feb 2009 15:22:23 +0200https://eccc.weizmann.ac.il/report/2009/013