Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy

• Published in: SIAM journal on computing 2013-01, Vol.42 (2), p.700-731
• Main Authors: Jha, Madhav, Raskhodnikova, Sofya
• Format: Article
• Language: English
• Subjects: Algorithms; Computer science; Cryptography; Design engineering; Error correction & detection; Mathematical analysis; Mathematical models; Noise; Privacy; Reconstruction; Releasing
• ISSN: 0097-5397; 1095-7111
• DOI: 10.1137/110840741

A function $f : D \to R$ is Lipschitz if $d_R(f(x),f(y)) \leq 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,\ldots,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 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. [PUBLICATION ABSTRACT]