Guruswami, VenkatesanVadhan, Salil2014-11-212010Guruswami, Venkatesan, and Salil Vadhan. 2010. “A Lower Bound on List Size for List Decoding.” IEEE Trans. Inform. Theory 56, no. 11: 5681–5688. doi:10.1007/s11127-010-9610-0.0048-5829http://nrs.harvard.edu/urn-3:HUL.InstRepos:13413333A q-ary error-correcting code C ⊆ {1,2,...,q}n is said to be list decodable to radius ρ with list size L if every Hamming ball of radius ρ 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- ε)n, we must have L = Ω(1/ ε2) . Specifically, we prove that there exists a constant cq > 0 and a function fq such that for small enough ε > 0, if C is list-decodable to radius (1-1/q)(1- ε)n with list size cq/ ε2, then C has at most fq( ε) 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/ ε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.en-USBounds on codeslist decodingprobabilistic methodrandom codesrandomness extractorsJournal Article2014-11-2110.1007/s11127-010-9610-0