© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

ACM Symposium on Theory of Computing (STOC)

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

Eli Ben‐Sasson, Ariel Gabizon, Yohay Kaplan, Swastik Kopparty, Shubangi Saraf

Published May 28, 2013• 16 citations

Abstract

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.

DOI: 10.1145/2488608.2488714

Related papers

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

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

Ronald Cramer, Chaoping Xing, Chen Yuan

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}.

arXiv:1604.01925•Apr 7, 2016•1 citation

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

Hulls of Reed-Solomon Codes via Algebraic Geometry Codes

Bocong Chen, San Ling, Hongwei Liu

Let${\mathrm{ RS}}_{k}(\mathbf {a})$be a$k$-dimensional Reed-Solomon (RS) code over$\mathbb {F}_{q}$associated with$\mathbf {a}=(\alpha _{1},\cdots,\alpha _{n})$and let$h=\prod _{i=1}^{n}(z-\alpha _{i})$be a polynomial in variable$z$. In this paper, by expressing${\mathrm{ RS}}_{k}(\mathbf {a})$as an$\mathcal {L}$-construction algebraic geometry code, we completely determine the dimension of the hull${\mathrm{ RS}}_{k}(\mathbf {a})\bigcap {\mathrm{ RS}}_{k}(\mathbf {a})^{\perp} $in terms of the degree of the derivative of$h$and some relevant polynomials. As applications, we explicitly determine the parameters of MDS entanglement-assisted quantum error-correcting codes constructed from RS codes, and all linear complementary dual (resp. self-dual) RS codes are also fully described.

IEEE Transactions on Information Theory•Oct 4, 2022•15 citations

Robust Local Testability of Tensor Products of Constant-Rate Algebraic Geometry Codes

Sumegha Garg, Akash Kumar Sengupta

We study the robust local testability of tensor products of two Algebraic-Geometry (AG) codes. In particular, we prove that constant rate AG codes are robust locally testable. This significantly generalizes the seminal result of Polishchuk-Spielman (1994), which proved robust local testability of Reed-Solomon codes. We establish an algebraic-geometric framework that enables us to geometrically interpret codewords in tensor products of AG codes. Thereby, we use tools from intersection theory of algebraic surfaces to prove a divisibility criterion for AG codes, that generalizes the bivariate divisibility result of Polishchuk-Spielman.Over the years, robust local testability of tensor products has played a key role in the development of classical locally testable codes (LTCs) as well as quantum Low Density Parity Check (qLDPC) codes and quantum Locally Testable Codes (qLTCs). To the best of our knowledge, after Reed-Solomon codes, our result provides the first explicit family of robustly locally testable codes with constant rate and linear dual-distance. Moreover, our result, when combined with Golowich-Guruswami (2024), yields new explicit families of good quantum CSS codes of length N which are locally testable with locality $O(\sqrt N )$ and constant soundness.

Annual Symposium on Foundations of Computer Science•Dec 14, 2025•0 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

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.

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.

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}.

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.

Let

{\mathrm{ RS}}_{k}(\mathbf {a})

be a

k

-dimensional Reed-Solomon (RS) code over

\mathbb {F}_{q}

associated with

\mathbf {a}=(\alpha _{1},\cdots,\alpha _{n})

and let

h=\prod _{i=1}^{n}(z-\alpha _{i})

be a polynomial in variable

z

. In this paper, by expressing

{\mathrm{ RS}}_{k}(\mathbf {a})

as an

\mathcal {L}

-construction algebraic geometry code, we completely determine the dimension of the hull${\mathrm{ RS}}_{k}(\mathbf {a})\bigcap {\mathrm{ RS}}_{k}(\mathbf {a})^{\perp}

in terms of the degree of the derivative of

h$and some relevant polynomials. As applications, we explicitly determine the parameters of MDS entanglement-assisted quantum error-correcting codes constructed from RS codes, and all linear complementary dual (resp. self-dual) RS codes are also fully described.

We study the robust local testability of tensor products of two Algebraic-Geometry (AG) codes. In particular, we prove that constant rate AG codes are robust locally testable. This significantly generalizes the seminal result of Polishchuk-Spielman (1994), which proved robust local testability of Reed-Solomon codes. We establish an algebraic-geometric framework that enables us to geometrically interpret codewords in tensor products of AG codes. Thereby, we use tools from intersection theory of algebraic surfaces to prove a divisibility criterion for AG codes, that generalizes the bivariate divisibility result of Polishchuk-Spielman.Over the years, robust local testability of tensor products has played a key role in the development of classical locally testable codes (LTCs) as well as quantum Low Density Parity Check (qLDPC) codes and quantum Locally Testable Codes (qLTCs). To the best of our knowledge, after Reed-Solomon codes, our result provides the first explicit family of robustly locally testable codes with constant rate and linear dual-distance. Moreover, our result, when combined with Golowich-Guruswami (2024), yields new explicit families of good quantum CSS codes of length N which are locally testable with locality

O(\sqrt N )

and constant soundness.