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), Theoretical Computer Science, TCS.ORCID iD: 0000-0002-5379-345X
2011 (English)In: IEEE Transactions on Information Theory, ISSN 0018-9448, Vol. 57, no 2, 718-725 p.Article in journal (Refereed) Published
Abstract [en]

The list-decodability of random linear codes is shown to be as good as that of general random codes. Specifically, for every fixed finite field, Gamma(q), p is an element of (0, 1 - 1/q) and epsilon > 0, it is proved that with high probability a random linear code C in F-q(n) of rate (1 - H-q(p) - epsilon) can be list decoded from a fraction p of errors with lists of size at most O(1/epsilon). This also answers a basic open question concerning the existence of highly list-decodable linear codes, showing that a list-size of O(1/epsilon) suffices to have rate within epsilon of the information-theoretically optimal rate of 1 - H-q(p). The best previously known list-size bound was q(O(1/epsilon)) (except in the q = 2 case where a list-size bound of O(1/epsilon) was known). The main technical ingredient in the proof is a strong upper bound on the probability that l random vectors chosen from a Hamming ball centered at the origin have too many (more than Omega(l)) vectors from their linear span also belong to the ball.

Place, publisher, year, edition, pages
2011. Vol. 57, no 2, 718-725 p.
Keyword [en]
Hamming bound, linear codes, list decoding, probabilistic method, random coding
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-31347DOI: 10.1109/TIT.2010.2095170ISI: 000286514200010ScopusID: 2-s2.0-79251490359OAI: diva2:404462

QC 20110317

Available from: 2011-03-17 Created: 2011-03-14 Last updated: 2013-04-05Bibliographically 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
Theoretical Computer Science, TCS
In the same journal
IEEE Transactions on Information Theory
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: 41 hits
ReferencesLink to record
Permanent link

Direct link