PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 00, Number 0, Pages 000–000 S 0002-9939(XX)0000-0

SOME APPLICATIONS OF BALL’S EXTENSION THEOREM

MANOR MENDEL AND ASSAF NAOR

(Communicated by David Preiss)

Abstract. We present two applications Ball’s extension theorem. First we observe that Ball’s extension theorem, together with the recent solution of Ball’s Markov type 2 problem due to Naor, Peres, Schramm and Sheffilield, imply a generalization, and an alternative proof of, the Johnson-Lindenstrauss extension theorem. Secondly, we prove that the distortion required to embed the integer lattice {0, 1, …, m}^{n}, equipped with the ℓ_{p}^{n} metric, in any 2-uniformly convex Banach space is of order min \{n^{\frac{1}{2} − \frac{1}{p}} , m^{1− \frac{2}{p}} \}.

1. Introduction

Let (Y, d_{Y}), (Z, d_{Z}) be metric spaces, and for every X ⊆ Y, denote by e(X, Y, Z) the infimum over all constants K such that every Lipschitz function f : X → Z can be extended to a function f̃: Y → Z satisfying ∥f̃∥_{Lip} ≤ K∥f∥_{Lip}. (If no such K exists, we set e(X, Y, Z) = ∞). We also define e(Y, Z) = sup{e(X, Y, Z) : X ⊆ Y } and for every integer n, e_{n}(Y, Z) = sup{e(X, Y, Z) : X ⊆ Y, |X| ≤ n}. We refer to [11, 13, 22] and the references therein for a discussion of the rich history and many results dealing with these notions.

The investigation of these parameters has often involved the introduction of influential probabilistic tools. The first result on the parameter e_{n}(X, Y) is due to Marcus and Pisier [16], who used the theory of stable processes to show that for every 1 < p ≤ 2, e_{n}(L_{p}, L_{2}) = O ((log n)^{\frac{1}{p} − \frac{1}{2}} ). Johnson and Lindenstrauss [9]

have shown that for every metric space X, e_{n}(X, L_{2}) = O(\sqrt{log n}), and that

e_{n}(L_{1}, L_{2}) = Ω (\sqrt{\frac{log n}{log log n}}). Their paper used the method of random projections, and contained the celebrated Johnson-Lindenstrauss dimension reduction lemma, which has since found numerous applications in asymptotic geometry and theoretical computer science (see the monograph [27]). The best known general upper bound is due to Lee and Naor [11, 13], who used random partitions of metric spaces to show that for every metric space X and every Banach space Z, e_{n}(X, Z) = O (\frac{log n}{log log n}).

In an important paper, K. Ball [1] discovered a striking connection between the behavior of Markov chains in metric spaces and the Lipschitz extension problem. In

\begin{matrix}c \\ ◯ \end{matrix}2005 American Mathematical Society

Received by the editors January 27, 2005 and, in revised form, March 18, 2005.

2000 Mathematics Subject Classification. Primary 46B20; Secondary 51F99.

Key words and phrases. Lipschitz extension, bi-Lipschitz embeddings.

particular, he introduced the notion of Markov type, and used it to prove a fundamental extension criterion. This criterion, in combination with the recent solution of Ball’s Markov type 2 problem due to Naor, Peres, Schramm and Sheffield [22], yields the following extension theorem:

Theorem 1.1. For every 2 ≤ p < ∞ and every 2-uniformly convex Banach space Y,

e(L_{p}, Y) ≤ 24K_{2}(Y)\sqrt{p − 1}.

(Recall that a Banach space Y is said to be 2-uniformly convex with constant K if for every x, y ∈ Y,

2∥x∥^{2} + \frac{2}{K^{2}} ∥y∥^{2} ≤ ∥x + y∥^{2} + ∥x − y∥^{2}.

The least such K is called the 2-uniform convexity constant of Y, and is denoted K_{2}(Y). See [14, 2] for a discussion of this notion.)

