We show that for every nondecreasing concave function w:R+ --> R+ with
w(0)=0, either every finite metric space embeds with distortion arbitrarily
close to 1 into a metric space of the form (X,w o d) for some metric d on X, or
there exists a=a(w)>0 and n_0=n_0(w)\in N such that for all n>n_0, any
embedding of {0,...,n} into a metric space of the form (X,w o d) incurs
distortion at least n^a.
It is shown that if (X, ||.||_X) is a Banach space with Rademacher cotype q
then for every integer n there exists an even integer m< n^{1+1/q}$ such that
for every f:Z_m^n --> X we have \sum_{j=1}^n \Avg_x [ ||f(x+ (m/2) e_j)-f(x)
||_X^q ] < C m^q \Avg_{\e,x} [ ||f(x+\e)-f(x) ||_X^q ], where the expectations
are with respect to uniformly chosen x\in Z_m^n and \e\in \{-1,0,1\}^n, and all
the implied constants may depend only on q and the Rademacher cotype q constant
of X.
Given a finite regular graph G=(V,E) and a metric space (X,d_X), let
$gamma_+(G,X) denote the smallest constant $\gamma_+>0$ such that for all
f,g:V\to X we have:
\frac{1}{|V|^2}\sum_{x,y\in V} d_X(f(x),g(y))^2\le \frac{\gamma_+}{|E|}
\sum_{xy\in E} d_X(f(x),g(y))^2.
Given a finite regular graph G=(V,E) and a metric space (X,d_X), let
$gamma_+(G,X) denote the smallest constant $\gamma_+>0$ such that for all
f,g:V\to X we have:
\frac{1}{|V|^2}\sum_{x,y\in V} d_X(f(x),g(y))^2\le \frac{\gamma_+}{|E|}
\sum_{xy\in E} d_X(f(x),g(y))^2.
We present fast algorithms for constructing probabilistic embeddings and
approximate distance oracles in sparse graphs. The main ingredient is a fast
algorithm for sampling the probabilistic partitions of Calinescu, Karloff, and
Rabani in sparse graphs.