A record of my past conjectures re PIR

Oded Goldreich

July 2008


My initial conjecture about the communication complexity of $k$-server PIR was that $n^{1/(k+1)}$ was a lower bound. For $k>2$, this conjecture was disproved by Ambainis in his paper ``An Upper Bound On The Communication Complexity of Private Information Retrieval'' (24th ICALP, LNCS 1256, pages 401--407, 1997). Ambainis established an upper bound of $n^{1/(2k-1)}$, which became my revised conjecture for a tight result.

This conjecture was disproved by Beimel, Ishai, Kushilevitz, and Raymond in their paper ``Breaking the $O(n^{1/(2k-1)})$ barrier for information-theoretic private information retrieval'' (43rd FOCS, pages 261--270, 2002).

My last attempt at a conjecture was that for every $k$ there exists a constant $c=c(k)$ such that a $k$-server PIR requires communication complexity $n^c$. (Actually, this conjecture actually reflects better my original beliefs.) Needless to say, I expected $c(k)$ to equal the reciprocal of some small polynomial (and regreted having previously specified $c(k) as $1/(2k-1)$).

However, this last conjecture seems to be disproven by Yekhanin in his paper ``Towards 3-Query Locally Decodable Codes of Subexponential Length'' (39th STOC, pages 266--274, 2007).

I dare not make further conjectures....


Back to Oded Goldreich's homepage or to the full list of papers.