Testing metric properties

Finite metric spaces, and in particular tree metrics play an important role in various disciplines such as evolutionary biology and statistics. A natural family of problems concerning metrics is deciding, given a matrix M, whether or not it is a distance metric of a certain predetermined type. Here we consider the following relaxed version of such decision problems: For any given matrix M and parameter ϵ, we are interested in determining, by probing M, whether M has a particular metric property P, or whether it is ϵ-far from having the property. In ϵ-far we mean that at least an ϵ-fraction of the entries of M must be modified so that it obtains the property. The algorithm may query the matrix on entries M[i, j] of its choice, and is allowed a constant probability of error. We describe algorithms for testing Euclidean metrics, tree metrics and ultrametrics. Furthermore, we present an algorithm that tests whether a matrix M is an approximate ultrametric. In all cases the query complexity and running time are polynomial in 1/ϵ and independent of the size of the matrix. Finally, our algorithms can be used to solve relaxed versions of the corresponding search problems in time that is sub-linear in the size of the matrix.

Authors

• Michal Parnas
• Dana Ron

Keywords

No keywords are indexed for this paper.