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:1604.01925

Efficient Multi-Point Local Decoding of Reed-Muller Codes via Interleaved Codex

Ronald Cramer, Chaoping Xing, Chen Yuan

Published Apr 7, 2016• 1 citation
arXivHTMLPDF

Abstract

Reed-Muller codes are among the most important classes of locally correctable codes. Currently local decoding of Reed-Muller codes is based on decoding on lines or quadratic curves to recover one single coordinate. To recover multiple coordinates simultaneously, the naive way is to repeat the local decoding for recovery of a single coordinate. This decoding algorithm might be more expensive, i.e., require higher query complexity. In this paper, we focus on Reed-Muller codes with usual parameter regime, namely, the total degree of evaluation polynomials is $d=Θ({q})$, where $q$ is the code alphabet size (in fact, $d$ can be as big as $q/4$ in our setting). By introducing a novel variation of codex, i.e., interleaved codex (the concept of codex has been used for arithmetic secret sharing \cite{C11,CCX12}), we are able to locally recover arbitrarily large number $k$ of coordinates of a Reed-Muller code simultaneously at the cost of querying $O(q^2k)$ coordinates. It turns out that our local decoding of Reed-Muller codes shows ({\it perhaps surprisingly}) that accessing $k$ locations is in fact cheaper than repeating the procedure for accessing a single location for $k$ times. Our estimation of success error probability is based on error probability bound for $t$-wise linearly independent variables given in \cite{BR94}.

DOI
10.48550/arxiv.1604.01925

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

On the Local Correctabilities of Projective Reed-Muller Codes

Sian-Jheng Lin

In this paper, we show that the projective Reed-Muller~(PRM) codes form a family of locally correctable codes~(LCC) in the regime of low query complexities. A PRM code is specified by the alphabet size $q$, the number of variables $m$, and the degree $d$. When $d\leq q-1$, we present a perfectly smooth local decoder to recover a symbol by accessing $γ\leq q$ symbols to the coordinates fall on a line. There are three major parameters considered in LCCs, namely the query complexity, the message length and the code length. This paper shows that PRM codes are shorter than generalized Reed-Muller~(GRM) codes in LCCs. Precisely, given a GRM code over a field of size $q$, there exists a class of shorter codes over a field of size $q-1$, while maintaining the same values on the query complexities and the message lengths.

arXiv:1702.02671•Feb 9, 2017•0 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

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

Emmanuel A. Abbe, Colin Sandon, Oscar Sprumont

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.

arXiv:2601.16164•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2026•1 citation

A new family of locally correctable codes based on degree-lifted algebraic geometry codes

Eli Ben‐Sasson, Ariel Gabizon, Yohay Kaplan +2 more

We describe new constructions of error correcting codes, obtained by "degree-lifting" a short algebraic geometry base-code of block-length q to a lifted-code of block-length qm, for arbitrary integer m. The construction generalizes the way degree-d, univariate polynomials evaluated over the q-element field (also known as Reed-Solomon codes) are "lifted" to degree-d, m-variate polynomials (Reed-Muller codes). A number of properties are established: The rate of the degree-lifted code is approximately a 1/m!-fraction of the rate of the base-code. The relative distance of the degree-lifted code is at least as large as that of the base-code. This is proved using a generalization of the Schwartz-Zippel Lemma to degree-lifted Algebraic-Geometry codes. [Local correction] If the base code is invariant under a group that is "close" to being doubly-transitive (in a precise manner defined later then the degree-lifted code is locally correctable with query complexity at most q2. The automorphisms of the base-code are crucially used to generate query-sets, abstracting the use of affine-lines in the local correction procedure of Reed-Muller codes. Taking a concrete illustrating example, we show that degree-lifted Hermitian codes form a family of locally correctable codes over an alphabet that is significantly smaller than that obtained by Reed-Muller codes of similar constant rate, message length, and distance.

ACM Symposium on Theory of Computing (STOC)•May 28, 2013•16 citations
Reed-Muller codes are among the most important classes of locally correctable codes. Currently local decoding of Reed-Muller codes is based on decoding on lines or quadratic curves to recover one single coordinate. To recover multiple coordinates simultaneously, the naive way is to repeat the local decoding for recovery of a single coordinate. This decoding algorithm might be more expensive, i.e., require higher query complexity. In this paper, we focus on Reed-Muller codes with usual parameter regime, namely, the total degree of evaluation polynomials is d=Θ(q)d=Θ({q})d=Θ(q), where qqq is the code alphabet size (in fact, ddd can be as big as q/4q/4q/4 in our setting). By introducing a novel variation of codex, i.e., interleaved codex (the concept of codex has been used for arithmetic secret sharing \cite{C11,CCX12}), we are able to locally recover arbitrarily large number kkk of coordinates of a Reed-Muller code simultaneously at the cost of querying O(q2k)O(q^2k)O(q2k) coordinates. It turns out that our local decoding of Reed-Muller codes shows ({\it perhaps surprisingly}) that accessing kkk locations is in fact cheaper than repeating the procedure for accessing a single location for kkk times. Our estimation of success error probability is based on error probability bound for ttt-wise linearly independent variables given in \cite{BR94}.
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.
In this paper, we show that the projective Reed-Muller~(PRM) codes form a family of locally correctable codes~(LCC) in the regime of low query complexities. A PRM code is specified by the alphabet size qqq, the number of variables mmm, and the degree ddd. When d≤q−1d\leq q-1d≤q−1, we present a perfectly smooth local decoder to recover a symbol by accessing γ≤qγ\leq qγ≤q symbols to the coordinates fall on a line. There are three major parameters considered in LCCs, namely the query complexity, the message length and the code length. This paper shows that PRM codes are shorter than generalized Reed-Muller~(GRM) codes in LCCs. Precisely, given a GRM code over a field of size qqq, there exists a class of shorter codes over a field of size q−1q-1q−1, while maintaining the same values on the query complexities and the message lengths.
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.
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.
We describe new constructions of error correcting codes, obtained by "degree-lifting" a short algebraic geometry base-code of block-length q to a lifted-code of block-length qm, for arbitrary integer m. The construction generalizes the way degree-d, univariate polynomials evaluated over the q-element field (also known as Reed-Solomon codes) are "lifted" to degree-d, m-variate polynomials (Reed-Muller codes). A number of properties are established: The rate of the degree-lifted code is approximately a 1/m!-fraction of the rate of the base-code. The relative distance of the degree-lifted code is at least as large as that of the base-code. This is proved using a generalization of the Schwartz-Zippel Lemma to degree-lifted Algebraic-Geometry codes. [Local correction] If the base code is invariant under a group that is "close" to being doubly-transitive (in a precise manner defined later then the degree-lifted code is locally correctable with query complexity at most q2. The automorphisms of the base-code are crucially used to generate query-sets, abstracting the use of affine-lines in the local correction procedure of Reed-Muller codes. Taking a concrete illustrating example, we show that degree-lifted Hermitian codes form a family of locally correctable codes over an alphabet that is significantly smaller than that obtained by Reed-Muller codes of similar constant rate, message length, and distance.