Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR02-059 | 9th August 2002 00:00

Exponential Lower Bound for 2-Query Locally Decodable Codes



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.

ISSN 1433-8092 | Imprint