Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2601.16164 · IEEE International Symposium on Information Theory (ISIT)

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

Emmanuel A. Abbe, Colin Sandon, Oscar Sprumont

Published Jun 1, 2026• 1 citation
arXivHTMLPDF

Abstract

Define the codewords of the Tensor Reed-Muller code $\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 $\left\{x_{ij}\right\}_{i=1,\dots,t}^{j=1,\dots m_i}$ with degree at most $r_i$ in the variables $x_{i1},x_{i2},\dots,x_{im_i}$. The generator matrix of $\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 $\mathsf{RM}(r_1,m_1),\dots, \mathsf{RM}(r_t,m_t)$. We show that for any constant rate $R$ below capacity, one can construct a Tensor Reed-Muller code $\mathsf{TRM}(r_1,m_1;\dotsc;r_t,m_t)$ of rate $R$ that is decodable in quasilinear time. For any blocklength $n$, we provide two constructions of such codes: 1) Our first construction (with $t=3$) has error probability $n^{-ω(\log n)}$ and decoding time $O(n\log\log n)$. 2) Our second construction, for any $t\geq 4$, has error probability $2^{-n^{\frac{1}{2}-\frac{1}{2(t-2)}-o(1)}}$ and decoding time $O(n\log n)$. One of our main tools is a polynomial-time algorithm for decoding an arbitrary tensor code $C=C_1\otimes\dotsc\otimes C_t$ from $\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,\dotsc,C_t$ to themselves be decodable in polynomial time.

DOI
10.1109/isit62367.2026.11654036

Related papers

Efficiently decoding Reed-Muller codes from random errors

Ramprasad Saptharishi, Shpilka, Amir, Ben Lee Volk

Reed-Muller codes encode an $m$-variate polynomial of degree $r$ by evaluating it on all points in $\{0,1\}^m$. We denote this code by $RM(m,r)$. The minimal distance of $RM(m,r)$ is $2^{m-r}$ and so it cannot correct more than half that number of errors in the worst case. For random errors one may hope for a better result. In this work we give an efficient algorithm (in the block length $n=2^m$) for decoding random errors in Reed-Muller codes far beyond the minimal distance. Specifically, for low rate codes (of degree $r=o(\sqrt{m})$) we can correct a random set of $(1/2-o(1))n$ errors with high probability. For high rate codes (of degree $m-r$ for $r=o(\sqrt{m/\log m})$), we can correct roughly $m^{r/2}$ errors. More generally, for any integer $r$, our algorithm can correct any error pattern in $RM(m,m-(2r+2))$ for which the same erasure pattern can be corrected in $RM(m,m-(r+1))$. The results above are obtained by applying recent results of Abbe, Shpilka and Wigderson (STOC, 2015), Kumar and Pfister (2015) and Kudekar et al. (2015) regarding the ability of Reed-Muller codes to correct random erasures. The algorithm is based on solving a carefully defined set of linear equations and thus it is significantly different than other algorithms for decoding Reed-Muller codes that are based on the recursive structure of the code. It can be seen as a more explicit proof of a result of Abbe et al. that shows a reduction from correcting erasures to correcting errors, and it also bares some similarities with the famous Berlekamp-Welch algorithm for decoding Reed-Solomon codes.

arXiv:1503.09092•Mar 31, 2015•2 citations

Recursive decoding of Reed-Muller codes

Ilya I. Dumer

New soft- and hard decision decoding algorithms are presented for general Reed-Muller codes $\left\{\genfrac{}{}{0pt}{}{m}{r}\right\} $ of length $2^{m}$ and distance $2^{m-r}$. We use Plotkin $(u,u+v)$ construction and decompose code $\left\{\genfrac{}{}{0pt}{}{m}{r}\right\} $ onto subblocks $u\in\left\{\genfrac{}{}{0pt}{}{m-1}{r}\right\} $ and $v\in\left\{\genfrac{}{}{0pt}{}{m-1}{r-1}\right\} .$ In decoding, we first try to find a subblock $v$ from the better protected code and then proceed with the block $u$. The likelihoods of the received symbols are recalculated in a way similar to belief propagation. Thus, decoding is relegated to the two constituent codes. We repeat this recursion and execute decoding only at the end nodes $\left\{\genfrac{}{}{0pt}{}{j}{1}\right\} $ and $\left\{\genfrac{}{}{0pt}{}{j}{j-1}\right\} $. The overall complexity has low order of $n\log n.$ It is shown that this decoding substantially outperforms other algorithms of polynomial complexity known for RM codes. In particular, for medium and high code rates, the algorithm corrects most error patterns of weight $d\ln d/2.$

