We consider the problem of list decoding from erasures. We establish lower and upper bounds on the rate of a (linear) code that can be list decoded with list size L when up to a fraction p of its symbols are adversarially erased. Our results show that in the limit of large L, the rate of such a code approaches the capacity (1-p) of the erasure channel. Such nicely list decodable codes are then used as inner codes in a suitable concatenation scheme to give a uniformly constructive family of asymptotically good binary linear codes of rate Ω(ε{sup}2/lg(1/ε)) that can be efficiently list decoded using lists of size O(1/ε) from up to a fraction (1-ε) of erasures. This improves previous results from [14] in this vein, which achieved a rate of Ω(ε{sup}3lg(1/ε)).
展开▼