Several applications of Theorem 1.1 to the theory of Lipschitz extensions and the theory of bi-Lipschitz embeddings were presented in [22]. In this note we present additional applications of Theorem 1.1 to both of these theories. Our first observation is that the fact that L_{p}, p > 2, has Markov type 2 with constant O(\sqrt{p}) (proved in [22]) answers positively a question posed by K. Ball in [1], showing that indeed the Markov type approach to Lipschitz extension introduced in [1] gives an alternative proof of the Johnson-Lindenstrauss extension theorem [9]. Moreover, this approach yields a significant generalization of this theorem to the case when the target space is an arbitrary 2-uniformly convex Banach space. Although this is a rather straightforward corollary of the results of [1, 22], we believe that it is worthwhile to point out an alternative approach to the Johnson-Lindenstrauss extension theorem which does not depend on dimension reduction (especially since it is known that Johnson-Lindenstrauss type dimension reduction is not always possible [7, 12, 10]).

Our second application of Theorem 1.1 is to the problem of embedding the integer lattice into 2-uniformly convex normed spaces, improving a result of Bourgain [5]. Our main result is that if Y is an infinite dimensional 2-uniformly convex Banach space, p > 2, and m, n are integers, then the distortion required to embed the integer lattice \{0, …, m\}^{n}, equipped with the ℓ_{p}^{n} metric, is Θ (min \{n^{\frac{1}{2} − \frac{1}{p}} , m^{1− \frac{2}{p}} \}). This shows that up to constants which may depend only on p, the optimal embedding of the integer lattice is the better of two natural embeddings: the identity map and a natural snowflake-type embedding à la Schoenberg (the phase transition occurs at m = \sqrt{n}. See Section 3 for more details).

2. A generalization of the Johnson-Lindenstrauss theorem

The main purpose of this section is to present a very simple proof of the following strengthning of the Johnson-Lindenstrauss extension theorem:

Theorem 2.1. Let Y be a 2 uniformly convex Banach space. Then for every metric space X and every n ∈ ℕ

e_{n}(X, Y) ≤ 60K_{2}(Y)\sqrt{log n}.

Proof. Fix A = {a_{1}, …, a_{n}} ⊆ X and f : A → Y. Consider the Fréchet map F : X → ℓ_{∞}^{n} given by

F(x) = (d(x, a_{1}), d(x, a_{2}), …, d(x, a_{n})).

Then F|_{A} is easily seen to be an isometry (see [4, Lemma 1.1]), and ∥F∥_{Lip} ≤ 1. Fix p > 2. By Hölder’s inequality the identity mappings Id_{∞→p} : ℓ_{∞}^{n} → ℓ_{p}^{n} and Id_{p→∞} : ℓ_{p}^{n} → ℓ_{∞}^{n} satisfy ∥Id_{∞→p}∥_{Lip} ≤ n^{1/p}, ∥Id_{p→∞}∥_{Lip} ≤ 1. The mapping g : Id_{∞→p} ∘ F(A) → Y given by g = f ∘ (F|_{A})^{−1} ∘ Id_{p→∞} can be extended using Theorem 1.1 to a mapping g̃ : ℓ_{p}^{n} → Y with ∥g̃∥_{Lip} ≤ 24K_{2}(Y)\sqrt{p} · ∥g∥_{Lip} ≤ 24K_{2}(Y)\sqrt{p} · ∥f∥_{Lip}. Define f̃: X → Y by f̃ = g̃ ∘ Id_{∞→p} ∘ F. Then f̃ extends f and ∥f̃∥_{Lip} ≤ 24K_{2}(X)\sqrt{p} · n^{1/p} · ∥f∥_{Lip}. Choosing p = 2 log n yields the required result. □

Remark 2.2. A similar argument shows that for every 2 ≤ p < ∞,

e_{n}(L_{p}, L_{1}) ≤ 10\sqrt{p log n}.

