# A Lower Bound on List Size for List
Decoding

Venkatesan Guruswami
and Salil Vadhan

### Abstract

A q-ary error-correcting code C \subseteq {1,2,...,q}^n is said to be
list decodable to radius \rho with list size L if every Hamming ball of radius
\rho contains at most L codewords of C. We prove that in order for a q-ary code
to be list-decodable up to radius (1-1/q)(1-\eps)n, we must have L =
Omega(1/\eps^2). Specifically, we prove that there exists a constant c_q>0
and a function f_q such that for small enough \eps > 0, if C is
list-decodable to radius (1-1/q)(1-\eps)n with list size c_q/\eps^2, then C has
at most f_q(\eps) codewords, independent of n. This result is asymptotically
tight (treating q as a constant), since such codes with an exponential (in n)
number of codewords are known for list size L = O(1/\eps^2).

A result similar to ours is implicit in Blinovsky (1986) for the binary (q=2)
case. Our proof works for all alphabet sizes, and provides more intuition for
why the lower bound arises.

### Versions

- In
*Proceedings of the 8th
International Workshop on Randomization and Computation (RANDOM `05), * volume
3624 of Lecture Notes in Computer Science, pages 318-329. Springer-Verlag,
22-24 August 2005. [ps][pdf][Springer page]
- Revised full version, July
2008. [pdf]
- Minor revision, January 2010. [pdf]
*IEEE Transactions on Information Theory *56(11), pages 5681-5688, November 2010. [pdf][IEEE page]

[ back to
Salil Vadhan's research]