© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:2403.20305 · ACM Symposium on Theory of Computing (STOC)

Local Correction of Linear Functions over the Boolean Cube

Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan

Published Jun 10, 2024• 0 citations

Abstract

We consider the task of locally correcting, and locally list-correcting, multivariate linear functions over the domain {0,1}n over arbitrary fields and more generally Abelian groups. Such functions form error-correcting codes of relative distance 1/2 and we give local-correction algorithms correcting up to nearly 1/4-fraction errors making O(logn) queries. This query complexity is optimal up to poly(loglogn) factors. We also give local list-correcting algorithms correcting (1/2 − ε)-fraction errors with Oε(logn) queries. These results may be viewed as natural generalizations of the classical work of Goldreich and Levin whose work addresses the special case where the underlying group is ℤ2. By extending to the case where the underlying group is, say, the reals, we give the first non-trivial locally correctable codes (LCCs) over the reals (with query complexity being sublinear in the dimension (also known as message length)). Previous works in the area mostly focused on the case where the domain is a vector space or a group and this lends to tools that exploit symmetry. Since our domains lack such symmetries, we encounter new challenges whose resolution may be of independent interest. The central challenge in constructing the local corrector is constructing “nearly balanced vectors” over {−1,1}n that span 1n — we show how to construct O(logn) vectors that do so, with entries in each vector summing to ±1. The challenge to the local-list-correction algorithms, given the local corrector, is principally combinatorial, i.e., in proving that the number of linear functions within any Hamming ball of radius (1/2−ε) is Oε(1). Getting this general result covering every Abelian group requires integrating a variety of known methods with some new combinatorial ingredients analyzing the structural properties of codewords that lie within small Hamming balls.

DOI: 10.1145/3618260.3649746

Related papers

Low Degree Local Correction Over the Boolean Cube

Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar +2 more

In this work, we show that the class of multivariate degree-d polynomials mapping {0,1}n to any Abelian group G is locally correctable with Õd((log n )d) queries for up to a fraction of errors approaching half the minimum distance of the underlying code. In particular, this result holds even for polynomials over the reals or the rationals, special cases that were previously not known. Further, we show that they are locally list correctable up to a fraction of errors approaching the minimum distance of the code. These results build on and extend the prior work of Amireddy, Behera, Paraashar, Srinivasan, and Sudan [1] (STOC 2024) who considered the case of linear polynomials (d = 1) and gave analogous results.

arXiv:2411.07374•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2025•1 citation

On t-designs and bounds relating query complexity to error resilience in locally correctable codes

V. Lalitha, N. Prakash, Govinda M. Kamath +1 more

An n-length block code C is said to be r-query locally correctable, if for any codeword x ∈ C, one can probabilistically recover any one of the n coordinates of the codeword x by querying at most r coordinates of a possibly corrupted version of x. It is known that linear codes whose duals contain 2-designs are locally correctable. In this article, we consider linear codes whose duals contain t-designs for larger t. It is shown here that for such codes, for a given number of queries r, under linear decoding, one can, in general, handle a larger number of corrupted bits. We exhibit to our knowledge, for the first time, a finite length code, whose dual contains 4-designs, which can tolerate a fraction of up to 0.567/r corrupted symbols as against a maximum of 0.5/r in prior constructions. We also present an upper bound that shows that 0.567 is the best possible for this code length and query complexity over this symbol alphabet thereby establishing optimality of this code in this respect. A second result in the article is a finite-length bound which relates the number of queries r and the fraction of errors that can be tolerated, for a locally correctable code that employs a randomized algorithm in which each instance of the algorithm involves t-error correction.

National Conference on Communications•Feb 1, 2012•0 citations

Message-Passing Algorithms and Improved LP Decoding

Sanjeev Arora, Constantinos Daskalakis, David Steurer

Linear programming (LP) decoding for low-density parity-check codes (and related domains such as compressed sensing) has received increased attention over recent years because of its practical performance-coming close to that of iterative decoding algorithms-and its amenability to finite-blocklength analysis. Several works starting with the work of Feldman showed how to analyze LP decoding using properties of expander graphs. This line of analysis works for only low error rates, about a couple of orders of magnitude lower than the empirically observed performance. It is possible to do better for the case of random noise, as shown by Daskalakis and Koetter and Vontobel. Building on work of Koetter and Vontobel, we obtain a novel understanding of LP decoding, which allows us to establish a 0.05 fraction of correctable errors for rate-½ codes; this comes very close to the performance of iterative decoders and is significantly higher than the best previously noted correctable bit error rate for LP decoding. Our analysis exploits an explicit connection between LP decoding and message-passing algorithms and, unlike other techniques, directly works with the primal linear program. An interesting byproduct of our method is a notion of a “locally optimal” solution that we show to always be globally optimal (i.e., it is the nearest codeword). Such a solution can in fact be found in near-linear time by a “reweighted” version of the min-sum algorithm, obviating the need for LP. Our analysis implies, in particular, that this reweighted version of the min-sum decoder corrects up to a 0.05 fraction of errors.

