Testing and reconstruction of lipschitz functions with applications to data privacy

A function f : D → R is Lipschitz if dR(f(x), f(y)) ≤ d _D(x,y) for all x, y in D, where dR 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 ℓ₁ 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.