On the list-decodability of random linear codes
2010 (English)In: Proceedings of the Annual ACM Symposium on Theory of Computing, 2010, 409-416 p.Conference paper (Refereed)
We show that the list-decodability of random linear codes is as good as that of general random codes. Specifically, for every fixed finite field double-struck Fq, p ∈ (0,1-1/q) and ε > 0, we prove that with high probability a random linear code C in double-struck F qn of rate (1-H-q(p)-ε) can be list decoded from a fraction p of errors with lists of size at most O(1/ε). This also answers a basic open question concerning the existence of highly list-decodable linear codes, showing that a list-size of O(1/ε) suffices to have rate within ε of the "list decoding capacity" 1-Hq(p). The best previously known list-size bound was qO(1/ε) (except in the q=2 case where a list-size bound of O(1/ε) was known). 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.
Place, publisher, year, edition, pages
2010. 409-416 p.
, ACM Symposium on the Theory of Computing. Annual Proceedings, ISSN 0737-8017
linear codes, list decoding capacity, list error-correction, probabilistic method, Finite fields, Hamming ball, High probability, Linear span, List decoding, Probabilistic methods, Random codes, Random linear codes, Random vectors, Upper Bound, Computation theory, Decoding
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-31519DOI: 10.1145/1806689.1806747ScopusID: 2-s2.0-77954695916ISBN: 978-1-60558-817-9OAI: oai:DiVA.org:kth-31519DiVA: diva2:404467
42nd ACM Symposium on Theory of Computing, STOC 2010; Cambridge, MA; 5 June 2010 through 8 June 2010
QC 201103172011-03-172011-03-172012-09-25Bibliographically approved