Bounds for Linear Locally Decodable Codes and
Private Information Retrieval
Webpage for a paper by Goldreich, Karloff, Schulman, and Trevisan
We prove that if a linear error correcting code
is such that a bit of the message can
be probabilistically reconstructed by looking at two entries of a
corrupted codeword, then the codeword length must be exponential
in the block length (i.e., the amount of information encoded).
We also present several extensions of this result,
and derive implications on the complexity of one-round, two-server,
information-theoretic Private Information Retrieval Systems.
Material available on-line
either Oded Goldreich's homepage.
or general list of papers.