Robust models for property testing.

摘要

Property testing [Rubinfeld Sudan 96,Goldreich Goldwasser Ron 98] is a formal framework for studying approximate sublinear time randomized algorithms for decision problems. These algorithms have black-box query access to the input functions. Property testers are required to distinguish between functions that satisfy a given property from those that are 'far' from satisfying the property. Informally, a function is far from satisfying a given property if many function values need to be changed to satisfy the property. The notion of distance from a property is central to property testing. The distance of a function f : D → R from a property P is the smallest distance between f and any function g : D → R that satisfies P. One of the most widely studied model [Rubinfeld Sudan 96,Goldreich Goldwasser Ron 98] uses the relative Hamming distance as the notion of distance between two functions. That is, the distance between two functions f : D → R and g : D → R is the fraction of domain points on which f and g differ. A long line of work has been dedicated to the design and study of sublinear time algorithms for a number of function properties using this model.;This works focuses on studying practical generalizations of the aforementioned model. In the first part, we work with generalizing the notion of distance between functions. The relative Hamming distance can also be viewed as the distance between functions with respect to the uniform distribution. As part of our study, we design optimal testers for a large class of functions properties, called the bounded derivative properties, when the distance is measured with respect to a known or an unknown product distribution. The class of bounded derivative properties include well studied function properties like monotonicity and the Lipschitz property.;The second part of our work focuses on a generalization of the input access model. In many practical scenarios, a black-box access to the whole input function might not be possible. Some of the function values might not be available to the tester due to privacy requirements or adversarial erasures.We refer to such domain points as erased. The location of an erasure becomes known to the tester only upon querying the respective domain point. We design efficient erasure-resilient sublinear time testers for a large number of properties including the bounded derivative properties and convexity. Some of our testers are almost optimal, even in the case when a constant fraction of points are erased.