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), 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, Published 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.
Series
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
Identifiers
URN: urn:nbn:se:kth:diva-31519DOI: 10.1145/1806689.1806747Scopus ID: 2-s2.0-77954695916ISBN: 978-1-60558-817-9 (print)OAI: oai:DiVA.org:kth-31519DiVA: diva2:404467
Conference
42nd ACM Symposium on Theory of Computing, STOC 2010; Cambridge, MA; 5 June 2010 through 8 June 2010
Note

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

Authority records BETA

Håstad, Johan

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

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 37 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