Pseudorandom linear codes are list-decodable to capacity

DOI10.4230/LIPICS.ITCS.2024.90MaRDI QIDQ6906337zbMATH OpenFDO

Authors Aaron L Putterman, Edward Pyne

Publication date 4 November 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2024.90

zbMATH Keywords

derandomizationerror-correcting codes

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A combinatorial construction of almost-Ramanujan graphs using the zig-zag product
• An efficient decoder for a linear distance quantum LDPC code
• Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
• Expander codes
• Expander graphs and their applications
• Explicit, almost optimal, epsilon-balanced codes
• Good quantum LDPC codes with linear time decoders
• scientific article; zbMATH DE number 3760081 (Why is no real title available?)
• scientific article; zbMATH DE number 7758332 (Why is no real title available?)
• scientific article; zbMATH DE number 7758311 (Why is no real title available?)
• LDPC codes achieve list decoding capacity
• Linear-Time Encodable/Decodable Codes With Near-Optimal Rate
• Near-linear time decoding of Ta-Shma’s codes via splittable regularity
• On the List-Decodability of Random Linear Codes
• Pseudorandomness
• Soft Decoding, Dual BCH Codes, and Better List-Decodable $\varepsilon$-Biased Codes
• Three XOR-lemmas -- an exposition

Cited in

(1)

• When do low-rate concatenated codes approach the Gilbert-Varshamov bound?

This page was built for publication: Pseudorandom linear codes are list-decodable to capacity

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