Indeed, fix A = {a_{1}, …, a_{n}} ⊆ L_{p} and f : A → L_{1}. Denote Z = span(f(A)). Then dim(Z) ≤ n, so that by a theorem of Talagrand [25] there is an invertible linear mapping T : Z → ℓ_{1}^{m} such that ∥T ∥_{Lip} = 1 and ∥T^{−1}∥_{Lip} ≤ 2, where m = O(n log n). For 1 < q ≤ 2 the identity mappings Id_{1→q} : ℓ_{1}^{m} → ℓ_{q}^{m} and Id_{q→1} : ℓ_{q}^{m} → ℓ_{1}^{m} satisfy ∥Id_{1→q}∥_{Lip} ≤ 1 and ∥Id_{q→1}∥_{Lip} ≤ m^{1−1/q}. The Banach space W := Id_{1→q} ∘ T (Z) is a subspace of ℓ_{q}^{m}, so that K_{2}(W) ≤ 1/\sqrt{q − 1} (see [2]). The mapping h : A → W given by h = Id_{1→q} ∘ T ∘ f can be extended using Theorem 1.1 to a mapping h̃ : L_{p} → W such that ∥h̃∥_{Lip} ≤ 24\sqrt{p − 1} · K_{2}(W) ·

∥h∥_{Lip} ≤ 24\sqrt{\frac{p−1}{q−1}} · ∥f∥_{Lip}. The mapping f̃ := T^{−1} ∘ Id_{q→1} ∘ h̃ : L_{p} → Z ⊆ L_{1} extends f and satisfies

∥f̃∥_{Lip} ≤ 48 · m^{1−1/q}\sqrt{\frac{p − 1}{q − 1}} · ∥f∥_{Lip} = O (\frac{(n log n)^{1−1/q}\sqrt{p}}{\sqrt{q − 1}}) · ∥f∥_{Lip}.

Choosing q = 1 + \frac{1}{log n} yields the required result.

Remark 2.3. Using the arguments in [21] it is possible to prove variants of Theorem 2.1 which deal with extensions of Hölder functions. For example, for every metric space (X, d) and α ∈ (0, 1] let X^{α} denote the metric space (X, d^{α}). A combination of the above proof and [21] shows that for q ≥ 2, and every metric space X, e_{n}(X^{2/q}, L_{q}) = O((log n)^{1/q}).

3. Embedding the integer lattice into uniformly convex spaces

Given two metric spaces X, Y and an injection f : X ↪ Y we define the distortion of f to be dist(f) = ∥f∥_{Lip} · ∥f^{−1}∥_{Lip}. The least distortion with which X may be embedded into Y is denoted c_{Y} (X) = inf{dist(f) : f : X ↪ Y }. When Y = L_{p} we write c_{Y} (X) = c_{p}(X). The parameter c_{2}(X) is called the Euclidean distortion of X.

We recall the notions of type and cotype of a Banach space X: we say that X has type p if for every x_{1}, …, x_{n} ∈ X,

(∫_{{−1,1}^{n}} ∥∑_{j=1}^{n} ε_{j}x_{j}∥^{2} dε)^{1/2} ≤ T (∑_{j=1}^{n} ∥x_{j}∥^{p})^{1/p} .

The least such constant T is called the type p constant of X, and is denoted T_{p}(X). X is said to have cotype q if for every x_{1}, …, x_{n} ∈ X,

(∫_{\{−1,1\}^{n}} ∥∑_{j=1}^{n} ε_{j}x_{j}∥^{2} dε)^{1/2} ≥ \frac{1}{C} (∑_{j=1}^{n} ∥x_{j}∥^{p})^{1/p} .

The least such constant C is called the cotype q constant of X, and is denoted C_{q}(X). It is well known that C_{2}(X) ≤ K_{2}(X) (see for example [14]).

Fix p ≥ 1, and two integers m, n ∈ ℕ. We denote by [m]_{p}^{n} the set {0, 1, …, m}^{n} equipped with the metric induced by ℓ_{p}^{n}. We first deal with the case 2 ≤ p ≤ ∞ (the case p ∈ [1, 2] is discussed below). Observe that for every x, y ∈ [m]_{p}^{n},

∥x − y∥_{2}^{2/p} = (∑_{j=1}^{n}(x_{j} − y_{j})^{2})^{1/p} ≤ (∑_{j=1}^{n} |x_{j} − y_{j}|^{p})^{1/p} ≤ m^{1− \frac{2}{p}} · ∥x − y∥_{2}^{2/p}.

