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(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 = Omega (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.