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.

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.