CSAIL Event Calendar

[A&C Seminar] Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy

A function f : D → R is Lipschitz if d_R(f(x), f(y)) ≤ d_D(x, y) for
all x, y in D, where d_R and d_D denote the distance metrics on the
range and domain of f , respectively. We initiate the study of testing
and local reconstruction of the Lipschitz property of functions. A
property tester has to distinguish functions with the property (in
this case, Lipschitz) from functions that differ from every function
with the property on many values. A local filter reconstructs a
desired property (in this case, Lipschitz) in the following sense:
given an arbitrary function f and a query x, it returns g(x), where
the resulting function g satisfies the property, changing f only when
necessary. If f has the property, g must be equal to f .

We design efficient testers and local reconstructors for functions
over domains of the form {1, . . . , n}^d , equipped with ell_1
distance, and give corresponding impossibility results. The algorithms
we design have applications to program analysis and data privacy. The
application to privacy is based on the fact that a function f of
entries in a database of sensitive information can be released with
noise of magnitude proportional to a Lipschitz constant of f, while
preserving the privacy of individuals whose data is stored in the
database (Dwork, McSherry, Nissim and Smith, TCC 2006). We give a
differentially private mechanism, based on local filters, for
releasing a function f when a purported Lipschitz constant of f is
provided by a distrusted client.

Based on a FOCS 2011 paper with S. Raskhodnikova and RANDOM 2012
papers with P. Awasthi, M. Molinaro and S. Raskhodnikova.

See other events happening in December 2012