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

Back to either Oded Goldreich's homepage. or general list of papers.