Exponential Lower Bound for 2-Query Locally Decodable Codes
Iordanis Kerenidis, Ronald de Wolf · arXiv (Cornell University) · 2002
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.