By a theorem of Schoenberg (see for example [28]), ℝ^{n} equipped with the metric ∥x − y∥_{2}^{2/p} is isometric to a subset of L_{2}. Thus we have shown that c_{2} ([m]_{p}^{n}) ≤ m^{1− \frac{2}{p}}. Additionally, by Hölder’s inequality, the identity mapping between ℓ_{p}^{n} and ℓ_{2}^{n} is n^{\frac{1}{2} − \frac{1}{p}} bi-Lipschitz. This shows that

c_{2} ([m]_{p}^{n}) ≤ min \{n^{\frac{1}{2} − \frac{1}{p}} , m^{1− \frac{2}{p}} \} .

This bound on the Euclidean distortion of the integer lattice, in combination with Dvoretzky’s theorem (see [20]), implies the following fact:

Fact 3.1. Let Y be an infinite dimensional Banach space. Then for every p ≥ 2

c_{Y} ([m]_{p}^{n}) ≤ min \{n^{\frac{1}{2} − \frac{1}{p}} , m^{1− \frac{2}{p}} \} .

The main result of this section is a matching lower bound for 2-uniformly convex spaces. The proof is a modification of an argument of Bourgain [5], combined with Theorem 1.1.

Theorem 3.2. Let Y be a 2-uniformly convex Banach space. Then for every 2 ≤ p < ∞,

c_{Y} ([m]_{p}^{n}) ≥ \frac{1}{400K_{2}(Y)^{2}\sqrt{p}} · min \{n^{\frac{1}{2} − \frac{1}{p}} , m^{1− \frac{2}{p}} \} .

Proof. Let f : [m]_{p}^{n} → Y be a one to one mapping with ∥f∥_{Lip} = L and ∥f^{−1}∥_{Lip} = 1. Assume first of all that m ≥ 4\sqrt{n} (which implies that m^{1− \frac{2}{p}} ≥ n^{\frac{1}{2} − \frac{1}{p}}). We may assume in this case that L ≤ \frac{m}{200K_{2}(Y)n^{1/p}\sqrt{p}}, since otherwise the required result holds true.

By Theorem 1.1 f can be extended to a function f̃ : ℓ_{p}^{n} → Y with ∥f̃∥_{Lip} ≤ 24K_{2}(Y)\sqrt{p} · L. By Rademacher’s theorem (see e.g. [4]) f̃ is differentiable almost everywhere. Let x ∈ ℓ_{p}^{n} be a point of differentiability of f̃ and ε ∈ {−1, 1}^{n}. Then

∥ \frac{d}{dt}|_{t=0} f̃(x + tε)∥_{Y} = lim_{t→0} \frac{∥f̃(x + tε) − f̃(x)∥_{Y}}{|t|}
≤ ∥ε∥_{p} · ∥f̃∥_{Lip}
≤ 24n^{1/p}K_{2}(Y)L\sqrt{p}.

On the other hand,

∫_{\{−1,1\}^{n}} ∥ \frac{d}{dt}|_{t=0} f̃(x + tε)∥_{Y}^{2} dε = ∫_{\{−1,1\}^{n}} ∥∑_{j=1}^{n} ε_{j} \frac{∂}{∂x_{j}} f̃(x)∥_{Y}^{2} dε

≥ \frac{1}{C_{2}(Y)^{2}} ∑_{j=1}^{n} ∥\frac{∂}{∂x_{j}} f̃(x)∥_{Y}^{2} .

Using the fact that C_{2}(Y) ≤ K_{2}(Y), and integrating with respect to x ∈ [0, m]^{n} we deduce that

∑_{j=1}^{n} \frac{1}{m^{n}} ∫_{[0,m]^{n}} ∥\frac{∂}{∂x_{j}} f̃(x)∥_{Y}^{2} dx ≤ 576pn^{2/p}L^{2}K_{2}(Y)^{4}. (3.1)

Fix an integer j ∈ {1, …, n}. For every x = (x_{1}, …, x_{n}) ∈ [0, m]^{n} there are a, b ∈ [m]_{p}^{n} such that

