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.