I don't know anything about DP, so my question might be unrelated. But I think perhaps someone can answer it. Almost 20 years ago, I was told of the following problem at the university:
You have two identical databases (sets of n bits) that do not communicate. You want to know a single bit from the database. How many bits do you have retrieve from each database so that neither database would learn about which bit you were looking for?
The simplest answer is n, retrieve all bits. But we were also given a better answer, square root of n - you order the bits into a square, ask for a xor of random subset of columns but to the first/second database respectively with/without the column you're looking for.
And here is my question, we were also told that this can be done even better, in cube root of n bits. But I never learned the answer, and since I wonder, was that claim correct? Does anyone know this problem and the better solution?
You have two identical databases (sets of n bits) that do not communicate. You want to know a single bit from the database. How many bits do you have retrieve from each database so that neither database would learn about which bit you were looking for?
The simplest answer is n, retrieve all bits. But we were also given a better answer, square root of n - you order the bits into a square, ask for a xor of random subset of columns but to the first/second database respectively with/without the column you're looking for.
And here is my question, we were also told that this can be done even better, in cube root of n bits. But I never learned the answer, and since I wonder, was that claim correct? Does anyone know this problem and the better solution?