A lower bound on list size for list decoding

Citation:

Guruswami, Venkatesan, and Salil Vadhan. “A lower bound on list size for list decoding.” IEEE Transactions on Information Theory 56, no. 11 (2010): 5681-5688.
 RANDOM2005.pdf 0 bytes

Abstract:

Version History: Preliminary version published in RANDOM '05 (https://link.springer.com/chapter/10.1007/11538462_27) and attached as RANDOM2005.pdf.

q-ary error-correcting code $$C ⊆ \{1,2,...,q\}^n$$ is said to be list decodable to radius $$\rho$$ 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 $$c_q >0$$ and a function $$f_q$$ such that for small enough $$ε > 0$$, if C is list-decodable to radius$$(1–1/q)(1–ε)n$$with list size $$c_q /ε^2$$, then C has at most $$f q (ε)$$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 [Bli] for the binary $$(q=2)$$ case. Our proof works for all alphabet sizes, and is technically and conceptually simpler.

Publisher's Version

Last updated on 06/03/2020