Testing and reconstruction of lipschitz functions with applications to data privacy

Madhav Jha, Sofya Raskhodnikova

Research output: Contribution to journalArticlepeer-review

39 Scopus citations


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 dD 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 ℓ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.

Original languageEnglish (US)
Pages (from-to)700-731
Number of pages32
JournalSIAM Journal on Computing
Issue number2
StatePublished - 2013

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics


Dive into the research topics of 'Testing and reconstruction of lipschitz functions with applications to data privacy'. Together they form a unique fingerprint.

Cite this