Lower bounds for linear locally decodable codes and private information retrieval

被引：55

作者：

Goldreich, O ^{[1
]}

Karloff, H ^{[1
]}

Schulman, LJ ^{[1
]}

Trevisan, L ^{[1
]}

机构：

[1] Weizmann Inst Sci, Dept Comp Sci, IL-76100 Rehovot, Israel

来源：

17TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS | 2002年

关键词：

D O I：

10.1109/CCC.2002.1004353

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We prove that if a linear error-correcting code C : {0, 1}(n) --> {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.

引用

页码：175 / 183

页数：9