Testing embeddability between metric spaces
Resource
Proceedings of Computing: The Australasian Theory Symposium (CATS), New SouthWales, Australia, January 22–25, 2008
International Journal of Foundations of Computer Science,20(2),313-329.
Journal
International Journal of Foundations of Computer Science
Journal Volume
20
Journal Issue
2
Pages
313-329
Date Issued
2009
Author(s)
Abstract
Let L < 1, ε > 0 be real numbers, (M, d) be a finite metric space and (N, ρ) be a metric space. A query to a metric space consists of a pair of points and asks for the distance between these points. We study the number of queries to metric spaces (M, d) and (N, ρ) needed to decide whether (M, d) is L-bilipschitz embeddable into (N, ρ) or ε-far from being L-bilipschitz embeddable into N, ρ). When (M, d) is ε-far from being L-bilipschitz embeddable into (N, ρ), we allow an o(1) probability of error (i.e., returning the wrong answer "L-bilipschitz embeddable"). However, no error is allowed when (M, d) is L-bilipschitz embeddable into (N, ρ). That is, algorithms with only one-sided errors are studied in this paper. When |M| ≤ |N| are both finite, we give an upper bound of $O(√ln |N|}{ε |M|}}\, (|M|2+|N|2))$ on the number of queries for determining with one-sided error whether (M, d) is L-bilipschitz embeddable into (N, ρ) or ε-far from being L-bilipschitz embeddable into (N, ρ). For the special case of finite |M| = |N|, the above upper bound evaluates to $O(|N|{3/2} {{{\ln |N|} \over \epsilon }} )$. We also prove a lower bound of Ω(|N|3/2) for the special case when |M| = |N| are finite and L = 1, which coincides with testing isometry between finite metric spaces. For finite |M| = |N|, the upper and lower bounds thus match up to a multiplicative factor of at most $√ln |N|}{ε}}$, which depends only sublogarithmically in |N|. We also investigate the case when (N, ρ) is not necessarily finite. Our results are based on techniques developed in an earlier work on testing graph isomorphism. © 2009 World Scientific Publishing Company.
Type
journal article