Logo: University of Southern California

Events Calendar


  • Efficient and Private Distance Approximation

    Mon, Mar 26, 2007 @ 03:30 PM - 05:00 PM

    Thomas Lord Department of Computer Science

    Conferences, Lectures, & Seminars


    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

    Add to Google CalendarDownload ICS File for OutlookDownload iCal File

Return to Calendar