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 l(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 et al., Theory of Cryptography, Lecture Notes in Comput. Sci. 3878, S. Halevi and T. Rabin, eds., Springer, Berlin, 2006, pp. 265-284]. 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.
reconstruction data privacy lipschitz constant property testing