Nearly Tight Bounds on Testing of Metric Properties

Given a non-negative n × n matrix viewed as a set of distances between n points, we consider the property testing problem of deciding if it is a metric. We also consider the same problem for two special classes of metrics -tree metrics and ultrametrics. For general metrics, our paper is the first to consider these questions. We prove an upper bound of O(n 2/3 /ε 4/3 ) on the query complexity for this problem. Our algorithm is simple, but the analysis requires great care in bounding the variance on the number of violating triangles in a sample. When ε is a slowly decreasing function of n (rather than a constant, as is standard), we prove a lower bound of matching dependence on n of Ω(n 2/3 ), ruling out any property testers with o(n 2/3 ) query complexity unless their dependence on 1/ε is super-polynomial.

Next, we turn to tree metrics and ultrametrics. While there were known upper and lower bounds, we considerably improve these bounds showing essentially tight bounds of Õ(1/ε) on the sample complexity. We also show a lower bound of Ω(1/ε 4/3 ) on the query complexity. Our upper bounds are derived by doing a more careful analysis of a natural, simple algorithm. For the lower bounds, we construct distributions on NO instances, where it is hard to find a witness showing that these are not ultrametrics.