∥a − (x_{1}, …, x_{j−1}, m, x_{j+1}, …, x_{n})∥_{p} ≤ n^{1/p},

and

∥b − (x_{1}, …, x_{j−1}, 0, x_{j+1}, …, x_{n})∥_{p} ≤ n^{1/p}.

In particular it follows that ∥a − b∥_{p} ≥ m − 2n^{1/p}. Now, since f̃ extends f we have that

∥f̃(x_{1}, …, x_{j−1}, m, x_{j+1}, …, x_{n}) − f̃(x_{1}, …, x_{j−1}, 0, x_{j+1}, …, x_{n})∥_{Y}
≥ ∥f̃(a) − f̃(b)∥_{Y} −
∥f̃(a) − f̃(x_{1}, …, x_{j−1}, m, x_{j+1}, …, x_{n})∥_{Y} −
∥f̃(b) − f̃(x_{1}, …, x_{j−1}, 0, x_{j+1}, …, x_{n})∥_{Y}
≥ m − 2n^{1/p} − 2∥f̃∥_{Lip} · n^{1/p}
(3.2)  ≥ \frac{m}{4},

where we have used our assumption that L ≤ \frac{m}{200K_{2}(Y)n^{1/p}\sqrt{p}}. On the other hand,

∥f̃(x_{1}, …, x_{j−1}, m, x_{j+1}, …, x_{n}) − f̃(x_{1}, …, x_{j−1}, 0, x_{j+1}, …, x_{n})∥_{Y}

= ∥∫_{0}^{m} \frac{∂}{∂x_{j}} f̃(x_{1}, …, x_{j−1}, s, x_{j+1}, …, x_{n}) ds∥_{Y}
≤ ∫_{0}^{m} ∥\frac{∂}{∂x_{j}} f̃(x_{1}, …, x_{j−1}, s, x_{j+1}, …, x_{n})∥_{Y} ds

≤ \sqrt{m · ∫_{0}^{m} ∥\frac{∂}{∂x_{j}} f̃(x_{1}, …, x_{j−1}, s, x_{j+1}, …, x_{n})∥_{Y}^{2} ds}.

Squaring this inequality, integrating with respect to x_{1}, …, x_{j−1}, x_{j+1}, …, x_{n}, and using (3.2), we get that

\frac{1}{m^{n}} ∫_{[0,m]^{n}} ∥\frac{∂}{∂x_{j}} f̃(x)∥_{Y}^{2} dx ≥ \frac{1}{16}.

Plugging this estimate into (3.1) we see that

\frac{n}{16} ≤ 576pn^{2/p}L^{2}K_{2}(Y)^{4},

or

L ≥ \frac{n^{\frac{1}{2} − \frac{1}{p}}}{96K_{2}(Y)^{2}\sqrt{p}},

implying the required result.

It remains to deal with the case m ≤ 4\sqrt{n}, but in this case [m]_{p}^{n} contains an

isometric copy of [m]_{p}^{⌊m^{2}/16⌋} for so that the required result follows from the previous argument. □

We end this section with some remarks and open problems.

Remarks.

(1) For p ∈ [1, 2] we have that c_{q}([m]_{p}^{n}) = 1 for every q ∈ [1, p], since ℓ_{p} embeds isometrically into L_{q} in this case (see for example [28]). More generally, by the Maurey-Pisier theorem [18, 20]), for an infinite dimensional Banach space Y satisfying sup{q : Y has type q} ≤ p we have that c_{Y} ([m]_{p}^{n}) = 1. Observe that for m ≥ 1, [m]_{p}^{n} contains an isometric copy of {0, 1}^{n}. Thus, by a theorem of Enflo [8], if q ∈ [p, 2] then c_{q}([m]_{p}^{n}) = n^{\frac{1}{p} − \frac{1}{q}}, where the upper bound c_{q}([m]_{p}^{n}) ≤ n^{\frac{1}{p} − \frac{1}{q}} follows from Hölder’s inequality. More

