A Caltech Library Service

Lower bounds for linear locally decodable codes and private information retrieval

Goldreich, Oded and Karloff, Howard and Schulman, Leonard J. and Trevisan, Luca (2006) Lower bounds for linear locally decodable codes and private information retrieval. Computational Complexity, 15 (3). pp. 263-296. ISSN 1016-3328. doi:10.1007/s00037-006-0216-3.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription ReadCube access ItemConference Paper
Schulman, Leonard J.0000-0001-9901-2797
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.
Funding AgencyGrant Number
Minerva FoundationUNSPECIFIED
Charles Lee Powell FoundationUNSPECIFIED
Okawa FoundationUNSPECIFIED
Alfred P. Sloan FoundationUNSPECIFIED
Subject Keywords:Error-correcting codes; lower bounds; locally decodable codes; private information retrieval
Issue or Number:3
Classification Code:MSC: 68P30
Record Number:CaltechAUTHORS:20200225-113212660
Persistent URL:
Official Citation:Goldreich, O., Karloff, H., Schulman, L.J. et al. Lower bounds for linear locally decodable codes and private information retrieval. comput. complex. 15, 263–296 (2006).
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:101536
Deposited By: Tony Diaz
Deposited On:25 Feb 2020 20:19
Last Modified:16 Nov 2021 18:03

Repository Staff Only: item control page