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

Emmanuel Abbe, Colin Sandon, Oscar Sprumont · 2026

Read Tensor Reed-Muller Codes: Achieving Capacity with Quasilinear Decoding Time by Emmanuel Abbe, Colin Sandon, Oscar Sprumont (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-16164.txt.

Introduction

Emmanuel Abbe, Colin Sandon and Oscar Sprumont build codes from grid maps of many vars. Their 2026 preprint sets out Tensor Reed Muller codes. Code words come from values of maps with sets of vars. Each set has its own grade cap for the maps. Such codes join traits of the known Reed Muller codes in a grid form.

The team shows these codes can reach the top rate for a channel. They also give a read back method with near straight time cost. Top rate with fast read back is a rare pair. It makes the codes fit for real links and stores. The work is a step in code theory.

Catalog record

CREATOREmmanuel Abbe, Colin Sandon, Oscar Sprumont
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-16164

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Tensor Reed-Muller Codes: Achieving Capacity with Quasilinear Decoding Time Emmanuel Abbe, Colin Sandon, Oscar Sprumont Abstract Define the codewords of the Tensor Reed-Muller code 𝖳𝖱𝖬 ⁡ ( r 1 , m 1 , r 2 , m 2 , … , r t , m t ) \mathsf{TRM}(r_{1},m_{1};r_{2},m_{2};\dots;r_{t},m_{t}) to be the evaluation vectors of all multivariate polynomials in the variables { x i ​ j } i = 1 , … , t j = 1 , … ​ m i \left\{x_{ij}\right\}_{i=1,\dots,t}^{j=1,\dots m_{i}} with degree at most r i r_{i} in the variables x i ​ 1 , x i ​ 2 , … , x i ​ m i x_{i1},x_{i2},\dots,x_{im_{i}} . The generator matrix of 𝖳𝖱𝖬 ⁡ ( r 1 , m 1 , … , r t , m t ) \mathsf{TRM}(r_{1},m_{1};\dots;r_{t},m_{t}) is thus the tensor product of the generator matrices of the Reed-Muller codes 𝖱𝖬 ⁡ ( r 1 , m 1 ) , … , 𝖱𝖬 ⁡ ( r t , m t ) \mathsf{RM}(r_{1},m_{1}),\dots,\mathsf{RM}(r_{t},m_{t}) . We show that for any constant rate R R below capacity, one can construct a Tensor Reed-Muller code 𝖳𝖱𝖬 ⁡ ( r 1 , m 1 , … , r t , m t ) \mathsf{TRM}(r_{1},m_{1};\dotsc;r_{t},m_{t}) of rate R R that is decodable in quasilinear time. For any blocklength n n , we provide two constructions of such codes: • Our first construction (with t = 3 t=3 ) has error probability n − ω ⁡ ( log ⁡ n ) n^{-\omega(\log n)} and decoding time O ⁡ ( n ​ log ⁡ log ​ n ) O(n\log\log n) . • Our second construction, for any t ≥ 4 t\geq 4 , has error probability 2 − n 1 2 − 1 2 ​ ( t − 2 ) − o ⁡ ( 1 ) 2^{-n^{\frac{1}{2}-\frac{1}{2(t-2)}-o(1)}} and decoding time O ⁡ ( n ​ log ⁡ n ) O(n\log n) . One of our main tools is a polynomial-time algorithm for decoding an arbitrary tensor code C = C 1 ⊗ … ⊗ C t C=C_{1}\otimes\dotsc\otimes C_{t} from d min ​ ( C ) 2 ​ max ⁡ { d min ​ ( C 1 ) , … , d min ​ ( C t ) } − 1 \frac{d_{\min}(C)}{2\max\{d_{\min}(C_{1}),\dotsc,d_{\min}(C_{t})\}}-1 adversarial errors. Crucially, this algorithm does not require the codes C 1 , … , C t C_{1},\dotsc,C_{t} to themselves be decodable in polynomial time. 1 Introduction Reed-Muller (RM) codes, which were introduced by Reed and Muller in 1954 [ Ree54 , Mul54 ] , are one of the simplest and most widely used families of codes. Their codewords can be viewed as the evaluation vectors (over \mathbb{F}_{2}^{m} ) of all polynomials of degree at most r in m variables. Although RM codes were recently shown to achieve capacity on the erasure channel [ KKM+17 ] as well as all BMS channels for both the bit error [ RP24 ] and the block error [ AS23 ] , we do not know of any polynomial-time algorithm for decoding them in the constant-rate regime. In this paper, we introduce a variant of RM codes called Tensor Reed-Muller codes , where the m variables are split into groups and the degree requirement is applied to each group separately 1 1 1 See Section 2.2 for the formal definition. . We prove that Tensor Reed-Muller codes achieve capacity efficiently: Theorem 1 . Consider any noise probability p>0 and any rate R<1-h(p). Then for any integers n\in\mathbb{N} and t\geq 4 , we can construct a Tensor Reed-Muller code \mathsf{TRM}(r_{1},m_{1};\dotsc;r_{t},m_{t}) of length n^{1\pm o(1)} and rate R\pm o(1) such that: 1. If t=3 , there exists a decoder D for \mathsf{TRM}(r_{1},m_{1};r_{2},m_{2};r_{3},m_{3}) with worst-case runtime O(n\log{\log n}) and decoding success probability 1-n^{-\omega(\log n)} under p -noisy errors. 2. If t>3 , there exists a decoder D for \mathsf{TRM}(r_{1},m_{1};\dotsc;r_{t},m_{t}) with worst-case runtime O(n{\log n}) and decoding success probability 1-2^{-n^{\frac{1}{2}-\frac{1}{2(t-2)}-o(1)}} under p -noisy errors. Our analysis makes use of the following result for adversarial errors, which is of independent interest: Theorem 2 . Consider any integers r_{1}\leq m_{1},\dotsc,r_{t}\leq m_{t} and define n=2^{m_{1}+\dotsc+m_{t}}. Then there is an O(n\log n) -time algorithm for decoding the code C:=\mathsf{TRM}(r_{1},m_{1};\dotsc;r_{t},m_{t}) from \displaystyle\left\lceil\frac{d_{\min}(C)}{2\max_{i}\big\{2^{m_{i}-r_{i}}\big\}}\right\rceil-1 adversarial errors. One can modify our algorithm to decode any tensor code C:=C_{1}\otimes\dotsc\otimes C_{t} from \left\lceil\frac{d_{\min}(C)}{2\max\{d_{\min}(C_{1}),\dots,d_{\min}(C_{t})\}}\right\rceil-1 adversarial errors, but in that case the algorithm runs in time O(n\sum_{i}n_{i}) , for n_{i} the length of code C_{i} (see Section 4 .) 1.1 Previous Work Reed-Muller codes have in recent years attracted a lot of attention for their decoding performances under random noise. By bounding their weight distribution appropriately, [ ASW15 , SS20 ] first showed that Reed-Muller codes achieve capacity on the erasure channel (BEC) and the symmetric channel (BSC) in the regimes where the rate of the code is either very close to 0 or very close to 1 . [ KKM+17 ] then leveraged the double transitivity of their permutation group to show that Reed-Muller codes of constant rates achieve capacity on the BEC. [ Sam20 ] combined the results of [ KKM+17 ] with new \ell_{q}- norm inequalities to obtain better bounds on the weight distributions of doubly transitive codes. This allowed [ HSS21 ] to prove that Reed-Muller codes of constant rates can decode a constant fraction of random errors, although the maximum code rate allowed was below the capacity of the channel. The first capacity results were obtained in [ RP24 ] , which proved that for any R\in(0,1) , the asymptotic bit error probability of a rate- R Reed-Muller code vanishes on any memoryless symmetric channel (BMS) whose capacity is greater than R . That still left open the question of showing that the block error probability vanishes as well, which was finally proven in [ AS23 , ASSV24 ] : Theorem 3 ( [ AS23 ] ) . Consider any error parameter p\in(0,\frac{1}{2}) and any rate R<1-h(p) . Then any sequence of Reed-Muller codes \big\{\mathsf{RM}(r_{i},m_{i})\big\}_{i} of asymptotic rate R satisfies \displaystyle\Pr_{z\sim p}\Big[D_{ML}(c+z)=c\Big] \displaystyle\geq 1-2^{-2^{\Omega(\sqrt{m_{i}})}} for every c\in\mathsf{RM}(r_{i},m_{i}) , where z\sim p denotes a p -noisy error string and D_{ML} denotes the maximum-likelihood decoder for the code \mathsf{RM}(r_{i},m_{i}). The line of work described above established that Reed-Muller codes achieve capacity on all BMS channels. The most natural next challenge is then to understand whether or not they can be decoded efficiently. Reed provided the first known algorithm in [ Ree54 ] , allowing for the correction of half the minimum distance many adversarial errors. For random errors, efficient algorithms for decoding \mathsf{RM}(r,m) are known in the case where r is constant. The first algorithms [ VMS92 , Sak05 ] focused on the regime where r\in\{1,2\} , but algorithms for all values of r=O(1) have since been obtained. They exploit either the recursive structure of Reed-Muller codes [ Dum04 , DS06 , Dum06 , YA20 ] or their minimum-weight parity checks [ SHP18 ] . In the regime r=\omega(1) , the only known algorithm with proven polynomial runtime is the algorithm of [ SSV17 ] , which successfully decodes any error pattern in \mathsf{RM}(m-2t,m) for which the same erasure pattern can be corrected in \mathsf{RM}(m-t,m) . Theorem 4 ( [ SSV17 ] ) . For any integers

Read the complete text