arXiv:1703.05303•Mar 14, 2017•4 citations

Efficiently Decoding Reed–Muller Codes From Random Errors

Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk

Reed-Muller (RM) codes encode an m-variate polynomial of degree at most r by evaluating it on all points in {0,1}m. We denote this code by RM(r,m). The minimum distance of RM(r,m) is 2m-rand so it cannot correct more than half that number of errors in the worst case. For random errors one may hope for a better result. In this paper we give an efficient algorithm (in the block length n=2m) for decoding random errors in RM codes far beyond the minimum distance. Specifically, for low-rate codes (of degree r=o(√m)), we can correct a random set of (1/2-o(1))n errors with high probability. For high rate codes (of degree m-r for r=o(√m/log m)), we can correct roughly mr/2errors. More generally, for any integer r, our algorithm can correct any error pattern in RM(m-(2r+2),m), for which the same erasure pattern can be corrected in RM(m-(r+1),m). The results above are obtained by applying recent results of Abbe, Shpilka, and Wigderson (STOC, 2015) and Kudekar et al. (STOC, 2016) regarding the ability of RM codes to correct random erasures. The algorithm is based on solving a carefully defined set of linear equations and thus it is significantly different than other algorithms for decoding RM codes that are based on the recursive structure of the code. It can be seen as a more explicit proof of a result of Abbe et al. that shows a reduction from correcting erasures to correcting errors, and it also bares some similarities with the error-locating pair method of Pellikaan, Duursma, and Kötter that generalizes the Berlekamp-Welch algorithm for decoding Reed-Solomon codes.

IEEE Transactions on Information Theory•Feb 17, 2017•22 citations

Efficiently decoding Reed-Muller codes from random errors

Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk

Reed-Muller codes encode an m-variate polynomial of degree r by evaluating it on all points in {0,1}m. We denote this code by RM(m,r). The minimal distance of RM(m,r) is 2m−r and so it cannot correct more than half that number of errors in the worst case. For random errors one may hope for a better result.

ACM Symposium on Theory of Computing (STOC)•Jun 10, 2016•8 citations

On polylogarithmic decoding complexity for reed-muller codes

Ilya I. Dumer

For Reed-Muller (RM) codes of length n and distance d, a recursive decoding algorithm is designed that has complexity of order nlogn for any fixed rate R, and corrects most error patterns of weight up to (dlnd)/2 on the binary symmetric channels (BSC) and up to (2dlnd)/pi on the AWGN channels. For long RM codes of fixed order r, a vanishing decoding error probability and polylogarithmic decoding complexity of order (logn)r+1are obtained on the BSC given any transition probability p that is bounded away from 1/2

IEEE International Symposium on Information Theory (ISIT)•Dec 23, 2004•1 citation

Polar Codes: Characterization of Exponent, Bounds, and Constructions

Satish Babu Korada, Eren Şaşoğlu, Rudiger L. Urbanke

Polar codes were recently introduced by Arıkan. They achieve the capacity of arbitrary symmetric binary-input discrete memoryless channels under a low complexity successive cancellation decoding strategy. The original polar code construction is closely related to the recursive construction of Reed-Muller codes and is based on the $2 \times 2$ matrix $\bigl[ 1 &0 1& 1 \bigr]$. It was shown by Arıkan and Telatar that this construction achieves an error exponent of $\frac12$, i.e., that for sufficiently large blocklengths the error probability decays exponentially in the square root of the length. It was already mentioned by Arıkan that in principle larger matrices can be used to construct polar codes. A fundamental question then is to see whether there exist matrices with exponent exceeding $\frac12$. We first show that any $\ell \times \ell$ matrix none of whose column permutations is upper triangular polarizes symmetric channels. We then characterize the exponent of a given square matrix and derive upper and lower bounds on achievable exponents. Using these bounds we show that there are no matrices of size less than 15 with exponents exceeding $\frac12$. Further, we give a general construction based on BCH codes which for large $n$ achieves exponents arbitrarily close to 1 and which exceeds $\frac12$ for size 16.

