🔢 mathematics

Tensor Reed-Muller Codes: Achieving Capacity with Quasilinear Decoding Time

This paper introduces Tensor Reed-Muller codes constructed via the tensor product of Reed-Muller codes, demonstrating that they achieve channel capacity with quasilinear decoding time and exponentially small error probabilities through a novel algorithm capable of decoding arbitrary tensor codes from adversarial errors without requiring the constituent codes to be efficiently decodable.

Original authors: Emmanuel Abbe, Colin Sandon, Oscar Sprumont

Published 2026-01-23

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Emmanuel Abbe, Colin Sandon, Oscar Sprumont

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Fixing Broken Messages

Imagine you are sending a secret message across a very noisy radio channel. Static, interference, and random glitches (errors) keep messing up your message. In the world of computer science, we use codes to protect these messages. A code adds extra "redundant" information so that if some parts get corrupted, the receiver can still figure out what the original message was.

For decades, a specific type of code called Reed-Muller (RM) codes has been famous. They are like the "gold standard" for reliability. Recent research proved that these codes are theoretically perfect: they can handle as much noise as physically possible (this is called "achieving capacity").

However, there was a huge problem: While we knew these codes could fix the message, we didn't have a fast enough computer program (algorithm) to actually do it when the messages were long and the noise was random. It was like having a perfect lock that you could never pick quickly enough to be useful.

This paper introduces a new variation called Tensor Reed-Muller (TRM) codes. The authors show that by rearranging how these codes are built, they can be decoded (fixed) incredibly fast, almost as fast as the theoretical limit allows.

The Core Idea: The "Tensor" Twist

To understand the new code, let's look at the old one first.

Old RM Codes: Imagine a message is a giant grid of numbers. The old codes treat this grid as a single, flat sheet of data.
New TRM Codes: The authors suggest thinking of the message not as a flat sheet, but as a multi-layered cake or a stack of transparent sheets.

They take the variables (the ingredients of the message) and split them into different groups.

Group 1: Controls the rows.
Group 2: Controls the columns.
Group 3: Controls the layers (depth).

This structure is called a Tensor. It's like taking a 2D spreadsheet and turning it into a 3D block, or even a 4D hyper-block. The magic is that the rules for "validity" apply to each slice of this block independently.

How the Decoding Works: The "Layered Repair" Strategy

The paper proposes a clever way to fix errors in this multi-layered block. Instead of trying to fix the whole mess at once (which is slow), they fix it layer by layer.

The Analogy: The "Row-Then-Column" Repair Crew
Imagine you have a massive, damaged mural painted on a wall. Some paint is missing or wrong.

Step 1 (The Small Fix): First, you look at just the rows (horizontal lines). Because the rows are short and simple, you can use a "brute force" method: you check every possible version of that short line and pick the one that looks most like the original. This is fast because the rows are short.
Step 2 (The Big Fix): Now that the rows are mostly fixed, you look at the columns (vertical lines). The columns are long, but because the rows are already mostly correct, the columns only have a few errors left. The authors use a special, high-speed algorithm (based on previous work) to fix these long columns quickly.
Step 3 (The Deep Fix): If the message is even more complex (3D or 4D), they repeat this process for the "depth" layers. They fix the slices, then the columns of the slices, then the layers of the whole block.

Why is this fast?
The paper claims this process takes quasilinear time. In everyday terms, if your message size doubles, the time it takes to fix it only increases by a tiny bit more than double (like $N \times \log N$ ). This is incredibly efficient compared to older methods that might take $N^2$ or $N^3$ time.

The Two Main Results

The authors present two specific ways to build these codes, depending on how complex you want the "block" to be:

The 3-Layer Cake (t=3):
- Speed: Extremely fast ( $O(n \log \log n)$ ). It's almost as fast as just reading the message.
- Reliability: The chance of failing to fix the message is incredibly low (so low it's written as $n$ to the power of a negative huge number).
- Best for: When you need speed above all else.
The Multi-Layer Tower (t≥4):
- Speed: Still very fast ( $O(n \log n)$ ), like sorting a list of names.
- Reliability: Even more reliable. The chance of failure drops exponentially (like $2^{-n}$ ).
- Best for: When you need near-perfect reliability while still keeping the speed high.

The Secret Weapon: "Adversarial" vs. "Random" Errors

A major part of the paper is a new tool they built to help with the decoding.

Random Errors: Like static on a radio; they happen by chance.
Adversarial Errors: Like a hacker trying to specifically break your code by changing the worst possible bits.

The authors created a general algorithm that can fix Tensor Codes even if a malicious attacker tries to break them, as long as the number of bad bits isn't too high. Crucially, this algorithm works even if the individual layers of the code aren't easy to decode on their own. It's like a master mechanic who can fix a complex engine even if they don't have the manual for every single part, as long as they know how the parts fit together.

Summary

The paper solves a 70-year-old puzzle. It proves that by reorganizing Reed-Muller codes into a multi-dimensional "Tensor" structure, we can:

Reach the theoretical limit of how much noise a channel can handle.
Decode the message almost instantly (in quasilinear time).

They achieved this by breaking the problem down into smaller, manageable slices (rows, columns, layers) and using a mix of brute-force checks for small slices and smart algorithms for large slices. The result is a code that is both theoretically perfect and practically usable.

Technical Summary: Tensor Reed-Muller Codes

Problem Statement

Reed-Muller (RM) codes, introduced in 1954, are a fundamental family of error-correcting codes. While recent theoretical work has established that RM codes achieve capacity on the Binary Erasure Channel (BEC) and all Binary Memoryless Symmetric (BMS) channels, a significant gap remains in the constant-rate regime regarding efficient decoding. Specifically, no polynomial-time algorithm is currently known for reliably decoding constant-rate Reed-Muller codes under random noise. Existing efficient decoders are limited to specific regimes: either very low/high rates, small blocklengths, or specific error patterns where the noise is below a certain threshold relative to the code's minimum distance.

This paper addresses the challenge of constructing a variant of Reed-Muller codes that achieves capacity on BMS channels while admitting a decoding algorithm with quasilinear time complexity.

Methodology

The authors introduce Tensor Reed-Muller (TRM) codes, defined as the tensor product of multiple Reed-Muller codes. A codeword in $\text{TRM}(r_1, m_1; \dots; r_t, m_t)$ corresponds to the evaluation vector of multivariate polynomials where the degree in each group of variables $x_{i1}, \dots, x_{im_i}$ is at most $r_i$ . The generator matrix of a TRM code is the tensor product of the generator matrices of its constituent RM codes.

The decoding strategy relies on a hybrid approach combining two distinct regimes of RM decoding:

Brute-force decoding for short, low-rate components: The first few dimensions of the tensor are constructed from short RM codes ( $m_1, m_2$ ) with sublinear blocklengths. These are decoded via brute-force search, which is efficient when the blocklength is small (e.g., $2^{m_1} \approx \log n$ ).
High-rate adversarial decoding for long components: The remaining dimensions utilize high-rate RM codes. The authors leverage a result from [SSV17] which allows for the correction of a constant fraction of random errors in high-rate RM codes, provided the error pattern is sparse enough relative to the code's minimum distance.

The core technical innovation is a general algorithm for decoding arbitrary tensor codes ( $C = C_1 \otimes \dots \otimes C_t$ ) from adversarial errors. This algorithm operates by iteratively treating errors as erasures:

It first identifies rows (or subtensors) that are not valid codewords of the constituent code $C_1$ and replaces them with erasure symbols.
It then checks columns (or the next axis) to see if a unique codeword in $C_2$ is consistent with the partially erased data. If so, it fills the column; otherwise, it erases the entire column.
This process is repeated for all axes.
Crucially, this algorithm does not require the constituent codes $C_i$ to be efficiently decodable themselves; it only requires a polynomial-time procedure to test for consistency with a codeword (which is efficient for RM codes via Gaussian elimination or specialized RM decoders).

Key Contributions

Tensor Reed-Muller Codes: The definition and analysis of TRM codes as a capacity-achieving family with efficient decoding properties.
General Tensor Code Decoder: A polynomial-time algorithm (Theorem 2/Theorem 5) that decodes any tensor code $C_1 \otimes \dots \otimes C_t$ from $\frac{d_{\min}(C)}{2 \max_i d_{\min}(C_i)} - 1$ adversarial errors. This algorithm runs in $O(n \log n)$ time for Reed-Muller components.
Capacity-Achieving Constructions: Two specific constructions of TRM codes that achieve any rate $R < 1 - h(p)$ $R < 1 - h (p)$ (where $p$ $p$ is the noise probability) with quasilinear decoding time:
- Construction 1 ( $t=3$ ): Achieves error probability $n^{-\omega(\log n)}$ with decoding time $O(n \log \log n)$ .
- Construction 2 ( $t \ge 4$ ): Achieves error probability $2^{-n^{\frac{1}{2} - \frac{1}{2(t-2)} - o(1)}}$ with decoding time $O(n \log n)$ .

Results

The paper proves Theorem 1, establishing that for any noise probability $p > 0$ and rate $R < 1 - h(p)$ , one can construct a TRM code of length $n^{1 \pm o(1)}$ and rate $R \pm o(1)$ that is decodable with high probability in quasilinear time.

For $t=3$ : The decoder runs in $O(n \log \log n)$ time. The failure probability is bounded by $n^{-\omega(\log n)}$ . This is achieved by using a very short first RM code (decoded by brute force) to reduce the error rate to a negligible level, followed by a second RM code to clean up the remaining errors.
For $t \ge 4$ : The decoder runs in $O(n \log n)$ time. The failure probability is bounded by $2^{-n^{\frac{1}{2} - \frac{1}{2(t-2)} - o(1)}}$ . This construction adds additional tensor dimensions with high-rate RM codes, iteratively reducing the error probability further. The error exponent approaches the distance-optimal $2^{-\Omega(\sqrt{n})}$ as $t$ increases, though the paper notes that for $t \le \sqrt{\log n}$ , the improvement is subsumed by lower-order terms.

The analysis relies on the Chernoff bound to show that the initial brute-force decoding step reduces the error density sufficiently such that the subsequent high-rate decoding steps (which rely on the adversarial error correction capability of [SSV17]) succeed with high probability.

Significance

The paper claims to resolve the open problem of efficient decoding for capacity-achieving Reed-Muller-like codes in the constant-rate regime. While standard Reed-Muller codes are known to achieve capacity, their efficient decoding in this regime remains an open problem. By introducing the Tensor Reed-Muller variant, the authors demonstrate that capacity can be achieved with quasilinear decoding time ( $O(n \log n)$ or better).

The work highlights that tensoring codes offers advantages over traditional concatenated codes (Forney's construction) in this context:

Structural Simplicity: The tensor product of RM codes retains a simple description as multilinear polynomials with degree constraints on variable groups, whereas concatenated RM codes lack such an intuitive description.
Alphabet Efficiency: Unlike concatenation, which often requires large alphabets for the outer code, the tensor product approach works naturally with binary alphabets.

The paper positions the general tensor code decoder (Theorem 5) as a tool of independent interest, capable of decoding arbitrary tensor codes from adversarial errors without requiring the constituent codes to be efficiently decodable, provided a consistency check is available.