Linear-time list recovery of high-rate expander codes

DOI10.1016/j.ic.2018.02.004zbMath1403.94106arXiv1503.01955OpenAlexW2790601937MaRDI QIDQ1640994

Mary Wootters, Brett Hemenway

Publication date: 14 June 2018

Published in: Information and Computation, Automata, Languages, and Programming (Search for Journal in Brave)

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

zbMATH Keywords

linear codesgraph theoryrandomized algorithmscombinatorial codescoding and information theory

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Randomized algorithms (68W20)

Related Items

Linear-time list recovery of high-rate expander codes, Unnamed Item, Local List Recovery of High-Rate Tensor Codes and Applications, Unnamed Item, Unnamed Item, Unnamed Item, Explicit list-decodable codes with optimal rate for computationally bounded channels, Low-Density Parity-Check Codes Achieve List-Decoding Capacity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Ramanujan graphs
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• Linear-time list recovery of high-rate expander codes
• List decoding of error-correcting codes. Winning thesis of the 2002 ACM Doctoral Dissertation Competition
• Local correctability of expander codes
• Explicit subspace designs
• Expander codes
• A linear time erasure-resilient code with nearly optimal recovery
• Expander graphs and their applications
• Concatenated Codes: Serial and Parallel
• Distance properties of expander codes
• List decoding from erasures: bounds and code constructions
• Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets
• Linear time encodable and list decodable codes
• Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy
• A recursive approach to low complexity codes
• Improved decoding of Reed-Solomon and algebraic-geometry codes
• On expander codes
• Error exponents of expander codes
• ℓ2/ℓ2-Foreach Sparse Recovery with Low Risk
• Local Correctability of Expander Codes
• Folded codes from function field towers and improved optimal rate list decoding
• Subspace evasive sets
• Automata, Languages and Programming
• List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound