Limits to List Decoding Random Codes

摘要

It has been known since [Zyablov and Pinsker 1982] that a random q-ary code of rate 1 - H_q(ρ)- ε (where 0 < p <1-1/q, ε > 0 and H_q(·) is the q-ary entropy function) with high probability is a (ρ, 1/ε)-list decodable code. (That is, every Hamming ball of radius at most pn has at most 1/ε codewords in it.) In this paper we prove the "converse" result. In particular, we prove that for every 0 < ρ < 1-1/q, a random code of rate 1 - H_q(ρ) - ε, with high probability, is not a (ρ, L)-list decodable code for any L ≤ c/ε, where c is a constant that depends only on ρ and q. We also prove a similar lower bound for random linear codes.