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.