文章基本信息

标题：Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval
本地全文：下载
作者：Oded Goldreich ; Howard Karloff ; Leonard Schulman 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2001
卷号：2001
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 ( 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 = ( 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.
关键词：Error Correcting Codes , Linear Codes , Private InformationRetrieval.