Limits to List Decoding Random Codes

DOI10.1007/978-3-642-02882-3_4MaRDI QIDQ5323045zbMATH OpenOpenAlexFDO

Authors Atri Rudra

Publication date 23 July 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02882-3_4

Mathematics Subject Classification ID

Bounds on codes (94B65) Decoding (94B35)

Recommendations

• On the list-decodability of random linear codes
• On the list decodability of random linear codes with large error rates
• Two theorems on list decoding (extended abstract)
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Combinatorial bounds for list decoding

Cites work

• scientific article; zbMATH DE number 3133919 (Why is no real title available?)
• scientific article; zbMATH DE number 3760081 (Why is no real title available?)
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• A Mathematical Theory of Communication
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Limits to List Decoding Random Codes
• List decoding of error-correcting codes. Winning thesis of the 2002 ACM Doctoral Dissertation Competition

Cited in

(18)

• scientific article; zbMATH DE number 4162826 (Why is no real title available?)
• Any code of which we cannot think is good
• Limits to List Decoding Random Codes
• Explicit list-decodable codes with optimal rate for computationally bounded channels
• On the list decodability of random linear codes with large error rates
• It'll probably work out: improved list-decoding through random operations
• Singleton-type bounds for list-decoding and list-recovery, and related results
• Restricted isometry of Fourier matrices and list decodability of random linear codes
• Two theorems on list decoding (extended abstract)
• Average-radius list-recoverability of random linear codes
• Every list-decodable code for high noise has abundant near-optimal rate puncturings
• Restricted isometry of Fourier matrices and list decodability of random linear codes
• Improved list-decodability of random linear binary codes
• Combinatorial Limitations of Average-Radius List Decoding
• Combinatorial bounds for list decoding
• On the list-decodability of random linear codes
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Explicit List-decodable codes with optimal rate for computationally bounded channels

This page was built for publication: Limits to List Decoding Random Codes

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