Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR03-087 | 10th December 2003 00:00

A Nearly Tight Bound for Private Information Retrieval Protocols

RSS-Feed




TR03-087
Authors: Richard Beigel, Lance Fortnow, William Gasarch
Publication: 10th December 2003 17:29
Downloads: 2182
Keywords: 


Abstract:

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.25n$ lower
bound of Kerenidis and de Wolf while avoiding their use of quantum
techniques.


Comment(s):

Comment #1 to TR03-087 | 7th May 2006 13:43

Much cleaner version of ``A Nearly Tight Bound for PIR Retrieval Protocols" Comment on: TR03-087





Comment #1
Authors: R. Beigel, Fortnow, Gasarch
Accepted on: 7th May 2006 13:43
Downloads: 3877
Keywords: 


Abstract:

This is a much cleaner version of ``A Nearly Tight Bound for PIR Retrieval
Protocols". Readers are strongly encouraged to read this version, not the
one originally posted. The new version is in
Computational Complexity, Vol 15, No 1, 2006, 82--91.




ISSN 1433-8092 | Imprint