TR04-010 Authors: Michal Parnas, Dana Ron, Ronitt Rubinfeld

Publication: 2nd February 2004 22:28

Downloads: 1885

Keywords:

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.