generally, if Y has type q ∈ [p, 2] then c_{q}([m]_{p}^{n}) ≥ ^{\frac{cn^{\frac{1}{p} − \frac{1}{q}}}{log n}} , where c is a universal constant. This follows from a result of Pisier [24] (see also an earlier slightly weaker result of Bourgain, Milman and Wolfson [6]). If we assume that Y has type q ∈ [p, 2] and that Y has the UMD property (see [23] for the definition), then the results of Naor and Schechtman [23] imply that c_{Y} ([m]_{p}^{n}) ≥ C(Y)n^{\frac{1}{p} − \frac{1}{q}}, where the constant C(Y) depends only on the UMD constant of Y. In particular, for 2 ≤ q < ∞ we get that c_{q}([m]_{p}^{n}) ≥ C(q)n^{\frac{1}{p} − \frac{1}{2}} , and this is optimal (up to constants depending only on q) since the Banach-Mazur distance between ℓ_{p}^{n} and ℓ_{q}^{n} is of order n^{\frac{1}{p} − \frac{1}{2}} (see [26]).

(2) For the ℓ_{∞} integer lattice we can take p = log (min{m, n}) in Theorem 3.2 to get that

c_{Y} ([m]_{∞}^{n}) ≥ \frac{1}{400K_{2}(Y)^{2}} · min \{\sqrt{\frac{n}{log n}}, \frac{m}{\sqrt{log m}}\} .

We conjecture that this lower bound is not optimal, namely that whenever Y is a 2-uniformly convex Banach space, c_{Y} ([m]_{p}^{n}) = Ω(min\{\sqrt{n}, m\}). In [5] Bourgain shows that if Y has cotype q then c_{Y} ([m]_{∞}^{m}) = Ω(n^{1/q}), provided that m ≥ n^{1+1/q}. Thus, the above conjecture is true for m ≥ n^{3/2}. The results of [15, 17] imply that there exist arbitrarily large n-point metric spaces X_{n} (namely expander graphs) with the property that for every x, y ∈ X_{n}, d(x, y) ∈ [1, 10 log n], and for p ≥ 1, c_{p}(X_{n}) = Ω (\frac{log n}{p}). Using the Fréchet embedding, we can embed X_{n} isometrically into ℓ_{∞}^{n}. Moreover, since the distances in X_{n} are in the range [1, 10 log n], we can embed X_{n} with distortion 2, say, into [⌈20 log n⌉]_{∞}^{n}. Thus, it follows that c_{p}([m]_{∞}^{n}) = Ω(m/p), at least for m ≤ 20 log n.

(3) A natural approach to the above conjecture would be to show that for a 2uniformly convex space Y, any Lipschitz mapping from [m]_{∞}^{n} into Y can be extended to ℓ_{∞}^{n} with only a universally bounded multiplicative loss in the Lipschitz constant. The above argument shows that this would imply that c_{Y} ([m]_{∞}^{n}) = Ω(min\{\sqrt{n}, m\}), and it would improve the results of [5, 3].

(4) The lower bounds on distortion which were presented in this paper do not belong to the usual type of non-embeddability results, since they are not based on Poincaré type inequalities. In our forthcoming paper [19] we introduce a family of Poincaré type inequalities which can be used to prove non-embeddability results for the integer lattice, and which are a non-linear analogue of the notion of cotype. We defer the discussion on this (more complicated) argument to [19], but we wish to state that it shows in particular that at least for Hilbert space, c_{2}([m]_{∞}^{n}) = Θ(min\{\sqrt{n}, m\}).

References

1. K. Ball. Markov chains, Riesz transforms and Lipschitz maps. Geom. Funct. Anal., 2(2):137– 172, 1992.

2. K. Ball, E. A. Carlen, and E. H. Lieb. Sharp uniform convexity and smoothness inequalities for trace norms. Invent. Math., 115(3):463–482, 1994.

3. B. Begun. A remark on almost extensions of Lipschitz functions. Israel J. Math., 109:151–155, 1999.

4. Y. Benyamini and J. Lindenstrauss. Geometric nonlinear functional analysis. Vol. 1, volume 48 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2000.

5. J. Bourgain. Remarks on the extension of Lipschitz maps defined on discrete sets and uniform homeomorphisms. In Geometrical aspects of functional analysis (1985/86), volume 1267 of Lecture Notes in Math., pages 157–167. Springer, Berlin, 1987.

