The distortion of an embedding $f$ from one metric space $\Bbb{X} = (X,ϱ_X)$ into a metric space $\Bbb{Y} = (Y,ϱ_Y)$ is the smallest value $D \ge 1$ such that there exists $α> 0$ for which $$αϱ_X(x,y) \le ϱ_Y(f(x),f(y)) \le Dαϱ_X(x,y)$$ for all $x$, $y \in X$. Denote by $c_{\Bbb{Y}}(\Bbb{X})$ the infimum of all distortions for embeddings of $\Bbb{X}$ into $\Bbb{Y}$. This article considers the problem of embedding or approximating $c_{\Bbb{Y}}(\Bbb{X})$ in the case of a finite metric space $\Bbb{X}$ and $\Bbb{Y} = \Bbb{R}^d$. Generalizing a result by {\it M.~Bădoiu, J.~Chuzhoy, P.~Indyk,} and {\it A.~Sidiropoulos} [in: STOC’05. Proceedings of the 37th annual ACM symposium on theory of computing. New York, NY: Association for Computing Machinery (ACM) (2005; Zbl 1192.68342)] to an arbitrary but fixed dimension $d \ge 2$, it is shown that it is NP-hard to approximate the minimum distortion required for the embedding of an $n$-point metric space into $\Bbb{R}^d$ within a factor of $Ω(n^{1/(22d-10)-ε})$. Here, $ε> 0$ is a given constant. For $d \ge 3$ it is NP-hard to distinguish between $n$-point metric spaces that embed in $\Bbb{R}^d$ with distortion at most $D_0$ and spaces that require distortion at least $n^{c/d}$ where $c > 0$ is a universal constant and $D_0$ is a constant depending on the dimension~$d$.
Reviewer: Hans-Peter Schröcker (Innsbruck)