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

Electronic colloquium on computational complexity

From Irreducible Representations to Locally Decodable Codes.

Klim Efremenko

Published Jan 1, 2011• 0 citations
OpenAlex

Abstract

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

Related papers

From irreducible representations to locally decodable codes

Klim Efremenko

A q-query Locally Decodable Code (LDC) is an error-correcting code that allows to read any particular symbol of the message by reading only q symbols of the codeword even if the codeword is adversary corrupted.

ACM Symposium on Theory of Computing (STOC)•May 19, 2012•7 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

Constant Query Locally Decodable Codes against Computationally Bounded Adversary

Rishiraj Bhattacharyya, Sourav Chakraborty

We consider the problem of Locally Decodable Codes against an adversary that is computationally bounded in terms of running time. Many times the computational limitations of the adversary help in designing better codes. In this paper we prove (using some standard crytographic assumptions) that in the case of constant query locally decodable codes the computational constraint does not make the adversary less powerful, unless both the sender and the receiver shares a secret key. We show, if either the receiver or the sender has a secret key (that is not known to the other) then designing LDCs against computationally bounded adversary is as hard as designing smooth codes unless some standard cryptographic assumptions are false.

•Nov 16, 2011•1 citation

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

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

Iordanis Kerenidis, Ronald de Wolf

We prove exponential lower bounds on the length of 2-query locally decodable codes. Goldreich et al. recently proved such bounds for the special case of linear locally decodable codes. Our proof shows that a 2-query locally decodable code 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 exhibit q-query locally quantum-decodable codes that are much shorter than the best known q-query classical codes. Finally, we give some new lower bounds for (not necessarily linear) private information retrieval systems.

arXiv:quant-ph/0208062•Electronic colloquium on computational complexity•Jan 1, 2002•4 citations
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
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 problem of Locally Decodable Codes against an adversary that is computationally bounded in terms of running time. Many times the computational limitations of the adversary help in designing better codes. In this paper we prove (using some standard crytographic assumptions) that in the case of constant query locally decodable codes the computational constraint does not make the adversary less powerful, unless both the sender and the receiver shares a secret key. We show, if either the receiver or the sender has a secret key (that is not known to the other) then designing LDCs against computationally bounded adversary is as hard as designing smooth codes unless some standard cryptographic assumptions are false.
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.
We prove exponential lower bounds on the length of 2-query locally decodable codes. Goldreich et al. recently proved such bounds for the special case of linear locally decodable codes. Our proof shows that a 2-query locally decodable code 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 exhibit q-query locally quantum-decodable codes that are much shorter than the best known q-query classical codes. Finally, we give some new lower bounds for (not necessarily linear) private information retrieval systems.