CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20111102-143056331

[img]
Preview
PDF - Published Version
See Usage Policy.

412Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20111102-143056331

Abstract

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
https://doi.org/10.1109/CCC.2002.1004353 DOIArticle
https://resolver.caltech.edu/CaltechAUTHORS:20200225-113212660Related ItemJournal Article
ORCID:
AuthorORCID
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].
Group:TAPIR
Record Number:CaltechAUTHORS:20111102-143056331
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20111102-143056331
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: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1004353&isnumber=21680
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:27595
Collection:CaltechAUTHORS
Deposited By: Ruth Sustaita
Deposited On:03 Nov 2011 02:42
Last Modified:25 Feb 2020 19:33

Repository Staff Only: item control page