Theory Seminar, October 19th, 2:00pm
Warren Weaver Hall, Room 1314

Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy.
Madhav Jha, Penn State University

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 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, McSherry, Nissim and Smith, TCC 2006). 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. Based on a FOCS 2011 paper with S. Raskhodnikova and RANDOM 2012 papers with P. Awasthi, M. Molinaro and S. Raskhodnikova.