arXiv:0901.0536•Jan 5, 2009•30 citations
Define the codewords of the Tensor Reed-Muller code TRM(r1,m1;r2,m2;… ;rt,mt)\mathsf{TRM}(r_1,m_1;r_2,m_2;\dots;r_t,m_t)TRM(r1​,m1​;r2​,m2​;…;rt​,mt​) to be the evaluation vectors of all multivariate polynomials in the variables {xij}i=1,…,tj=1,…mi\left\{x_{ij}\right\}_{i=1,\dots,t}^{j=1,\dots m_i}{xij​}i=1,…,tj=1,…mi​​ with degree at most rir_iri​ in the variables xi1,xi2,…,ximix_{i1},x_{i2},\dots,x_{im_i}xi1​,xi2​,…,ximi​​. The generator matrix of TRM(r1,m1;… ;rt,mt)\mathsf{TRM}(r_1,m_1;\dots;r_t,m_t)TRM(r1​,m1​;…;rt​,mt​) is thus the tensor product of the generator matrices of the Reed-Muller codes RM(r1,m1),…,RM(rt,mt)\mathsf{RM}(r_1,m_1),\dots, \mathsf{RM}(r_t,m_t)RM(r1​,m1​),…,RM(rt​,mt​). We show that for any constant rate RRR below capacity, one can construct a Tensor Reed-Muller code TRM(r1,m1;… ;rt,mt)\mathsf{TRM}(r_1,m_1;\dotsc;r_t,m_t)TRM(r1​,m1​;…;rt​,mt​) of rate RRR that is decodable in quasilinear time. For any blocklength nnn, we provide two constructions of such codes: 1) Our first construction (with t=3t=3t=3) has error probability n−ω(log⁡n)n^{-ω(\log n)}n−ω(logn) and decoding time O(nlog⁡log⁡n)O(n\log\log n)O(nloglogn). 2) Our second construction, for any t≥4t\geq 4t≥4, has error probability 2−n12−12(t−2)−o(1)2^{-n^{\frac{1}{2}-\frac{1}{2(t-2)}-o(1)}}2−n21​−2(t−2)1​−o(1) and decoding time O(nlog⁡n)O(n\log n)O(nlogn). One of our main tools is a polynomial-time algorithm for decoding an arbitrary tensor code C=C1⊗…⊗CtC=C_1\otimes\dotsc\otimes C_tC=C1​⊗…⊗Ct​ from dmin⁡(C)2max⁡{dmin⁡(C1),…,dmin⁡(Ct)}−1\frac{d_{\min}(C)}{2\max\{d_{\min}(C_1),\dotsc,d_{\min}(C_t) \}}-12max{dmin​(C1​),…,dmin​(Ct​)}dmin​(C)​−1 adversarial errors. Crucially, this algorithm does not require the codes C1,…,CtC_1,\dotsc,C_tC1​,…,Ct​ to themselves be decodable in polynomial time.
Reed-Muller codes encode an mmm-variate polynomial of degree rrr by evaluating it on all points in {0,1}m\{0,1\}^m{0,1}m. We denote this code by RM(m,r)RM(m,r)RM(m,r). The minimal distance of RM(m,r)RM(m,r)RM(m,r) is 2m−r2^{m-r}2m−r and so it cannot correct more than half that number of errors in the worst case. For random errors one may hope for a better result. In this work we give an efficient algorithm (in the block length n=2mn=2^mn=2m) for decoding random errors in Reed-Muller codes far beyond the minimal distance. Specifically, for low rate codes (of degree r=o(m)r=o(\sqrt{m})r=o(m​)) we can correct a random set of (1/2−o(1))n(1/2-o(1))n(1/2−o(1))n errors with high probability. For high rate codes (of degree m−rm-rm−r for r=o(m/log⁡m)r=o(\sqrt{m/\log m})r=o(m/logm​)), we can correct roughly mr/2m^{r/2}mr/2 errors. More generally, for any integer rrr, our algorithm can correct any error pattern in RM(m,m−(2r+2))RM(m,m-(2r+2))RM(m,m−(2r+2)) for which the same erasure pattern can be corrected in RM(m,m−(r+1))RM(m,m-(r+1))RM(m,m−(r+1)). The results above are obtained by applying recent results of Abbe, Shpilka and Wigderson (STOC, 2015), Kumar and Pfister (2015) and Kudekar et al. (2015) regarding the ability of Reed-Muller codes to correct random erasures. The algorithm is based on solving a carefully defined set of linear equations and thus it is significantly different than other algorithms for decoding Reed-Muller codes that are based on the recursive structure of the code. It can be seen as a more explicit proof of a result of Abbe et al. that shows a reduction from correcting erasures to correcting errors, and it also bares some similarities with the famous Berlekamp-Welch algorithm for decoding Reed-Solomon codes.
New soft- and hard decision decoding algorithms are presented for general Reed-Muller codes $\left\{\genfrac{}{}{0pt}{}{m}{r}\right\} $ of length 2m2^{m}2m and distance 2m−r2^{m-r}2m−r. We use Plotkin (u,u+v)(u,u+v)(u,u+v) construction and decompose code $\left\{\genfrac{}{}{0pt}{}{m}{r}\right\} $ onto subblocks $u\in\left\{\genfrac{}{}{0pt}{}{m-1}{r}\right\} $ and v∈{m−1r−1}.v\in\left\{\genfrac{}{}{0pt}{}{m-1}{r-1}\right\} .v∈{r−1m−1​}. In decoding, we first try to find a subblock vvv from the better protected code and then proceed with the block uuu. The likelihoods of the received symbols are recalculated in a way similar to belief propagation. Thus, decoding is relegated to the two constituent codes. We repeat this recursion and execute decoding only at the end nodes $\left\{\genfrac{}{}{0pt}{}{j}{1}\right\} $ and $\left\{\genfrac{}{}{0pt}{}{j}{j-1}\right\} $. The overall complexity has low order of nlog⁡n.n\log n.nlogn. It is shown that this decoding substantially outperforms other algorithms of polynomial complexity known for RM codes. In particular, for medium and high code rates, the algorithm corrects most error patterns of weight dln⁡d/2.d\ln d/2.dlnd/2.
Reed-Muller (RM) codes encode an m-variate polynomial of degree at most r by evaluating it on all points in {0,1}m. We denote this code by RM(r,m). The minimum distance of RM(r,m) is 2m-rand so it cannot correct more than half that number of errors in the worst case. For random errors one may hope for a better result. In this paper we give an efficient algorithm (in the block length n=2m) for decoding random errors in RM codes far beyond the minimum distance. Specifically, for low-rate codes (of degree r=o(√m)), we can correct a random set of (1/2-o(1))n errors with high probability. For high rate codes (of degree m-r for r=o(√m/log m)), we can correct roughly mr/2errors. More generally, for any integer r, our algorithm can correct any error pattern in RM(m-(2r+2),m), for which the same erasure pattern can be corrected in RM(m-(r+1),m). The results above are obtained by applying recent results of Abbe, Shpilka, and Wigderson (STOC, 2015) and Kudekar et al. (STOC, 2016) regarding the ability of RM codes to correct random erasures. The algorithm is based on solving a carefully defined set of linear equations and thus it is significantly different than other algorithms for decoding RM codes that are based on the recursive structure of the code. It can be seen as a more explicit proof of a result of Abbe et al. that shows a reduction from correcting erasures to correcting errors, and it also bares some similarities with the error-locating pair method of Pellikaan, Duursma, and Kötter that generalizes the Berlekamp-Welch algorithm for decoding Reed-Solomon codes.
For Reed-Muller (RM) codes of length n and distance d, a recursive decoding algorithm is designed that has complexity of order nlogn for any fixed rate R, and corrects most error patterns of weight up to (dlnd)/2 on the binary symmetric channels (BSC) and up to (2dlnd)/pi on the AWGN channels. For long RM codes of fixed order r, a vanishing decoding error probability and polylogarithmic decoding complexity of order (logn)r+1are obtained on the BSC given any transition probability p that is bounded away from 1/2
Polar codes were recently introduced by Arıkan. They achieve the capacity of arbitrary symmetric binary-input discrete memoryless channels under a low complexity successive cancellation decoding strategy. The original polar code construction is closely related to the recursive construction of Reed-Muller codes and is based on the 2×22 \times 22×2 matrix $\bigl[ 1 &0 1& 1 \bigr]$. It was shown by Arıkan and Telatar that this construction achieves an error exponent of 12\frac1221​, i.e., that for sufficiently large blocklengths the error probability decays exponentially in the square root of the length. It was already mentioned by Arıkan that in principle larger matrices can be used to construct polar codes. A fundamental question then is to see whether there exist matrices with exponent exceeding 12\frac1221​. We first show that any ℓ×ℓ\ell \times \ellℓ×ℓ matrix none of whose column permutations is upper triangular polarizes symmetric channels. We then characterize the exponent of a given square matrix and derive upper and lower bounds on achievable exponents. Using these bounds we show that there are no matrices of size less than 15 with exponents exceeding 12\frac1221​. Further, we give a general construction based on BCH codes which for large nnn achieves exponents arbitrarily close to 1 and which exceeds 12\frac1221​ for size 16.