Abstract:
We prove that if a linear error correcting code $\C:\{0,1\}^n\to\{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.

Abstract:

Abstract:

Abstract:
We prove that if a linear error correcting code $\C:\{0,1\}^n\to\{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.