| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

10. Euclidean Distortion


    1. Add remark

      Problem 10.1.

      [Sasha Nikolov] For an $n$-point subset $M$ of a $d$-dimensional normed space, equipped with the $1/2$-snowflake metric, find, in polynomial time, a nonexpansive embedding of $M$ into $\ell_2$ with $O(\sqrt{\log d}$) average distortion.


        • Add remark

          Problem 10.2.

          [Assaf Naor] Suppose $M$ is an $n$-point metric space that embeds with distortion $D<\infty$ into a convex combination of dominating tree metrics. Is $c_2(M) = o_D(\sqrt{\log n})$?

              Cite this as: AimPL: Metric embeddings, available at http://aimpl.org/metricembeddings.