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

National Conference on Communications

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

V. Lalitha, N. Prakash, Govinda M. Kamath, P. Vijay Kumar

Published Feb 1, 2012• 0 citations
Publisher

Abstract

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.

DOI
10.1109/ncc.2012.6176752

Related papers

Exponential lower bound for 2-query locally decodable codes via a quantum argument

Iordanis Kerenidis, Ronald de Wolf

A locally decodable code encodes n-bit strings x in m-bit codewords C(x), in such a way that one can recover any bit xi from a corrupted codeword by querying only a few bits of that word. We use a quantum argument to prove that LDCs with 2 classical queries need exponential length: m=2Ω(n). Previously this was known only for linear codes (Goldreich et al. 02). Our proof shows that a 2-query LDC can be decoded with only 1 quantum query, and then proves an exponential lower bound for such 1-query locally quantum-decodable codes. We also show that q quantum queries allow more succinct LDCs than the best known LDCs with q classical queries. Finally, we give new classical lower bounds and quantum upper bounds for the setting of private information retrieval. In particular, we exhibit a quantum 2 server PIR scheme with O(n3/10) qubits of communication, improving upon the O(n1/3) bits of communication of the best known classical 2-server PIR.

ACM Symposium on Theory of Computing (STOC)•Jun 9, 2003•194 citations

Exponential lower bound for 2-query locally decodable codes via a quantum argument

Iordanis Kerenidis, Ronald de Wolf

A locally decodable code encodes n-bit strings x in m-bit codewords C(x), in such a way that one can recover any bit xi from a corrupted codeword by querying only a few bits of that word. We use a quantum argument to prove that LDCs with 2 classical queries need exponential length: m=2Ω(n). Previously this was known only for linear codes (Goldreich et al. 02). Our proof shows that a 2-query LDC can be decoded with only 1 quantum query, and then proves an exponential lower bound for such 1-query locally quantum-decodable codes. We also show that q quantum queries allow more succinct LDCs than the best known LDCs with q classical queries. Finally, we give new classical lower bounds and quantum upper bounds for the setting of private information retrieval. In particular, we exhibit a quantum 2 server PIR scheme with O(n3/10) qubits of communication, improving upon the O(n1/3) bits of communication of the best known classical 2-server PIR.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 2003•25 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

Locally Decodable Quantum Codes

Jop Briët, Ronald de Wolf

We study a quantum analogue of locally decodable error-correcting codes. A q-query locally decodable quantum code encodes n classical bits in an m-qubit state, in such a way that each of the encoded bits can be recovered with high probability by a measurement on at most q qubits of the quantum code, even if a constant fraction of its qubits have been corrupted adversarially. We show that such a quantum code can be transformed into a classical q-query locally decodable code of the same length that can be decoded well on average (albeit with smaller success probability and noise-tolerance). This shows, roughly speaking, that q-query quantum codes are not significantly better than q-query classical codes, at least for constant or small q.

arXiv:0806.2101•Leibniz international proceedings in informatics•Jun 12, 2008•1 citation

Local Correction of Linear Functions over the Boolean Cube

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

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.

arXiv:2403.20305•ACM Symposium on Theory of Computing (STOC)•Jun 10, 2024•0 citations

From Irreducible Representations to Locally Decodable Codes.

Klim Efremenko

Locally Decodable Code (LDC) is a code that encodes a message in a way that one can decode any particular symbol of the message by reading only a constant number of locations, even if a constant fraction of the encoded message is adversarially corrupted. In this paper we present a new approach for the construction of LDCs. We show that if there exists an irreducible representation (ρ, V) of G and q elements g1, g2,..., gq in G such that there exists a linear combination of matrices ρ(gi) that is of rank one, then we can construct a q-query Locally Decodable Code C: V → F G. We show the potential of this approach by constructing constant query LDCs of subexponential length matching the parameters of the best known constructions. 1

Electronic colloquium on computational complexity•Jan 1, 2011•0 citations
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.
A locally decodable code encodes n-bit strings x in m-bit codewords C(x), in such a way that one can recover any bit xi from a corrupted codeword by querying only a few bits of that word. We use a quantum argument to prove that LDCs with 2 classical queries need exponential length: m=2Ω(n). Previously this was known only for linear codes (Goldreich et al. 02). Our proof shows that a 2-query LDC can be decoded with only 1 quantum query, and then proves an exponential lower bound for such 1-query locally quantum-decodable codes. We also show that q quantum queries allow more succinct LDCs than the best known LDCs with q classical queries. Finally, we give new classical lower bounds and quantum upper bounds for the setting of private information retrieval. In particular, we exhibit a quantum 2 server PIR scheme with O(n3/10) qubits of communication, improving upon the O(n1/3) bits of communication of the best known classical 2-server PIR.
A locally decodable code encodes n-bit strings x in m-bit codewords C(x), in such a way that one can recover any bit xi from a corrupted codeword by querying only a few bits of that word. We use a quantum argument to prove that LDCs with 2 classical queries need exponential length: m=2Ω(n). Previously this was known only for linear codes (Goldreich et al. 02). Our proof shows that a 2-query LDC can be decoded with only 1 quantum query, and then proves an exponential lower bound for such 1-query locally quantum-decodable codes. We also show that q quantum queries allow more succinct LDCs than the best known LDCs with q classical queries. Finally, we give new classical lower bounds and quantum upper bounds for the setting of private information retrieval. In particular, we exhibit a quantum 2 server PIR scheme with O(n3/10) qubits of communication, improving upon the O(n1/3) bits of communication of the best known classical 2-server PIR.
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.
We study a quantum analogue of locally decodable error-correcting codes. A q-query locally decodable quantum code encodes n classical bits in an m-qubit state, in such a way that each of the encoded bits can be recovered with high probability by a measurement on at most q qubits of the quantum code, even if a constant fraction of its qubits have been corrupted adversarially. We show that such a quantum code can be transformed into a classical q-query locally decodable code of the same length that can be decoded well on average (albeit with smaller success probability and noise-tolerance). This shows, roughly speaking, that q-query quantum codes are not significantly better than q-query classical codes, at least for constant or small q.
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.
Locally Decodable Code (LDC) is a code that encodes a message in a way that one can decode any particular symbol of the message by reading only a constant number of locations, even if a constant fraction of the encoded message is adversarially corrupted. In this paper we present a new approach for the construction of LDCs. We show that if there exists an irreducible representation (ρ, V) of G and q elements g1, g2,..., gq in G such that there exists a linear combination of matrices ρ(gi) that is of rank one, then we can construct a q-query Locally Decodable Code C: V → F G. We show the potential of this approach by constructing constant query LDCs of subexponential length matching the parameters of the best known constructions. 1