A guest post from Bill Gasarch. There have been two important NEW results in the field of Private Information Retrieval so its worth reviewing the field and the new results (Some background here).
This post is about InformationTheoretic Private Information Retrieval. We state the problem and five results in order of discovery, with the last two being the recent ones.
PROBLEM: A database is an nbit string (my wife tells me that databases are more complicated than that). The USER wants to know the ith bit but does not want the DB to have ANY CLUE of which bit he wanted.
EASY ANSWER: Request the ENTIRE DB. That is n bits.
QUESTION: Can we do this with substantially fewer than n bits?
ANSWER: NO if there is only one copy of the database.
NEW QUESTION: What if there are k copies of the DB? 2 DBs, O(n^{1/3}) bits; for k≥ 4, k DBs
O(n^{1/k})
Private Information Retrieval, Chor, Kushilevitz, Goldreich, Sudan, JACM1998, (Earlier version FOCS 95)NOTE: Introduced the field. Journal version has easy constructions. Conference version had slightly harder polyinterpolation constructions material that are a prelude to item (3) below.
NOTE: FOCS version has O(n^{1/k}) result, Journal omits it since item 2 below had already appeared.
NOTE3: k=3 gives O(n^{1/3})—can't use that its 3 DB's instead of 2. 
k DB's, O(n^{1/(2k1)})
Upper Bound on the Communication Complexity of Private Information Retrieval Ambainis, ICALP97,NOTE: Used Recursion. Constant is exponential. Later papers that reduced the constant to polynomial lead the way to the next paper.
NOTE3: k=3 gives O(n^{1/5}). 
k DB's, n^{O(loglog k/(k log k))}
Breaking the O(n^{1/(2k1)}) barrier for informationtheoretic Private Information Retrieval Beimel, Ishai, Kushilevitz, Raymond. FOCS 02.
NOTE: Brilliant use of polynomials.
NOTE3: Techniques yield k=3, O(n^{1/5.25})  2 DB Ω(n^{1/3}) LOWER BOUND
An Ω(n^{1/3}) lower bound for bilinear group based Private Information Retrieval Razborov, Yekhanin, FOCS 2006.NOTE: Hard paper! Modeled 2DBPrivate Information Retrieval via Latin Squares and then used representation theory of finite groups to push through the lower bound. ALL current 2DB protocols fit the model, so lower bound is either legitimate or will point way to other techniques. My money is on legit. Even so, there aren't that many 2DB protocols so who knows…

3 DB O(n^{1/32,586,658}) PIR!
Really!
New Locally Decodable Codes and Private Information Retrieval Schemes, Sergey YekhaninNOTE: Wins award for largest distance between GREATNESS of content and AWFULNESS of title. I would have called it
A 3 DB O(n^{1/32,586,658}) PIR! Really!
NOTE: Uses Mersenne primes. The number used is based on the largest Mersenne prime known, which is 2^{32,586,658}1. If there are infinitely many Mersenne primes then, for infinite number of n, get k=3, n^{1/loglog n}Private Information Retrieval
NOTE: Vast improvement on k=3, n^{1/5.25}
PIR scheme (2): the new 3DB PIR leads to a kDB, O(n^{1/(bk1)}) where b is enormous.
PIR scheme (3): the new 3DB PIR leads to the same asymptotic kDB n^{O(loglog k/(k log k)} but with a much smaller constant in the Oof term.

Posted by Lance to Computational Complexity at 11/07/2006 01:55:00 PM 2 DBs, O(n^{1/3}) bits; for k≥ 4, k DBs
O(n^{1/k})