Property testing and reconstruction with applications to data privacy
Open Access
- Author:
- Jha, Madhav
- Graduate Program:
- Computer Science and Engineering
- Degree:
- Doctor of Philosophy
- Document Type:
- Dissertation
- Date of Defense:
- April 24, 2013
- Committee Members:
- Sofya Raskhodnikova, Dissertation Advisor/Co-Advisor
Sofya Raskhodnikova, Committee Chair/Co-Chair
Piotr Berman, Committee Member
Martin Furer, Committee Member
Jason Ryder Morton, Committee Member - Keywords:
- property testing
property reconstruction
Lipschitz function
sublinear algorithms
data privacy - Abstract:
- The Lipschitz property is a fundamental property of functions with many applications in mathematics and computer science. Intuitively, a function is Lipschitz if it is not too sensitive to small changes in its inputs. In various applications, it is important (often crucial) that the input function satisfies the Lipschitz property. Given query access to a function, can we test that it is Lipschitz? Better still, can we restore or reconstruct the Lipschitz property in a (possibly non-Lipschitz) function by modifying it suitably? In this thesis, we initiate the study of testing and reconstruction of the Lipschitz property of functions. Our primary motivation for studying the Lipschitz property stems from its applications to data privacy. Formally, 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 investigate the Lipschitz property of functions under the well- studied model of property testing (Rubinfeld and Sudan; Goldreich, Goldwasser and Ron) and local property reconstruction (Ailon, Chazelle, Comandur and Liu; Saks and Seshadhri). 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 reconstructor restores 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 (or at least “close”) to f . We design efficient testers and local reconstructors for functions over domains of the form {1, . . . , n}^d, equipped with l1 distance, and give corresponding impossibility results. The algorithms we design have applications to data privacy and program analysis.