| 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 dR(f( x), f(y)) ≤ dD (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 investigate the Lipschitz property of functions under the wellstudied 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 ℓ1 distance, and give corresponding impossibility results. The algorithms we design have applications to data privacy and program analysis. |
