On the list-decodability of random linear codes

DOI10.1145/1806689.1806747MaRDI QIDQ2875168zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Swastik Kopparty, Venkatesan Guruswami, Johan Hastad

Publication date 13 August 2014

Published in Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1001.1386

zbMATH Keywords

linear codeslist decoding capacitylist error-correctionprobabilistic method

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Decoding (94B35)

Abstract: For every fixed finite field $F_q$, $pin(0,1-1/q)$ and $epsilon>0$, we prove that with high probability a random subspace $C$ of $F_q^n$ of dimension $(1-H_q(p)-epsilon)n$ has the property that every Hamming ball of radius $pn$ has at most $O(1/epsilon)$ codewords. This answers a basic open question concerning the list-decodability of linear codes, showing that a list size of $O(1/epsilon)$ suffices to have rate within $epsilon$ of the "capacity" $1-H_q(p)$. Our result matches up to constant factors the list-size achieved by general random codes, and gives an exponential improvement over the best previously known list-size bound of $q^{O(1/epsilon)}$. The main technical ingredient in our proof is a strong upper bound on the probability that $ell$ random vectors chosen from a Hamming ball centered at the origin have too many (more than $Theta(ell)$) vectors from their linear span also belong to the ball.

Recommendations

• On the list decodability of random linear codes with large error rates
• Limits to List Decoding Random Codes
• Combinatorial bounds for list decoding
• Average-radius list-recoverability of random linear codes
• Two theorems on list decoding (extended abstract)

Cited in

(24)

• On the list decodability of self-orthogonal rank-metric codes
• Asymptotical properties of linear codes
• On list decoding of certain \(\mathbb{F}_q\)-linear codes
• Individual codewords
• Local list-decoding and testing of random linear codes from high error
• Local list-decoding and testing of random linear codes from high error
• It'll probably work out: improved list-decoding through random operations
• Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets
• Linear time encodable and list decodable codes
• Two theorems on list decoding (extended abstract)
• List Decoding of Biorthogonal Codes and the Hadamard Transform With Linear Complexity
• Average-radius list-recoverability of random linear codes
• Combinatorial bounds for list decoding
• Improved list-decodability of random linear binary codes
• Low-density parity-check codes achieve list-decoding capacity
• Every list-decodable code for high noise has abundant near-optimal rate puncturings
• Limits to List Decoding Random Codes
• Restricted isometry of Fourier matrices and list decodability of random linear codes
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• On the list decodability of random linear codes with large error rates
• Restricted isometry of Fourier matrices and list decodability of random linear codes
• Nearly optimal property preserving hashing
• Algorithms for the diverse-k-SAT problem: the geometry of satisfying assignments

This page was built for publication: On the list-decodability of random linear codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2875168)