Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, E-ISSN 1557-9654, 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 Sciences
Identifiers
URN: urn:nbn:se:kth:diva-31347DOI: 10.1109/TIT.2010.2095170ISI: 000286514200010Scopus ID: 2-s2.0-79251490359OAI: oai:DiVA.org:kth-31347DiVA: diva2:404462
Note

QC 20110317

Available from: 2011-03-17 Created: 2011-03-14 Last updated: 2018-01-12Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Håstad, Johan

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 Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 55 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf