On the optimality of gluing over scales

Details On the optimality of gluing over scales On the optimality of gluing over scales

2009-10-01

arxiv.org/abs/0910.0277v3

Mathematics

Metric Geometry

minor revisions

Scientific paper

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$.

Affiliated with

Also associated with

No associations

Rating

On the optimality of gluing over scales does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the optimality of gluing over scales, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the optimality of gluing over scales will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-25633