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

5. Low Dimensional and Sparse Embeddings


    1. Add remark

      Problem 5.1.

      [Alexandros Eskenazis] Set $d(n)$ to be the minimal integer $d$ with the property that every $n$-point metric space isometrically embeds into $\ell_\infty^d$. What are the asymptotics of $n - d(n)$?


        • Add remark

          Problem 5.2.

          [Dylan Altschuler] For each $\alpha > 1, n \in \mathbb{N}$, let $k^n_\alpha$ denote the minimal $k$ such that every $n$-point metric space embeds with distortion $\alpha$ into some $k$-dimensional normed space. What is the behavior of $k_\alpha^n$ when $\frac{\log n}{\log\log n} \leq \alpha \leq \log n \cdot \log\log n$?


            • Add remark

              Problem 5.3.

              [Assaf Naor] Does every $n$-point subset of $\ell_1$ embed with average distortion $1+\varepsilon$ into $\ell_1^d$, where $d = O_\varepsilon(\log n)$?


                • Add remark

                  Problem 5.4.

                  [Alex Andoni] Fix a distortion $c<\infty$ and dimension $d<\infty$. Let $M$ be an $n$-point subset of $\ell_1^d$ (or $\ell_\infty^d$). What is the least number of edges needed for a (weighted) graph to admit an embedding of $M$ with distortion $c$ (in terms of $c,d$)?

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