Lower bounds for linear locally decodable codes and private information retrieval

• Main Authors: Goldreich, O., Karloff, H., Schulman, L.J., Trevisan, L.
• Format: Conference Proceeding
• Language: English
• Subjects: Algebraic combinatorics; Applied sciences; Coding, codes; Combinatorics; Combinatorics. Ordered structures; Complexity theory; Computer science; Decoding; Error correction; Error correction codes; Exact sciences and technology; Information retrieval; Information, signal and communications theory; Linear code; Mathematics; Probability and statistics; Protocols; Sciences and techniques of general use; Signal and communications theory; Statistics; Sufficiency and information; Telecommunications and information theory; Upper bound
• ISSN: 1093-0159; 2575-8403
• DOI: 10.1109/CCC.2002.1004353

We prove that if a linear error-correcting code C: {0, 1}/sup n/ /spl rarr/ {0, 1}/sup 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/sup /spl Omega/(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 = /spl Omega/(n/2/sup a/), where t is the length of the user's query and a is the length of the servers' answers. Actually, 2/sup a/ can be replaced by O(a/sup k/), where k is the number of bit locations in the answer that are actually inspected in the reconstruction.