On the List-Decodability of Random Linear Codes

الأصل · EN

For every fixed finite field, p ∈ (0,1-1/q) and ε> 0, we prove that with high probability a random subspace C of ⁿ of dimension (1-Hq(p)-ε)n has the property that every Hamming ball of radius pn has at most O(1/ε) codewords. This answers a basic open question concerning the list-decodability of linear codes, showing that a list size of O(1/ε) suffices to have rate within ε of the "capacity" 1-Hq(p). Our result matches up to constant factors the list-size achieved by general random codes, and gives an exponential improvement over the best previously known list-size bound of qᵒ⁽¹/ε⁾. The main technical ingredient in our proof is a strong upper bound on the probability that ℓ random vectors chosen from a Hamming ball centered at the origin have too many (more than Θ(ℓ)) vectors from their linear span also belong to the ball.