Abstract:

I will cover two of my results in distance approximation. Consider the setting in which two parties want to approximate the distance between their input vectors.

First I will consider l_2, the Euclidean distance. It is known how to approximate l_2 efficiently. However, if we require the protocol to be private, that is, neither party can learn more than what follows from the distance and his/her private input, much less is known. Feigenbaum, Ishai, Malkin, Nissim, Strauss, and Wright [FIMNSW] gave a protocol with O(sqrt{d}) communication for privately approximating the Hamming distance of two d-dimensional vectors. I will give a private protocol with polylog(d) communication for l_2. As a special case, this yields an exponential improvement over [FIMNSW] for the Hamming distance.

Next I will consider the l_p distance, for p > 2. This problem is motivated by recent research in streaming algorithms, and has applications in database theory. I will give a 1-round protocol achieving optimal communication for this problem, up to logarithmic factors. It is easy to implement in the streaming model, and consequently resolves the main open question of a 1996 paper of Alon, Matias, and Szegedy.

Joint work with Piotr Indyk (STOC 2005, TCC 2006).