A Lower Bound on List Size for List Decoding
A q-ary error-correcting code C subset of {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 q-ary code to be list-decodable up to radius (1 - 1/q)(1 - epsilon)n, we must have L = ohm(1/epsilon(2)). Specifically we prove that there exists a constant c(q) > 0 and a function f(q) such that for small enough epsilon > 0, if C is list-decodable to radius (1 - 1/q)(1 - epsilon)n with list size c(q)/epsilon(2) then C has at most f(q)(epsilon) 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/epsilon(2)). A result similar to ours is implicit in Blinovsky (Problems of Information Transmission, 1986) for the binary (q = 2) case. Our proof is simpler and works for all alphabet sizes, and provides more intuition for why the lower bound arises.
list decoding bounds on codes probabilistic method random codes randomness extractors