IEEE Transactions on Information Theory•Jul 13, 2012•24 citations

The Quantum Hamming Bound in Arbitrary Local Dimension

Yu-Xuan Zhang, Jing-Ling Chen

The quantum Hamming bound arises from a direct dimension estimate for exact quantum error-correcting codes. For nondegenerate codes, distinct correctable errors map the code space into orthogonal subspaces, so dimension counting directly gives the bound; degeneracy allows these subspaces to overlap and invalidates the argument. Although linear-programming, asymptotic, and structural approaches have advanced the problem from several directions, the general local-dimension case has remained open. Here we prove the quantum Hamming bound for every local dimension $q\ge3$. Building on the exact two-center Fourier reduction, we develop new overlap estimates for nonbinary Hamming spaces. For $q\ge4$, Jacobi estimates and monotonicity give a uniform gap; qutrits form the boundary case where the gap vanishes and are handled by a filtered correction. This completes the finite-length nonbinary case; together with the existing qubit result, it establishes the quantum Hamming bound for arbitrary local dimension.

quant-pharXiv:2606.22538•Jun 23, 2026•0 citations

Estimating Euclidean Distance to Linearity

Bogdanov, Andrej, Taschin, Lorenzo

Given oracle access to a real-valued function on the n-dimensional Boolean cube, how many queries does it take to estimate the squared Euclidean distance to its closest linear function within ε? Our main result is that O(log³(1/ε) ⋅ 1/ε²) queries suffice. Not only is the query complexity independent of n but it is optimal up to the polylogarithmic factor. Our estimator evaluates f on pairs correlated by noise rates chosen to cancel out the low-degree contributions to f while leaving the linear part intact. The query complexity is optimized when the noise rates are multiples of Chebyshev nodes. In contrast, we show that the dependence on n is unavoidable in two closely related settings. For estimation from random samples, Θ(√n/ε + 1/ε²) samples are necessary and sufficient. For agnostically learning a linear approximation with ε mean-square regret under the uniform distribution, Ω(n/√ε) nonadaptively chosen queries are necessary, while O(n/ε) random samples are known to be sufficient (Linial, Mansour, and Nisan). Our upper bounds apply to functions with bounded 4-norm. Our lower bounds apply even to ± 1-valued functions.

Leibniz international proceedings in informatics•Jan 1, 2025•0 citations

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

We consider the task of locally correcting, and locally list-correcting, multivariate linear functions over the domain {0,1}n over arbitrary fields and more generally Abelian groups. Such functions form error-correcting codes of relative distance 1/2 and we give local-correction algorithms correcting up to nearly 1/4-fraction errors making O(logn) queries. This query complexity is optimal up to poly(loglogn) factors. We also give local list-correcting algorithms correcting (1/2 − ε)-fraction errors with Oε(logn) queries. These results may be viewed as natural generalizations of the classical work of Goldreich and Levin whose work addresses the special case where the underlying group is ℤ2. By extending to the case where the underlying group is, say, the reals, we give the first non-trivial locally correctable codes (LCCs) over the reals (with query complexity being sublinear in the dimension (also known as message length)). Previous works in the area mostly focused on the case where the domain is a vector space or a group and this lends to tools that exploit symmetry. Since our domains lack such symmetries, we encounter new challenges whose resolution may be of independent interest. The central challenge in constructing the local corrector is constructing “nearly balanced vectors” over {−1,1}n that span 1n — we show how to construct O(logn) vectors that do so, with entries in each vector summing to ±1. The challenge to the local-list-correction algorithms, given the local corrector, is principally combinatorial, i.e., in proving that the number of linear functions within any Hamming ball of radius (1/2−ε) is Oε(1). Getting this general result covering every Abelian group requires integrating a variety of known methods with some new combinatorial ingredients analyzing the structural properties of codewords that lie within small Hamming balls.

