[Colloquium] Guest Speaker announcement

[Ponda Barnes]

Guest Speaker
 
Presented by: Toyota Technological Institute at Chicago
 
Speaker: David Woodruff
Speaker's home page:  http://web.mit.edu/dpwood/www/
 
Date: 3/21/07
Time: 10:00am
Location: TTI-C Conference room
 
Title: Efficient and Private Distance Approximation
 
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.  I will give a 1-round protocol
achieving optimal communication for this problem, up to logarithmic factors.
It can be implemented in the streaming model, and consequently resolves one
of the main open questions of a 1996 paper of Alon, Matias, and Szegedy.
 
Joint work with Piotr Indyk.
 
If you have any questions or would like to meet the speaker, please contact
Ponda Barnes at pondabarnes at tti-c.org.
For future TTI-C talks and events, please go to
http://ttic.uchicago.edu/cal/month.php
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20070321/df5d8fb4/attachment-0001.htm