Nearly Tight Bounds on Testing of Metric Properties

Yiqiao Bao, Sampath Kannan, Erik Waingarten

Given a non-negative $n\times 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 t…