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]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png)
|
PDF
- Published Version
See Usage Policy. 422kB |
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: |
| |||||||||
| ORCID: |
| |||||||||
| 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 | |||||||||
| DOI: | 10.1109/CCC.2002.1004353 | |||||||||
| 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: | 09 Nov 2021 16:50 |
Repository Staff Only: item control page
