Capital Area Theory Seminar

NOTE: This is work done by Chor, Goldreich, Kushlievitz, Sudan, and Ambainis. None of the work was done by Gasarch.

Let's say you want to query a database BUT you don't want the database to KNOW what information you are querying. Can you ask it questions in a sly way? We consider the following model of the problem: A database is an n-bit string. A query is a request for the some bit. One way to ensure your privacy is to query ALL n bits. This is quite expensive.

If there are 2 (or perhaps k) copies of the database around, that do not talk to each other, then you can do much better. In a paper of Chor, Goldreich, Kushlievitz, Sudan, it was shown that

1. If you have 2 databases then you can get the info you want with only O(n^1/3) bits of communication total, and
2. If you have k databases you can get the info you want with O(n^1/logk). Later, Ambainis improved this to O(n^1/k).

We will present these three results and summarize.