Events Calendar

Efficient and Private Distance Approximation

David WoodruffMassachusetts Institute of TechnologyAbstract: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).Biography: David Woodruff is a fifth-year PhD student at MIT. He received his master's in computer science, and B.S. degrees in both computer science and mathematics, all from MIT. He is interested in theoretical computer science, particularly algorithms, complexity theory, and cryptography.Hosted by David KempeRefreshments will be served.

Location: Seaver Science Library (SSL) - 150

Audiences: Everyone Is Invited

Contact: Nancy Levien