bilipschitz snowflakes and metrics of negative type
We show that there exists a metric space (X,d) such that (X,?d) admits a bilipschitz embedding into L 2 , but (X,d) does not admit an equivalent metric of negative type. In fact, we exhibit a strong quantitative bound: There are n-point subsets Y n ? X such that mapping (Y n , d) to a metric of negative type requires distortion ~?(log n) 1/4 . In a formal sense, this is the first lower bound specifically against bilipschitz embeddings into negative-type metrics, and therefore unlike other lower bounds, ours cannot be derived from a 1-dimensional Poincare inequality. This answers an open question about the strength of strong vs. weak triangle inequalities in a number of semi-definite programs. Our construction sheds light on the power of various notions of "dual flows" that arise in algorithms for approximating the Sparsest Cut problem. It also has other interesting implications for bilipschitz embeddings of finite metric spaces.
semi-definite programming sparsest cut metric embeddings