On the optimality of gluing over scales

Abstract

We show that for every $\alpha >0$, there exist $n$-point metric spaces (X,d) where every "scale" admits a Euclidean embedding with distortion at most $\alpha$, but the whole space requires distortion at least $\Omega (\sqrt{\alpha \log n})$. This shows that the scale-gluing lemma [Lee, SODA 2005] is tight, and disproves a conjecture stated there. This matching upper bound was known to be tight at both endpoints, i.e. when $\alpha =\Theta (1)$ and $\alpha =\Theta (\log n)$, but nowhere in between. More specifically, we exhibit $n$-point spaces with doubling constant $\lambda$ requiring Euclidean distortion $\Omega (\sqrt{\log \lambda \log n})$, which also shows that the technique of "measured descent" [Krauthgamer, et. al., Geometric and Functional Analysis] is optimal. We extend this to obtain a similar tight result for $L_p$ spaces with $p>1$.

minor revisions

References in corpus (1)

• Measured descent: A new embedding method for finite metrics