Exponential lower bound for 2-query locally decodable codes via a quantum argument
From MaRDI portal
Publication:5901095
DOI10.1145/780542.780560zbMath1192.81082arXivquant-ph/0208062OpenAlexW2000211775WikidataQ56815273 ScholiaQ56815273MaRDI QIDQ5901095
Iordanis Kerenidis, Ronald de Wolf
Publication date: 16 August 2010
Published in: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/quant-ph/0208062
Related Items
A quadratic lower bound for three-query linear locally decodable codes over any field, Quantum symmetrically-private information retrieval, Expanding the sharpness parameter area based on sequential \(3 \rightarrow 1\) parity-oblivious quantum random access code, Unnamed Item, Lower bounds for adaptive locally decodable codes, Robust quantum private queries, General constructions for information-theoretic private information retrieval, Quantum computing, postselection, and probabilistic polynomial-time, Short Locally Testable Codes and Proofs: A Survey in Two Parts, Exponential lower bound for 2-query locally decodable codes via a quantum argument, Short Locally Testable Codes and Proofs