The n^{1/3} barrier for 2-server PIR's broken! A lesson for us all!

Recall: PIR stands for Private Information Retrieval. Here is the model: A database is an n-bit string (my wife tells me this is not true). The user wants to find the ith bit without the database knowing what bit the user  wants. The user COULD just request ALL n bits. Can the user use less communication? See here for a website of many papers on PIR.

1. If there is just one copy of the DB and there are no comp. constraints on the computational power of the DB then ANY protocol requires n bits comm.
2. If there is one copy of the DB then, with some comp constraints, you can do better. I state one result: if quadratic residue is hard then there is a protocol using n^epsilon bits of comm. (Kushilevitz and Ostrovsky). The rest of this post is about the info-theoretic case, so the DB has no comp. constraints.
3. If there are two copies of the DB then there is a protocol that uses n^{1/3} bits. (Chor, Kushilevitz, Goldreich, Sudan)
4. If there are three copies of the DB then there is a protocl that uses n^{1/32582658} bits. Really! (Yekhanin).
5. If a 2-server protocol is a bilinear-group protocol (which all prior constructions were) then it must  take n^{1/3}.(Razborov and Yekhanin)
6. Most known constructions put into a geometric framework (Woodruff and Yekhanin). 

Recently Dvir ahd Gopi posted a paper  here which gives a 2-server PIR protocol that uses n^P bits where P= sqrt( (log log n)/log n)). That breaks the barrier proven by RY! How is that possible?

The barrier result was only for a certain type of PIR. It DID cover all the known PIR schemes at the time. But it does not cover this one.

This is how Barrier SHOULD work--- they should not discourage, but they should point to difficulties so that someone can overcome them.

Also note, the new result used the some of the Framework of Woodruff and Yekhanin. So good to unify and obtain  new proofs of old results.