Revision #3 Authors: Oded Goldreich, Howard Karloff, Leonard J. Schulman, Luca Trevisan

Accepted on: 17th March 2002 00:00

Downloads: 2722

Keywords:

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.

Revision #2 Authors: Oded Goldreich, Howard Karloff, Leonard J. Schulman, Luca Trevisan

Accepted on: 17th March 2002 00:00

Downloads: 2699

Keywords:

Revision #1 Authors: Oded Goldreich, Howard Karloff, Leonard J. Schulman, Luca Trevisan

Accepted on: 17th March 2002 00:00

Downloads: 2595

Keywords:

TR01-080 Authors: Oded Goldreich, Howard Karloff, Leonard Schulman, Luca Trevisan

Publication: 14th November 2001 09:44

Downloads: 2654

Keywords:

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.