In this work, we show that the class of multivariate degree-d polynomials mapping {0,1}n to any Abelian group G is locally correctable with Õd((log n )d) queries for up to a fraction of errors approaching half the minimum distance of the underlying code. In particular, this result holds even for polynomials over the reals or the rationals, special cases that were previously not known. Further, we show that they are locally list correctable up to a fraction of errors approaching the minimum distance of the code. These results build on and extend the prior work of Amireddy, Behera, Paraashar, Srinivasan, and Sudan [1] (STOC 2024) who considered the case of linear polynomials (d = 1) and gave analogous results.

An n-length block code C is said to be r-query locally correctable, if for any codeword x ∈ C, one can probabilistically recover any one of the n coordinates of the codeword x by querying at most r coordinates of a possibly corrupted version of x. It is known that linear codes whose duals contain 2-designs are locally correctable. In this article, we consider linear codes whose duals contain t-designs for larger t. It is shown here that for such codes, for a given number of queries r, under linear decoding, one can, in general, handle a larger number of corrupted bits. We exhibit to our knowledge, for the first time, a finite length code, whose dual contains 4-designs, which can tolerate a fraction of up to 0.567/r corrupted symbols as against a maximum of 0.5/r in prior constructions. We also present an upper bound that shows that 0.567 is the best possible for this code length and query complexity over this symbol alphabet thereby establishing optimality of this code in this respect. A second result in the article is a finite-length bound which relates the number of queries r and the fraction of errors that can be tolerated, for a locally correctable code that employs a randomized algorithm in which each instance of the algorithm involves t-error correction.

Linear programming (LP) decoding for low-density parity-check codes (and related domains such as compressed sensing) has received increased attention over recent years because of its practical performance-coming close to that of iterative decoding algorithms-and its amenability to finite-blocklength analysis. Several works starting with the work of Feldman showed how to analyze LP decoding using properties of expander graphs. This line of analysis works for only low error rates, about a couple of orders of magnitude lower than the empirically observed performance. It is possible to do better for the case of random noise, as shown by Daskalakis and Koetter and Vontobel. Building on work of Koetter and Vontobel, we obtain a novel understanding of LP decoding, which allows us to establish a 0.05 fraction of correctable errors for rate-½ codes; this comes very close to the performance of iterative decoders and is significantly higher than the best previously noted correctable bit error rate for LP decoding. Our analysis exploits an explicit connection between LP decoding and message-passing algorithms and, unlike other techniques, directly works with the primal linear program. An interesting byproduct of our method is a notion of a “locally optimal” solution that we show to always be globally optimal (i.e., it is the nearest codeword). Such a solution can in fact be found in near-linear time by a “reweighted” version of the min-sum algorithm, obviating the need for LP. Our analysis implies, in particular, that this reweighted version of the min-sum decoder corrects up to a 0.05 fraction of errors.

The quantum Hamming bound arises from a direct dimension estimate for exact quantum error-correcting codes. For nondegenerate codes, distinct correctable errors map the code space into orthogonal subspaces, so dimension counting directly gives the bound; degeneracy allows these subspaces to overlap and invalidates the argument. Although linear-programming, asymptotic, and structural approaches have advanced the problem from several directions, the general local-dimension case has remained open. Here we prove the quantum Hamming bound for every local dimension

q\ge3

. Building on the exact two-center Fourier reduction, we develop new overlap estimates for nonbinary Hamming spaces. For

q\ge4

, Jacobi estimates and monotonicity give a uniform gap; qutrits form the boundary case where the gap vanishes and are handled by a filtered correction. This completes the finite-length nonbinary case; together with the existing qubit result, it establishes the quantum Hamming bound for arbitrary local dimension.

Given oracle access to a real-valued function on the n-dimensional Boolean cube, how many queries does it take to estimate the squared Euclidean distance to its closest linear function within ε? Our main result is that O(log³(1/ε) ⋅ 1/ε²) queries suffice. Not only is the query complexity independent of n but it is optimal up to the polylogarithmic factor. Our estimator evaluates f on pairs correlated by noise rates chosen to cancel out the low-degree contributions to f while leaving the linear part intact. The query complexity is optimized when the noise rates are multiples of Chebyshev nodes. In contrast, we show that the dependence on n is unavoidable in two closely related settings. For estimation from random samples, Θ(√n/ε + 1/ε²) samples are necessary and sufficient. For agnostically learning a linear approximation with ε mean-square regret under the uniform distribution, Ω(n/√ε) nonadaptively chosen queries are necessary, while O(n/ε) random samples are known to be sufficient (Linial, Mansour, and Nisan). Our upper bounds apply to functions with bounded 4-norm. Our lower bounds apply even to ± 1-valued functions.

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.