Change search
ReferencesLink to record
Permanent link

Direct link
On the list-decodability of random linear codes
KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.ORCID iD: 0000-0002-5379-345X
2010 (English)In: Proceedings of the Annual ACM Symposium on Theory of Computing, 2010, 409-416 p.Conference paper (Refereed)
Abstract [en]

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
Keyword [en]
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
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-31519DOI: 10.1145/1806689.1806747ScopusID: 2-s2.0-77954695916ISBN: 978-1-60558-817-9OAI: diva2:404467
42nd ACM Symposium on Theory of Computing, STOC 2010; Cambridge, MA; 5 June 2010 through 8 June 2010

QC 20110317

Available from: 2011-03-17 Created: 2011-03-17 Last updated: 2012-09-25Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Håstad, Johan
By organisation
Numerical Analysis and Computer Science, NADA
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 24 hits
ReferencesLink to record
Permanent link

Direct link