Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published October 2006 | public
Journal Article

Lower bounds for linear locally decodable codes and private information retrieval


We prove that if a linear error-correcting code C:{0, 1}^n→{0, 1}^m is such that a bit of the message can be probabilistically reconstructed by looking at two entries of a corrupted codeword, then m = 2^(Ω (n)). We also present several extensions of this result. We show a reduction from the complexity of one-round, information-theoretic Private Information Retrieval Systems (with two servers) to Locally Decodable Codes, and conclude that if all the servers' answers are linear combinations of the database content, then t = Ω (n/2^a), where t is the length of the user's query and a is the length of the servers' answers. Actually, 2^a can be replaced by O(a^k), where k is the number of bit locations in the answer that are actually inspected in the reconstruction.

Additional Information

© 2006 Birkhäuser Verlag, Basel. Manuscript received 14 December 2003. We are grateful to Alex Samorodnitsky for suggesting the information-theoretic proof of Lemma 3.3 and allowing us to present it in Section 3.4. Thanks also to Noga Alon for helpful discussions, to Yan Zhong Ding for suggesting an improvement in Section 3.3, and to the anonymous referees for their valuable comments. A preliminary version of this work appeared in the proceedings of 17th IEEE Conference on Computational Complexity, pages 175–183, 2002. Oded Goldreich's work was supported by the MINERVA Foundation, Germany. Leonard Schulman's work was partially supported by NSF Career grant 0049092, the Charles Lee Powell Foundation, and an Okawa Foundation Grant. Luca Trevisan's work was supported by an NSF Career award CCR-9984703, a Sloan Research Fellowship, and an Okawa Foundation Grant.

Additional details

August 22, 2023
October 19, 2023