All reports by Author Srivatsan Narayanan:

__
TR12-017
| 1st March 2012
__

Venkatesan Guruswami, Srivatsan Narayanan#### Combinatorial limitations of a strong form of list decoding

Revisions: 1

Venkatesan Guruswami, Srivatsan Narayanan

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)$ ... more >>>