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 (2002) Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval. In: 17th IEEE Annual Conference on Computational Complexity. IEEE , Los Alamitos, CA, pp. 143-151. ISBN 0-7695-1468-5.

PDF - Published Version
See Usage Policy.


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:Book Section
Related URLs:
URLURL TypeDescription DOIArticle ItemJournal Article
Schulman, Leonard J.0000-0001-9901-2797
Additional Information:© 2002 IEEE. Date of Current Version: 07 August 2002. We are grateful to Alex Samorodnitsky for suggesting to us the information-theoretic proof of Lemma 3.3 and allowing us to present it in Section 3.4. Thanks also to Noga Alon for providing us with a proof of Lemma 3.5 and allowing us to reproduce it in our technical report [5].
Record Number:CaltechAUTHORS:20111102-143056331
Persistent URL:
Official Citation:Goldreich, O.; Karloff, H.; Schulman, L.J.; Trevisan, L.; , "Lower bounds for linear locally decodable codes and private information retrieval," Computational Complexity, 2002. Proceedings. 17th IEEE Annual Conference on , vol., no., pp.143-151, 2002 doi: 10.1109/CCC.2002.1004353 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:27595
Deposited By: Ruth Sustaita
Deposited On:03 Nov 2011 02:42
Last Modified:09 Nov 2021 16:50

Repository Staff Only: item control page