Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Private InformationRetrieval:
TR01-080 | 14th November 2001
Oded Goldreich, Howard Karloff, Leonard Schulman, Luca Trevisan

Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval

Revisions: 3

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 ... more >>>

ISSN 1433-8092 | Imprint