Computer Science Colloquium
    GUEST TALK.  Note unusual hour  on Thursday 07/04/2011
Time+Place : Thursday 07/04/2011 15:00 room 337-8 Taub  Bld.
Speaker    : David Woodruff SPECIAL GUEST TALK.  Note unusual hour
Affiliation: IBM Almaden
Host       : Yuval Ishai
Title      : Near-Optimal Private Approximation Protocols via a
             Black Box Transformation
Abstract   :
A private approximation of a function f is defined to be another
function that approximates f in the usual sense, but does not reveal
any information about its input other than what can be deduced from
knowing the exact function value f.  In general it is insufficient to
use generic techniques in cryptography to design private
approximations from non-private approximations. This is because,
somewhat counterintuitively, the approximation may reveal more
information about the input than what the exact function value reveals
about the input. For example, the least-significant bit of a +- 1
approximation to the Hamming distance between two input vectors may be
set to equal a particular bit of an input vector.
We show the following general transformation: any two-party protocol
for outputting a (1+eps)-approximation to f(x,y) = sum_{j=1}^n g(x_j,
y_j) with constant probability, for any non-negative efficiently
computable function g, can be transformed into a two-party private
approximation protocol with only a polylogarithmic factor loss in
communication, computation, and round complexity. Applying our
transformation and variations of it, we obtain near-optimal private
approximation protocols for a wide range of problems in the data
stream literature for which previously nothing was known.
To appear in STOC, 2011.
Short Bio:
David Woodruff did his B.S. degrees in mathematics and computer
science, and his Ph.D. in theoretical computer science, each at MIT.
His advisor was Piotr Indyk. He graduated in 2007 and joined the
theory group at IBM Almaden as a Research Staff Member, where he has
been ever since.
Visit our home page-   <>
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <> 
Announcement from: Hadas Heier   <>