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. https://resolver.caltech.edu/CaltechAUTHORS:20200225-113212660
Full text is not posted in this repository. Consult Related URLs below.
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200225-113212660
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: | Article | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||||||||||
ORCID: |
| ||||||||||||||
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. | ||||||||||||||
Funders: |
| ||||||||||||||
Subject Keywords: | Error-correcting codes; lower bounds; locally decodable codes; private information retrieval | ||||||||||||||
Issue or Number: | 3 | ||||||||||||||
Classification Code: | MSC: 68P30 | ||||||||||||||
DOI: | 10.1007/s00037-006-0216-3 | ||||||||||||||
Record Number: | CaltechAUTHORS:20200225-113212660 | ||||||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20200225-113212660 | ||||||||||||||
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). https://doi.org/10.1007/s00037-006-0216-3 | ||||||||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||||
ID Code: | 101536 | ||||||||||||||
Collection: | CaltechAUTHORS | ||||||||||||||
Deposited By: | Tony Diaz | ||||||||||||||
Deposited On: | 25 Feb 2020 20:19 | ||||||||||||||
Last Modified: | 16 Nov 2021 18:03 |
Repository Staff Only: item control page