Abstract:
A standard property testing algorithm is required to determine with high probability whether a given object has property P or whether it is \epsilon-far from having P, for any given distance parameter \epsilon. An object is said to be \epsilon-far from having property P if at least an \epsilon-fraction of the object should be modified so that it obtains P. In this paper we study a generalization of standard property testing where the algorithms are required to be more *tolerant*. Specifically, a tolerant property testing algorithm is required to accept objects that are \epsilon_1-close to having a given property P and reject objects that are \epsilon_2-far from having P, for some parameters 0 <= \epsilon_1 < \epsilon_2 <= 1. Another related natural extension of standard property testing that we study, is distance approximation. Here the algorithm should output an estimate \hat{\epsilon} of the distance of the object to P, where there are certain provable upper and lower bounds on \hat{\epsilon} in terms of the correct distance. We first formalize the notions of tolerant property testing and distance approximation and discuss the relationship between the two tasks, as well as their relationship to standard testing. We then study two problems: The first is distance approximation for monotonicity, and the second is tolerant testing of clustering. We present and analyze algorithms whose query complexity is either polylogarithmic or independent of the size of the input. Our distance approximation algorithm for monotonicity works by defining a certain tree structure by which upper and lower bounds on the distance of the function to monotonicity can be obtained, and then constructing only a small number of random paths in the tree. Our tolerant testing algorithms for clustering for tolerant testing of other cost measures for clustering, as well as for tolerant testing of other properties.