## 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.