A Lower Bound on List Size for List Decoding
Venkatesan Guruswami, Salil Vadhan · IEEE Transactions on Information Theory · 2010
Aq-ary error-correcting codeC⊆ {1,2,...,q}nis said to be list decodable to radius ρ with list sizeLif every Hamming ball of radius ρ contains at mostLcodewords ofC. We prove that in order for aq-ary code to be list-decodable up to radius (1-1/q)(1- ε)n, we must haveL= Ω(1/ ε2) . Specifically, we prove that there exists a constantcq> 0 and a functionfqsuch that for small enough ε > 0, ifCis list-decodable to radius (1-1/q)(1- ε)nwith list sizecq/ ε2, thenChas at mostfq( ε) codewords, independent ofn. This result is asymptotically tight (treatingqas a constant), since such codes with an exponential (inn) number of codewords are known for list sizeL=O(1/ ε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.