Computer Science – Information Theory
Scientific paper
2012-02-27
Computer Science
Information Theory
23 pages
Scientific paper
We prove the following results concerning the combinatorics of list decoding, motivated by the exponential gap between the known upper bound (of $O(1/\gamma)$) and lower bound (of $\Omega_p(\log (1/\gamma))$) for the list-size needed to decode up to radius $p$ with rate $\gamma$ away from capacity, i.e., $1-\h(p)-\gamma$ (here $p\in (0,1/2)$ and $\gamma > 0$). We prove that in any binary code $C \subseteq \{0,1\}^n$ of rate $1-\h(p)-\gamma$, there must exist a set $\mathcal{L} \subset C$ of $\Omega_p(1/\sqrt{\gamma})$ codewords such that the average distance of the points in $\mathcal{L}$ from their centroid is at most $pn$. In other words, there must exist $\Omega_p(1/\sqrt{\gamma})$ codewords with low "average radius". The motivation for this result is that it gives a list-size lower bound for a strong notion of list decoding which has been implicitly been used in the previous negative results for list decoding. (The usual notion of list decoding corresponds to replacing {\em average} radius by the {\em minimum} radius of an enclosing Hamming ball.) The remaining results are for the usual notion of list decoding: 1. We give a short simple proof, over all fixed alphabets, of the above-mentioned $\Omega_p(\log (1/\gamma))$ lower bound due to Blinovsky. 2. We show that one {\em cannot} improve the $\Omega_p(\log (1/\gamma))$ lower bound via techniques based on identifying the zero-rate regime for list decoding of constant-weight codes. 3. We show a "reverse connection" showing that constant-weight codes for list decoding imply general codes for list decoding with higher rate. 4. We give simple second moment based proofs of tight (up to constant factors) lower bounds on the list-size needed for list decoding random codes and random linear codes from errors as well as erasures.
Guruswami Venkatesan
Narayanan Srivatsan
No associations
LandOfFree
Combinatorial limitations of a strong form of list decoding does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Combinatorial limitations of a strong form of list decoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combinatorial limitations of a strong form of list decoding will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-605255