6. J. Bourgain, V. Milman, and H. Wolfson. On type of metric spaces. Trans. Amer. Math. Soc., 294(1):295–317, 1986.

7. B. Brinkman and M. Charikar. On the impossibility of dimension reduction in ℓ_{1}. In Proceedings of the 44th Annual IEEE Conference on Foundations of Computer Science. ACM, 2003.

8. P. Enflo. On the nonexistence of uniform homeomorphisms between L_{p}-spaces. Ark. Mat., 8:103–105, 1969.

9. W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. In Conference in modern analysis and probability (New Haven, Conn., 1982), pages 189–206. Amer. Math. Soc., Providence, RI, 1984.

10. J. R. Lee, M. Mendel, and A. Naor. Metric structures in L_{1}: Dimension, snowflakes, and average distortion. European J. Combin., 2004. To appear.

11. J. R. Lee and A. Naor. Absolute Lipschitz extendability. C. R. Math. Acad. Sci. Paris, 338(11):859–862, 2004.

12. J. R. Lee and A. Naor. Embedding the diamond graph in L_{p} and dimension reduction in L_{1}. Geom. Funct. Anal., 14(4):745–747, 2004.

13. J. R. Lee and A. Naor. Extending Lipschitz functions via random metric partitions. Invent. Math., 160(1):59–95, 2005.

14. J. Lindenstrauss and L. Tzafriri. Classical Banach spaces. II, volume 97 of Ergebnisse der Mathematik und ihrer Grenzgebiete [Results in Mathematics and Related Areas]. Springer-Verlag, Berlin, 1979. Function spaces.

15. N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215–245, 1995.

16. M. B. Marcus and G. Pisier. Characterizations of almost surely continuous p-stable random Fourier series and strongly stationary processes. Acta Math., 152(3-4):245–301, 1984.

17. J. Matoušek. On embedding expanders into l_{p} spaces. Israel J. Math., 102:189–197, 1997.

18. B. Maurey and G. Pisier. Séries de variables aléatoires vectorielles indépendantes et propriétés géométriques des espaces de Banach. Studia Math., 58(1):45–90, 1976.

19. M. Mendel and A. Naor. Metric cotype. Manuscript, 2004.

20. V. D. Milman and G. Schechtman. Asymptotic theory of finite-dimensional normed spaces, volume 1200 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 1986. With an appendix by M. Gromov.

21. A. Naor. A phase transition phenomenon between the isometric and isomorphic extension problems for Hölder functions between L_{p} spaces. Mathematika, 48(1-2):253–271 (2003), 2001.

22. A. Naor, Y. Peres, O. Schramm, and S. Sheffield. Markov chains in smooth Banach spaces and Gromov hyperbolic metric spaces. Preprint, 2004.

23. A. Naor and G. Schechtman. Remarks on non linear type and Pisier’s inequality. J. Reine Angew. Math., 552:213–236, 2002.

24. G. Pisier. Probabilistic methods in the geometry of Banach spaces. In Probability and analysis (Varenna, 1985), volume 1206 of Lecture Notes in Math., pages 167–241. Springer, Berlin, 1986.

25. M. Talagrand. Embedding subspaces of L_{1} into l_{1}^{N}. Proc. Amer. Math. Soc., 108(2):363–369, 1990.

26. N. Tomczak-Jaegermann. Banach-Mazur distances and finite-dimensional operator ideals, volume 38 of Pitman Monographs and Surveys in Pure and Applied Mathematics. Longman Scientific & Technical, Harlow, 1989.

27. S. S. Vempala. The random projection method. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 65. American Mathematical Society, Providence, RI, 2004. With a foreword by Christos H. Papadimitriou.

28. J. H. Wells and L. R. Williams. Embeddings and extensions in analysis. Springer-Verlag, New York, 1975. Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 84.

Department of Computer Science, California Institute of Technology, Pasadena, California 91125

E-mail address: mendelma@gmail.com

Theory Group, Microsoft Research, Redmond, Washington 90852

E-mail address: anaor@microsoft.com