Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published May 2002 | Published
Book Section - Chapter Open

Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval


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.

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].

Attached Files

Published - GOLaccc02.pdf


Files (422.4 kB)
Name Size Download all
422.4 kB Preview Download

Additional details

August 19, 2023
October 24, 2023