Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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

RSS-Feed

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
Downloads: 3974
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
Downloads: 3461
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 Schulman, Luca Trevisan
Publication: 14th November 2001 09:44
Downloads: 3389
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