Tolerant property testing and distance approximation

摘要

In this paper we study a generalization of standard property testing where the algorithms are required to be more tolerant with respect to objects that do not have, but are close to having, the property. Specifically, a tolerant property testing algorithm is required to accept objects that are ϵ1-close to having a given property P and reject objects that are ϵ2-far from having P, for some parameters 0⩽ϵ1<ϵ2⩽1. Another related natural extension of standard property testing that we study, is distance approximation. Here the algorithm should output an estimate ϵˆ of the distance of the object to P, where this estimate is sufficiently close to the true distance of the object to P. 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 property testing. We then apply these new notions to the study of two problems: tolerant testing of clustering and distance approximation for monotonicity. We present and analyze algorithms whose query complexity is either polylogarithmic or independent of the size of the input.