This is a reference request. There is a large body of work, I'm familiar with, that describes the existence of bi-Hölder embeddings of finite metric spaces into Euclidean space (such as this snowflaking business in Assouad's theorem).


My question is: Given a finite metric space $(X,d\_X)$ are there known results outlining a (concrete) randomized algorithm for generating a bi-Hölder embedding of $f:(X,d\_X)\rightarrow \ell\_2^n$ into some suitably high-dimensional Euclidean space $\ell\_2^n$ which can be computed in random-polynomial time (or better) and estimates of the Hölder coefficients $C$ and $\alpha$,i.e.:
$$
C^{-1/\alpha}\|f^{-1}(x\_1)-f^{-1}(x\_2)\|^{1/\alpha}\leq 
d\_X(x\_1,x\_2)\leq C\|f(x\_1)-f(x\_2)\|^{\alpha}
$$


**Note:** There are of abstract existence results and [characterizations](https://mathoverflow.net/questions/12394/representability-of-finite-metric-spaces?rq=1) for metric spaces for which this is possible, but here I look for something concrete and implementable.



Bi-Hölder embeddings of finite metric spaces
The thing about Assouad's theorem is that the distortion of the embedding provided depends on the metric dimension of the space aka the doubling constant. If you take a Hamming cube which is a set $\{0,1\}^n$ considered with $L\_1$ metric and fix some $1/2 < a < 1$ then for any embedding $f:\{0,1\}^n \rightarrow L\_2$ the following holds
$$\sup\_{x \neq y \in \{0,1\}^d} \frac{||f(x) - f(y)||}{d\_X(x,y)^a}\sup\_{x \neq y \in \{0,1\}^d} \frac{d\_X(x,y)^a}{||f(x) - f(y)||} \ge C\_1n^{C\_2},$$
where $C\_1=C\_1(a) > 0, C\_2=C\_2(a) > 0$ are absolute constants depending only on $a$.


