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.