Reproduce “Tensor Reed-Muller Codes: Achieving Capacity with Quasilinear Decoding Time” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Emmanuel Abbe, Colin Sandon, Oscar Sprumont
Researchers from EPFL developed Tensor Reed-Muller (TRM) codes, a structured variant of Reed-Muller codes, that achieve Shannon capacity on noisy channels. This work introduces quasilinear-time decoding algorithms, achieving O(n log n) or O(n log log n) complexity, thus bridging the gap between theoretical capacity and practical decoding efficiency for these codes.
Key insights
- The tensor product structure of TRM codes allows for a recursive and parallel decoding strategy, effectively breaking down the complex decoding problem into more manageable subproblems.
- Efficient decoders for specific RM code regimes (small blocklength and high-rate) can be successfully integrated as subroutines within a broader iterative decoding framework for capacity-achieving tensor codes.
- A general algorithm for tensor codes can correct adversarial errors by iteratively applying component-wise erasure correction, even if the component codes themselves do not possess general efficient error decoders.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.