## Testing and Reconstruction of Lipschitz Functions with Applications to
Data Privacy

by Madhav Jha and Sofya Raskhodnikova

#### Oded's comments

I heard of this research direction from Sofya in January 2010,
but at that stage it was mainly a promising idea about a possible
application of local reconstruction to privacy presevation.
I have just learned that this direction has materialized,
and the result is the current paper (see Sec 1.2 and 5).
The initial observation is that one can preserve privacy w.r.t
queries that are Lipschitz functions, but hell may break loose
otherwise. The idea, then, is to ``filter'' the queries through
a reconstruction interface that preserves the functionality
of legitimate queries (corresponding to Lipschitz functions)
and modifies illegitimate queries to legitimate ones.
The point to stress is that this interface operates
without assuming anything on the syntax of legitiamte queries;
it rather operates on their semantics (or functionality).
This is done by running a (local) reconstruction algorithm
that maps functions to functions (such that Lipschitz functions
are mapped to themselves).

#### The original abstract

See ECCC TR11-057.

Back to
list of Oded's choices.