文章基本信息

标题：A Nearly Tight Bound for Private Information Retrieval Protocols
本地全文：下载
作者：Richard Beigel ; Lance Fortnow ; William Gasarch 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2003
卷号：2003
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We show that any 1-round 2-server Private Information Retrieval Protocol where the answers are 1-bit long must ask questions that are at least n − 2 bits long, which is nearly equal to the known n − 1 upper bound. This improves upon the approximately 0 25 n lower bound of Kerenidis and de Wolf while avoiding their use of quantum techniques.
关键词：lower bounds , private information retrieval