Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #3 to TR01-080 | 17th March 2002 00:00

#### Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval Revision of: TR01-080

Revision #3
Authors: Oded Goldreich, Howard Karloff, Leonard J. Schulman, Luca Trevisan
Accepted on: 17th March 2002 00:00
Keywords:

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.

Revision #2 to TR01-080 | 17th March 2002 00:00

Revision #2
Authors: Oded Goldreich, Howard Karloff, Leonard J. Schulman, Luca Trevisan
Accepted on: 17th March 2002 00:00
Keywords:

Abstract:

Revision #1 to TR01-080 | 17th March 2002 00:00

Revision #1
Authors: Oded Goldreich, Howard Karloff, Leonard J. Schulman, Luca Trevisan
Accepted on: 17th March 2002 00:00
Keywords:

Abstract:

### Paper:

TR01-080 | 14th November 2001 00:00

#### Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval

TR01-080
Authors: Oded Goldreich, Howard Karloff, Leonard J. Schulman, Luca Trevisan
Publication: 14th November 2001 09:44
Keywords:

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.

ISSN 1433-8092 | Imprint