Euclidean distortion and the Sparsest Cut

Sanjeev Arora^{∗}  James R. Lee^{†}  Assaf Naor ^{‡}

Abstract We prove that every n-point metric space of negative type (and, in particular, every npoint subset of L_{1}) embeds into a Euclidean space with distortion O(\sqrt{log n} · log log n), a result which is tight up to the iterated logarithm factor. As a consequence, we obtain the best known polynomial-time approximation algorithm algorithm for the Sparsest Cut problem with general demands. If the demand is supported on a subset of size k, we achieve an approximation ratio of O(\sqrt{log k} · log log k).

1 Introduction

Bi-Lipschitz embeddings of finite metric spaces, a topic originally studied in geometric analysis and Banach space theory, became an integral part of theoretical computer science following work of Linial, London, and Rabinovich [27]. They presented an algorithmic version of a result of Bourgain [7] which shows that every n-point metric space embeds into L_{2} with distortion O(log n). This geometric viewpoint offers a way to understand the approximation ratios achieved by linear programming (LP) and semidefinite programming (SDP) relaxations for cut problems [27, 5]. It soon became apparent that further progress in understanding SDP relaxations would involve improving Bourgain’s general bound of O(log n) for n-point metric spaces of negative type. For instance, the approximation ratio achieved by a well-known SDP relaxation for the general Sparsest Cut problem is known to coincide exactly with the best-possible distortion bound achievable for the embedding of n-point metrics of negative type into L_{1}—a striking connection between pure mathematics and algorithm design.

Further progress on these problems required new insights into the structure of metric spaces of negative type, and the design of more sophisticated and flexible embedding methods for finite metrics. Coincidentally, significant progress was made recently on both these fronts. Arora, Rao and Vazirani [4] proved a new structural theorem about metric spaces of negative type and used it to design an O(\sqrt{log n})-approximation algorithm for uniform case of the Sparsest Cut problem. Krauthgamer, Lee, Mendel and Naor [21] introduced a new embedding method called measured descent which unified and strengthened many existing embedding techniques, and they used it to solve a number of open problems in the field.

These breakthroughs indeed resulted in improved embeddings for negative type metrics; Chawla, Gupta, and Räcke [10] used the structural theorem of [4] (specifically, its stronger form due to Lee [22]), in conjunction with measured descent to show that every n-point metric of negative type embeds into L_{2} with distortion O(log n)^{3/4}. In the present work, we show how one can achieve distortion O(\sqrt{log n} · log log n). This almost matches the 35-year-old lower bound of \sqrt{log n} from Enflo [13]. Our methods use the results of [4, 22, 10] essentially as a “black box,” together with an enhancement of the measured descent technique.

∗Supported by David and Lucile Packard Fellowship and NSF grant CCR-0205594. Princeton University.

arora@cs.princeton.edu

†Supported by NSF grant CCR-0121555 and an NSF Graduate Research Fellowship. U. C. Berkeley.

jrl@cs.berkeley.edu

‡Microsoft Research. anaor@microsoft.com

Recall that a metric space (X, d) is said to be of negative type if (X, \sqrt{d}) is isometric to a subset of Euclidean space. In particular, it is well known that L_{1} is of negative type. (We also remind the reader that L_{2} is isometrically equivalent to a subset of L_{1}.) The parameter c_{2}(X), known as the Euclidean distortion of X, is the least distortion with which X embeds into Hilbert space, i.e. it is the minimum of distortion(f) = ∥f∥_{Lip} · ∥f^{−1}∥_{Lip} over all bijections f : X ↪ L_{2}. The mathematical investigation of the problem we study here goes back to the work of Enflo [13], who showed that the Euclidean distortion of the Hamming cube Ω_{d} = \{0, 1\}^{d} equals \sqrt{d} = \sqrt{log_{2} |Ω_{d}|}. The following natural question is folklore in geometric and functional analysis.

“Is the discrete d-dimensional hypercube the most non-Euclidean 2^{d}-point subset of L_{1}?”

A positive answer to this question would imply that any n-point subset of L_{1} embeds in L_{2} with distortion O(\sqrt{log n}). In fact, motivated by F. John’s theorem in convex geometry (see [32]), Johnson and Lindenstrauss [19] asked in 1983 whether every n-point metric space embeds into L_{2} with distortion O(\sqrt{log n}). Here, the analogy between finite dimensional normed spaces and finite metric spaces is not complete: Bourgain [7] has shown that for any n-point metric space X, c_{2}(X) = O(log n), and this result is existentially optimal [27, 5]. By now we understand that finite metric spaces (namely expander graphs) can exhibit an isoperimetric profile which no normed space can achieve, and this is the reason for the discrepancy with John’s theorem. However, it is known (see [21]) that several natural restricted classes of metrics do adhere to the O(\sqrt{log n}) Euclidean distortion suggested by John’s theorem. Arguably, for applications in theoretical computer science, the most important restricted class of metrics are those of negative type, yet improvements over Bourgain’s theorem for such metrics have long resisted the attempts of mathematicians and computer scientists.

The present paper is devoted to proving that up to iterated logarithmic factors, the answer to the above question is positive. This yields a general tool for the rounding of certain classes of semi-definite programs. As a result, we obtain the best-known polynomial time algorithm for the approximation of the Sparsest Cut problem with general demands, improving over the previous bounds due to [10] and the preceding works [27] and [5] (which yield an O(log n) approximation). This problem is described in Section 1.1. We now state our main result. In the case of metrics of negative type (and not just L_{1} metrics), it answers positively (up to iterated logarithms) a well known conjecture in theoretical computer science and metric geometry (stated explicitly by Goemans in [16]).

Theorem 1.1. Let (X, d) be an n-point metric space of negative type. Then

c_{2}(X) = O (\sqrt{log n} · log log n) .

Related work. Until recently, there was little solid evidence behind the conjecture that any npoint subset of L_{1} embeds in Hilbert space with distortion O(\sqrt{log n}). In the paper [23], Lee, Mendel and Naor show that any n-point subset of L_{1} embeds into Hilbert space with average distortion O(\sqrt{log n}). Arora, Rao, and Vazirani [4] have shown that O(\sqrt{log n}) distortion is achievable using a different notion of average distortion, which turns out to be more relevant for bounding the actual distortion. As described above, combining their result with the measured descent technique of Krauthgamer, Lee, Mendel and Naor [21], Chawla, Gupta, and Räcke [10] have recently proved that for any n-point metric space X of negative type, c_{2}(X) = O(log n)^{3/4}. It was conjectured [29, pg. 379] that n-point metrics of negative type embed into L_{1} with distortion O(1). Recently, Khot and Vishnoi [20] have obtained a lower bound of Ω(log log n)^{δ}, for some constant δ > 0.

Our results also suggest that the dimension reduction lower bound of Brinkman and Charikar [8] (see also [24]) is tight for certain distortions. They show that embedding certain n-point subsets of L_{1} into ℓ_{1}^{d} with distortion D requires that d ≥ n^{Ω(1/D^{2})}. Theorem 1.1, together with theorems of Johnson and Lindenstrauss [19] and Figiel, Lindenstrauss, and Milman [15], yields an embedding of every n-point subset of L_{1} into ℓ_{1}^{O(log n)} with distortion O(\sqrt{log n} · log log n).

1.1 Algorithmic application: The Sparsest Cut problem with general demands

In this section, we briefly describe an application of Theorem 1.1 to the Sparsest Cut problem with general demands (and its relation to the multi-commodity flow problem). This is a fundamental NPhard combinatorial optimization problem—we refer the interested reader to the articles [26, 2, 27, 5], the survey [37], and Chapter 21 of the book [38] for additional information on Sparsest Cut, and its applications to the design of approximation algorithms.

Let G = (V, E) be a graph (network), with a capacity C(e) ≥ 0 associated to every edge e ∈ E. Assume that we are given k pairs of vertices (s_{1}, t_{1}), ..., (s_{k}, t_{k}) ∈ V × V and D_{1}, …, D_{k} ≥ 1. We think of the s_{i} as sources, the t_{i} as targets, and the value D_{i} as the demand of the terminal pair (s_{i}, t_{i}) for some commodity κ_{i}. The problem is said to have uniform demands if every pair u, v ∈ V occurs as some (s_{i}, t_{i}) pair with D_{i} = 1.

In the MaxFlow problem the objective is to maximize the fraction λ of the demand that can be shipped simultaneously for all the commodities, subject to the capacity constraints. Denote this maximum by λ^{∗}. A trivial upper bound on λ^{∗} is the cut ratio. Given any subset S ⊆ V, we write

Φ(S) = \frac{∑_{uv∈E} C(uv) · |1_{S}(u) − 1_{S}(v)|}{∑_{i=1}^{k} D_{i} · |1_{S}(s_{i}) − 1_{S}(t_{i})|},

where 1_{S} is the characteristic function of S. The value Φ^{∗} = min_{S⊆V} Φ(S) is the minimum over all cuts (partitions) of V, of the ratio between the total capacity crossing the cut and the total demand crossing the cut. In the case of a single commodity (i.e. k = 1) the classical MaxFlow-MinCut theorem states that λ^{∗} = Φ^{∗}, but in general this is no longer the case. It is known [26, 27, 5] that Φ^{∗} = O(log k)λ^{∗}. This result is perhaps the first striking application of metric embeddings in combinatorial optimization (specifically, it uses Bourgain’s embedding theorem [7]).

Computing Φ^{∗} is NP-hard [30]. Moreover, finding a cut for which Φ^{∗} is (approximately) attained is a basic step in approximation algorithms for several NP-hard problems [26, 2, 37]. The best known algorithm for computing Φ^{∗} in the case of uniform demands is due to [4], where an approximation ratio of O(\sqrt{log n}) is achieved. In the case of non-uniform demands, an approximation ratio of O(log k)^{3/4} is obtained in [10]. Here, as an application of Theorem 1.1, we prove the following theorem:

Theorem 1.2. Using the above notation, there exists a polynomial-time algorithm which produces a subset S ⊆ V for which

Φ(S) = O (\sqrt{log k} · log log k) Φ^{∗}.

Structure of the paper: This paper is organized as follows. In Section 2 we present an informal overview of the ideas involved in the proof of Theorem 1.1. Section 3 is devoted to various preliminaries on the geometry of metrics of negative type. Theorem 1.1 is proved in Section 4, and the algorithm of Theorem 1.2 is described and analyzed in Section 5. We end with Section 6, which contains additional remarks and open problems.

2 Overview of the proof of Theorem 1.1

Remarks on notation. When we write E ≳ F for two expressions E and F, we intend this to mean that there exists some ϵ > 0 such that E ≥ ϵF, where ϵ is intended to be a universal constant, independent of the variables or parameters on which E and F depend.

We will often work with Hilbert spaces of the following form: If H is a Hilbert space, and (Ω, μ) is a probability space, we use L_{2}(H, Ω, μ) to denote the Hilbert space of H-valued random variables Z with norm ||Z||_{L_{2}(H,Ω,μ)} = \sqrt{𝔼 ||Z||_{H}^{2}}. When H, Ω are clear from context, we simply write L_{2}(μ) and denote || · ||_{H} by || · ||_{2}.

Our proof of Theorem 1.1 has little to do with metrics of negative type; the connection to such spaces comes through the techniques of [4, 22, 10] and is laid out in Section 3. Instead, we present a general theorem about gluing together various maps from finite metric spaces into Hilbert spaces (and, more generally, L_{p} spaces for p ∈ [1, ∞)). Our starting point is the following type of ensemble.

Let (X, d) be an n-point metric space. Suppose that for every τ ≥ 0, and every subset S ⊆ X, there exists a 1-Lipschitz map φ_{S,τ} : X → L_{2} with

||φ_{S,τ} (x) − φ_{S,τ} (y)||_{2} ≥ \frac{τ}{\sqrt{log |S|}}  (1)

whenever x, y ∈ S and d(x, y) ∈ [τ, 2τ]. In general, \sqrt{log |S|} could be a different function of |S|, but we restrict ourselves here for simplicity. Additionally, let us temporarily define φ_{τ} = φ_{X,τ} for every τ ≥ 0 so that for the maps {φ_{τ} }, condition (1) holds for all x, y ∈ X and |S| = n. The problem we are now confronted with is how to combine the ensemble of maps {φ_{S,τ} } together to obtain a genuinely bi-Lipschitz map.

There is an obvious approach which comes to mind: Let R ⊆ ℤ be such that for all x, y ∈ X, there exists k ∈ R such that d(x, y) ∈ [2^{k}, 2^{k+1}]. Now define the map φ : X → L_{2} by φ = ⨁_{k∈R} φ_{2^{k}}. Clearly we have both ||φ||_{Lip} ≤ \sqrt{R} and, for all x, y ∈ X,

||φ(x) − φ(y)||_{2} ≥ \frac{d(x, y)}{2\sqrt{log n}},

hence distortion(φ) = O(\sqrt{R log n}). Trivially, we can choose R so that |R| ≤ n^{2}. A slightly more delicate argument yields such an R with |R| ≤ O(n). Unfortunately, we are searching for a bound of the form distortion(φ) ≈ \sqrt{log n}, making this construction useless.

Nevertheless, the key to a better gluing of the given ensemble does lie in the delicate interplay between the distributions of distances in X and the number of points in various regions of the space. The technique of measured descent from [21] relies essentially on two facts about finite metric spaces. First, the identity

∑_{k∈ℤ}log \frac{|B(x, α · 2^{k})|}{|B(x, 2^{k})|} = O(log n log α)  (2)

for any number α ≥ 2. (In [21], a fixed constant value of α was used, but for us the quantitative dependence is crucial, as we will have α depending on n.) This gives a simple bound on the rate that a finite metric space can expand over all its scales, and is implicitly used in earlier works under the name of “region growing” [26, 14].

For the purposes of this description, we will state the second fact less concretely. Basically, in certain settings, one can think of the ratio |B(x, ατ)|/|B(x, τ)| as the “local cardinality of the space” around x at scale τ. As an example, if X = ℝ^{d}, B(x, ·) represents a Euclidean ball, and | · | is the Lebesgue measure, then this ratio approximates the number of τ-net points that can be packed inside a ball of radius ατ. Later, it will become necessary to randomly partition X into pieces of diameter at most 2τ while ensuring that pairs x, y ∈ X with d(x, y) ≪ τ are usually in the same component of the partition (see Section 3.1 on padded decomposability). It is known [9, 14] that the properties of such partitions near x depends on the local value log \frac{|B(x,2τ)|}{|B(x,τ)|}.

Following [21], this relationship is used in [22] to prove (roughly) that, given the maps {φ_{τ} }_{τ≥0} defined above, there exists a map φ : X → L_{2} such that ||φ||_{Lip} ≤ O(\sqrt{log n}) and, for x, y ∈ X with d(x, y) ∈ [2^{k}, 2^{k+1}],

||φ(x) − φ(y)||_{2} ≳ \sqrt{log \frac{|B(x, 2^{k+1})|}{|B(x, 2^{k})|}} ( \underbrace{||φ_{2^{k}}(x) − φ_{2^{k}}(y)||}_{(I)} + \underbrace{\frac{d(x, y)}{log \frac{|B(x,2^{k+1})|}{|B(x,2^{k})|}}}_{(II)} )  (3)

The contribution (II) comes from random partitioning and Rao’s technique [36], and is valid for any metric space X. Observing that (I) ≳ d(x, y)/\sqrt{log n}, and using AM-GM in (3), one arrives at the lower bound

||φ(x) − φ(y)||_{2} ≳ \frac{d(x, y)}{(log n)^{\frac{1}{4}}} ,

hence distortion(φ) ≤ O(log n)^{\frac{3}{4}} . While not obvious at present, the identity (2) is what allows [22] to get the leading \sqrt{·} factor in (3) while keeping ||φ||_{Lip} small (see Theorem 4.5).

In order to get the distortion near O(\sqrt{log n}), we have to dispense with the contribution (II) which is not derived from the ensemble {φ_{S,τ} }. Instead, we would like to pass from the ensemble {φ_{S,τ} } to a family of maps {φ̃_{τ} : X → L_{2}} for which the contribution of (I) in (3) is replaced by

||φ̃_{2^{k}}(x) − φ̃_{2^{k}}(y)||_{2} ≳ \frac{d(x, y)}{\sqrt{log \frac{|B(x,2^{k+1})|}{|B(x,2^{k})|}}} .  (4)

Clearly this would finish the proof. Roughly, the construction of φ̃_{2^{k}} proceeds as follows. We first randomly partition X into components of diameter about 2^{k}α for some appropriately chosen α = α(n). Writing the random partition as X = C_{1} ∪ C_{2} ∪ ⋯ ∪ C_{m}, we then derive subsets C̃_{i} ⊆ C_{i} by randomly sampling points from each C_{i}. Then, we use an appropriately constructed (random) partition of unity to glue the collection of maps {φ_{C̃_{i},2^{k}}}_{i=1}^{m} together. To ensure that the resulting map still has ||φ̃_{2^{k}}||_{Lip} ≤ O(1), the partition of unity is constructed carefully using properties of the random partition (this bears some resemblance to the technique of [25] for extending Lipschitz functions).

The key to the proof is the way in which the random samples C̃_{i} are chosen. We have to maintain the property that C̃_{i} is a “good representative” of C_{i} at scale 2^{k} (i.e. we need that, on average, C̃_{i} is a 2^{k}-dense in C_{i}). On the other hand, we need to maintain the invariant that if x ∈ C_{i}, then

log |C̃_{i}| ≈ log \frac{|B(x, α2^{k})|}{|B(x, 2^{k})|},

so that we can achieve a bound similar to (4) (recall that the quality of the map φ_{S,τ} depends on |S| = |C̃_{i}|). Unfortunately, this is impossible since for distinct x, x′ ∈ C_{i}, the above ratios can be quite different. Instead, we have a number of phases, one for each estimate of the possible ratio (see the proof of Theorem 1.1). For this to work, we have to give up on achieving (4) exactly, and instead we weave together the inter-scale (Lemma 4.4) gluing of (3) with the intra-scale (Theorem 4.5) gluing of (4) to obtain a nearly-tight bound of O(\sqrt{log n} · log log n).

3 Single scale embeddings

In this section we present Theorem 3.1, and derive from it Lemma 3.5 which is one of the main tools used in the proof of the Main Theorem (1.1). It is a concatenation of the result of Arora, Rao, and Vazirani [4], its strengthening by Lee [22], and the “reweighting” method of Chawla, Gupta, and Räcke [10], who use it in conjunction with [21] to achieve distortion O (log n)^{\frac{3}{4}} . For the sake of completeness, we present below a sketch of the proof of Theorem 3.1. Complete details can be found in the full version of [22], where a more general result is proved; the statement actually holds for metric spaces which are quasisymmetrically equivalent to subsets of Hilbert space, and not only for those of negative type. (See [18] for the definition of quasisymmetry; the relevance of such maps to the techniques of [4] was first pointed out in [34]).

Theorem 3.1. There exist constants C ≥ 1 and 0 < p < \frac{1}{2} such that for every n-point metric space (Y, d) of negative type and every Δ > 0, the following holds. There exists a distribution μ over subsets U ⊆ Y such that for every x, y ∈ Y with d(x, y) ≥ \frac{Δ}{16},

μ \{U : y ∈ U and d(x, U) ≥ \frac{Δ}{C\sqrt{log n}}\} ≥ p.

Proof (sketch). Let g : Y → ℓ_{2} be such that

d(x, y) = ||g(x) − g(y)||_{2}^{2}

for all x, y ∈ Y. By [31], there exists a map T : ℓ_{2} → ℓ_{2} such that ||T (z)||_{2} ≤ \sqrt{Δ} for all z ∈ ℓ_{2} and

\frac{1}{2} ≤ \frac{||T (z) − T (z′)||_{2}}{min\{\sqrt{Δ}, ||z − z′||_{2}\}} ≤ 1.

for all z, z′ ∈ ℓ_{2}. As in [22], we let f : Y → ℝ^{n} be the map given by f = T ∘ g (we remark that this map can be computed efficiently). Then f is a bi-Lipschitz embedding (with distortion 2) of the metric space (Y, \sqrt{min\{Δ, d\}}) into the Euclidean ball of radius Δ.

Let 0 < σ < 1 be some constant. The basic idea is to choose a random u ∈ S^{n−1} and define

L_{u} = \{x ∈ Y : ⟨x, u⟩ ≤ \frac{−σ\sqrt{Δ}}{\sqrt{n}}\}
R_{u} = \{x ∈ Y : ⟨x, u⟩ ≥ \frac{σ\sqrt{Δ}}{\sqrt{n}}\}.

One then prunes the sets by iteratively removing any pairs of nodes x ∈ L_{u}, y ∈ R_{u} with d(x, y) ≤ Δ/\sqrt{log n}. At the end one is left with two sets L′_{u}, R′_{u}. The main result of [4, 22] is that with high probability (over the choice of u), the number of pairs pruned from L_{u} × R_{u} is not too large.

Let S_{Δ} = \{(x, y) ∈ Y × Y : d(x, y) ≥ \frac{Δ}{16}\}. The reweighting idea of [10] is to apply the above procedure to a weighted version of the point set as follows. Let w : Y ×Y → ℤ^{+} be an integer-valued weight function on pairs, with w(x, y) = w(y, x), w(x, x) = 0, and w(x, y) > 0 only if (x, y) ∈ S_{Δ}. This weight function can be viewed as yielding a new set of points where each point x is replaced by ∑_{y∈Y} w(x, y) copies, with w(x, y) of them corresponding to the pair (x, y). One could think of applying the above procedure on this new point set; note that the pruning procedure above may remove some or all copies of x. Then, as observed in [10], the theorems of [4, 22] imply that with high probability, after the pruning, we still have

∑_{x∈L′_{u},y∈R′_{u}} w(x, y) ≳ ∑_{x,y} w(x, y).

The distribution μ mentioned in the statement of the theorem is defined using a family of O(log n) weight functions described below. Sampling from μ consists of picking a weight function from this family and a random direction u ∈ S^{n−1}, and then forming sets L′_{u}, R′_{u} as above using the weight function. Let us call these sets L′_{u}(w), R′_{u}(w). One then outputs the set U of all points x for which any “copy” falls into L′_{u}(w).

Now we define the family of weight functions. The initial weight function has w_{0}(x, y) = n^{4} for all (x, y) ∈ S_{Δ}. Given w_{k}, obtain w_{k+1} as follows. If

μ {u ∈ S^{n−1} : (x, y) ∈ L′_{u}(w_{k}) × R′_{u}(w_{k})} ≥ 0.1,

we set w_{k+1}(x, y) = \frac{1}{2}w_{k}(x, y). Otherwise, we set w_{k+1}(x, y) = w_{k}(x, y). A simple argument (presented in [10]) shows that by repeating this O(log n) times we obtain O(log n) weight functions such that for every pair (x, y) ∈ S_{Δ} the following is true: If one picks a random weight function w and a random direction u ∈ S^{n−1}, then with constant probability we have (x, y) ∈ L′_{u}(w) × R′_{u}(w).

3.1 Padded decomposability and random zero sets

Theorem 3.1 is the only way the negative type property will be used in what follows. It is therefore helpful to introduce it as an abstract property of metric spaces. Let (X, d) be an n-point metric space.

Definition 3.2 (Random zero-sets). Given Δ, ζ > 0, and p ∈ (0, 1) we say that X admits a random zero set at scale Δ which is ζ-spreading with probability p if there is a distribution μ over subsets Z ⊆ X such that for every x, y ∈ X with d(x, y) ≥ Δ,

μ \{Z ⊆ X : y ∈ Z and d(x, Z) ≥ \frac{Δ}{ζ}\} ≥ p.

We denote by ζ(X; p) the least ζ > 0 such that for every Δ > 0, X admits a random zero set at scale Δ which is ζ-spreading with probability p. Finally, given k ≤ n we define

ζ_{k}(X; p) = max_{\begin{matrix}Y ⊆X \\ |Y |≤k \end{matrix}} ζ(Y; p).

With this definition, Theorem 3.1 implies that there exists a universal constant p ∈ (0, 1) such that for every n-point metric space (X, d) of negative type, ζ(X; p) = O(\sqrt{log n}).

We now recall the related notion of padded decomposability. Given a partition P of X and x ∈ X we denote by P (x) ∈ P the unique element of P to which x belongs. In what follows we sometimes refer to P (x) as the cluster of x.

Definition 3.3 (Decomposition bundle, modulus of padded decomposability). Following [21] we say that {P_{Δ}}_{Δ>0} is an α-padded decomposition bundle of a metric space X if for every Δ > 0, P_{Δ} is a random partition of X (whose distribution we denote by ν) with the following properties:

1. For all P ∈ supp(ν) and all C ∈ P we have that diam(C) < Δ.

2. For every x ∈ X we have that

ν\{P : B(x, Δ/α) ⊆ P (x)\} ≥ \frac{1}{2}.

The modulus of padded decomposability of X, denoted α_{X}, is defined as the largest constant α > 0 such that X admits an α-padded decomposition bundle.

As observed in [21], the results of [28, 6] imply that α_{X} = O(log |X|), and this will be used in the ensuing arguments. The following useful fact relates the notions of padded decomposability and random zero sets. Its proof is motivated by an argument of Rao [36].

Fact 3.4. ζ(X; 1/8) ≤ α_{X}.

Proof. Fix Δ > 0 and let P be a partition of X into subsets of diameter less than Δ. Given x ∈ X we denote by π_{P} (x) the largest radius r for which B(x, r) ⊆ P (x). Let {ε_{C}}_{C∈P} be i.i.d. symmetric {0, 1}-valued Bernoulli random variables. Let Z_{P} be a random subset of X given by

Z_{P} = ⋃_{C∈P: ε_{C}=0} C .

If x, y ∈ X satisfy d(x, y) ≥ Δ then P (x) ≠ P (y). It follows that

Pr[y ∈ Z_{P} ∧ d(x, Z_{P}) ≥ π_{P} (x)] ≥ \frac{1}{4}.

By the definition of α_{X}, there exists a distribution over partitions P of X into subsets of diameter less than Δ such that for every x ∈ X with probability at least 1/2, π_{P} (x) ≥ Δ/α_{X}. The required result now follows by considering the random zero set Z_{P}.

We end this section with the following simple lemma, which shows that the existence of random zero sets implies the existence of embeddings into L_{2} which are bi-Lipschitz on a fixed distance scale.

Lemma 3.5 (Random zero sets yield single scale embeddings). For every finite metric space X, every S ⊆ X every p ∈ (0, 1) and every τ > 0, there exists a 1-Lipschitz mapping φ : X → L_{2} such that for every x, y ∈ S with d(x, y) ≥ τ,

∥φ(x) − φ(y)∥_{2} ≥ \frac{τ\sqrt{p}}{ζ(S; p)}.

Proof. By the definition of ζ(S, p) there exists a distribution μ over subsets Z ⊆ S such that for every x, y ∈ S with d(x, y) ≥ τ,

μ \{Z ⊆ S : y ∈ Z and d(x, Z) ≥ \frac{τ}{ζ(S; p)}\} ≥ p.

Define φ : X → L_{2}(μ) by φ(x) = d(x, Z). Clearly φ is 1-Lipschitz. Moreover, for every x, y ∈ S with d(x, y) ≥ τ,

∥φ(x) − φ(y)∥_{L_{2}(μ)}^{2} = 𝔼_{μ} [d(x, Z) − d(y, Z)]^{2} ≥ p · (\frac{τ}{ζ(S; p)})^{2} .

4 Proof of Theorem 1.1

The primary result of this section is the following theorem.

Theorem 4.1. Let (X, d) be an n-point metric space. Suppose there exist constants C > 0 and \frac{1}{2} ≤ ε ≤ 1, such that for every τ ≥ 0, and every subset S ⊆ X, there exists a 1-Lipschitz map φ_{S,τ} : X → L_{2} with

||φ_{S,τ} (x) − φ_{S,τ} (y)||_{2} ≥ \frac{τ}{C(log |S|)^{ε}}

whenever x, y ∈ S and d(x, y) ∈ [τ, 6τ]. Then c_{2}(X) ≤ O(1) · C(log n)^{ε} log log n.

Theorem 4.1 implies Theorem 1.1. Indeed, if X is an n point metric space such that for some p ∈ (0, 1), ε ∈ [1/2, 1], and C > 0, we have for every k ≤ n, ζ_{k}(X; p) ≤ C(log k)^{ε}, then Theorem 4.1 together with Lemma 3.5 imply that

c_{2}(X) = O (\frac{C(log n)^{ε} log log n}{\sqrt{p}}) .

Theorem 1.1 follows since by Theorem 3.1 we know that for some universal constant p ∈ (0, 1), if X is a metric space of negative type then for all k, ζ_{k}(X; p) = O (\sqrt{log n}).

The proof of Theorem 4.1 will be broken down into several steps. In what follows we fix a finite metric space X, and for K ≥ 1, τ ≥ 0, define

S_{τ} (K) = \{x ∈ X : |B (x, 8τα_{X})| ≤ K |B (x, \frac{τ}{12C(log K)^{ε}} )|\} .

Lemma 4.2 (Embedding neighborhoods). Let S ⊆ X, τ ≥ 0, and assume that there exists a 1-Lipschitz map φ : X → L_{2} satisfying

||φ(x) − φ(y)||_{2} ≥ \frac{τ}{L}

for x, y ∈ S, d(x, y) ∈ [τ/2, 3τ] and some L ≥ 2. Then there is a 1-Lipschitz map h : X → L_{2} with

||h(x) − h(y)||_{2} ≥ \frac{τ}{9L}

whenever d(x, S) ≤ \frac{τ}{6L}, y ∈ X, and d(x, y) ∈ [τ, 2τ].

Proof. Define g : X → ℝ by g(x) = d(x, S), and set h = \frac{1}{\sqrt{2}}(φ ⊕ g). If d(y, S) > \frac{τ}{3L}, then

||h(x) − h(y)||_{2} ≥ \frac{1}{\sqrt{2}}||g(x) − g(y)||_{2} ≥ \frac{1}{\sqrt{2}}(d(y, S) − d(x, S)) ≥ \frac{1}{\sqrt{2}} · \frac{τ}{6L}.

Otherwise, let x′, y′ ∈ S be such that d(x, x′) ≤ \frac{τ}{6L}, d(y, y′) ≤ \frac{τ}{3L}, and observe that

d(x′, y′) ∈ [d(x, y) − \frac{τ}{6L} − \frac{τ}{3L}, d(x, y) + \frac{τ}{6L} + \frac{τ}{3L}] ⊆ [\frac{τ}{2} , 3τ] .

Using our assumptions on φ, we have

||φ(x) − φ(y)||_{2} ≥ ||φ(x′) − φ(y′)||_{2} − ||φ||_{Lip} (\frac{τ}{6L} + \frac{τ}{3L}) ≥ \frac{τ}{2L},

hence ||h(x) − h(y)||_{2} ≥ \frac{1}{\sqrt{2}} · \frac{τ}{2L}.

Lemma 4.3 (Random subsets). Assume that X satisfies the conditions of Theorem 4.1, and suppose that U ⊆ X and k ≥ 2. Define

T_{τ} (U; k) = \{x ∈ U : |U| ≤ k |B (x, \frac{τ}{12C(log k)^{ε}} )|\} .  (5)

Then there exists a 1-Lipschitz map γ_{U,k} : X → L_{2} such that

||γ_{U,k}(x) − γ_{U,k}(y)||_{2} ≥ \frac{τ}{30C(log k)^{ε}}

whenever x ∈ T_{τ} (U; k), y ∈ X and d(x, y) ∈ [τ, 2τ].

Proof. Let S be a uniformly random subset S ⊆ U with |S| = min{|U|, k}. Let h_{S} : X → L_{2} be the map defined by h_{S} = \frac{1}{\sqrt{2}}(φ_{S,τ/2} ⊕ g) where g(x) = d(x, S). Define γ_{U,k} : X → L_{2}(L_{2}, μ), where μ is the distribution of the random subset S, by γ_{U,k}(x) = h_{S}(x) (recall that h_{S}(x) is a random element of L_{2}). Note that γ_{U,k} is 1-Lipschitz because the same is true for each h_{S}.

Let L = 2C(log |S|)^{ε}. Observe that, by the definition of T_{τ} (U; k), with probability at least 1/e, we have

S ∩ B (x, \frac{τ}{6L}) = S ∩ B (x, \frac{τ}{12C(log k)^{ε}} ) ≠ ∅.

Assuming this holds, we see that d(x, S) ≤ \frac{τ}{6L}. Thus by Lemma 4.2, ||h_{S}(x) − h_{S}(y)||_{2} ≥ \frac{τ}{9L}. It follows that

||γ_{U,k}(x) − γ_{U,k}(y)||_{2} ≥ \frac{1}{\sqrt{e}} · \frac{τ}{9L} ≥ \frac{τ}{30C(log k)^{ε}} .

In what follows we shall use the fact that for every τ > 0 there exists a mapping G_{τ} : L_{2} → L_{2} such that for every x, y ∈ L_{2},

∥G_{τ} (x)∥_{2} = ∥G_{τ} (y)∥_{2} = τ and \frac{1}{2} min\{τ, ∥x − y∥_{2}\} ≤ ∥G_{τ} (x) − G_{τ} (y)∥_{2} ≤ min\{τ, ∥x − y∥_{2}\}. (6)

The existence of G_{τ} is precisely Lemma 5.2 in [31]. As in [22], we will use the map G_{τ} to control the Lipschitz constant of various functions under partitions of unity.

Lemma 4.4 (Localization). Assume that X satisfies the conditions of Theorem 4.1. Then for every τ ≥ 0, k ≥ 1, there exists a 1-Lipschitz map Λ_{τ,k} : X → L_{2} such that for every x ∈ S_{τ} (k), y ∈ X with d(x, y) ∈ [τ, 3τ],

||Λ_{τ,k}(x) − Λ_{τ,k}(y)||_{2} ≥ \frac{τ}{240C(log k)^{ε}} .

Proof. Let D = 4τα_{X} and take P_{D} to be a random partition from the α_{X}-padded bundle ensured by Definition 3.3. Define a random mapping ρ : X → ℝ by

ρ(z) = min \{1, \frac{d(z, X \ P_{D}(z))}{τ}\} .

Clearly ∥ρ∥_{Lip} ≤ 1/τ. For each U ∈ P_{D}, let γ_{U,k} be the corresponding map from Lemma 4.3. Finally, define a random map Λ_{τ,k} : X → L_{2} by

Λ_{τ,k}(z) = \frac{1}{2}ρ(z) · γ̂_{P_{D}(z),k}(z),

where for f : X → L_{2} we write f̂ = G_{τ} ∘ f, where G_{τ} is as in (6).

We claim that ∥Λ_{τ,k}∥_{Lip} ≤ 1. Indeed, fix u, v ∈ X. If P_{D}(u) = P_{D}(v) = U then

||Λ_{τ,k}(u) − Λ_{τ,k}(v)||_{2} ≤ \frac{1}{2}|ρ(u) − ρ(v)| · ||γ̂_{P_{D}(u),k}(u)||_{2} + \frac{1}{2}||γ̂_{U,k}(u) − γ̂_{U,k}(v)||_{2} · |ρ(v)|
≤ \frac{1}{2}(τ||ρ||_{Lip} + ||γ̂_{U,k}||_{Lip}) d(u, v)
≤ d(u, v).

Otherwise, assume that P_{D}(u) ≠ P_{D}(v). In particular,

d(u, v) ≥ max{d(u, X \ P_{D}(u)), d(v, X \ P_{D}(v))}.

It follows that

||Λ_{τ,k}(u) − Λ_{τ,k}(v)||_{2} ≤ ||Λ_{τ,k}(u)||_{2} + ||Λ_{τ,k}(v)||_{2}
≤ \frac{d(u, X \ P_{D}(u))}{2τ} · τ + \frac{d(v, X \ P_{D}(v))}{2τ} · τ
≤ d(u, v).

Now suppose that x ∈ S_{τ} (k), y ∈ X, and d(x, y) ∈ [τ, 3τ]. Observe that since diam(P_{D}(x)) ≤ D, we have P_{D}(x) ⊆ B(x, 2D). It follows that since x ∈ S_{τ} (k), we have x ∈ T_{τ} (P_{D}(x); k) (recall equation (5)). Moreover, using the defining property of the α_{X}-padded bundle, with probability at least \frac{1}{2}, we have d(x, X \ P_{D}(x)) ≥ 5τ. Since we are assuming that d(x, y) ≤ 3τ, this implies that ρ(x) = ρ(y) = 1. It follows that

𝔼 ||Λ_{τ,k}(x) − Λ_{τ,k}(y)||_{2} ≥ \frac{1}{2} · \frac{1}{2}𝔼 ||γ̂_{P_{D}(x),k}(x) − γ̂_{P_{D}(x),k}(y)||_{2}
≥ \frac{1}{8}𝔼 (min \{||γ_{P_{D}(x),k}(x) − γ_{P_{D}(x),k}(y)||_{2}, τ\})
≥ \frac{τ}{240C(log k)^{ε}} .

Denoting by (Ω, μ) the probability space on which Λ_{τ,k} is defined, we can think of Λ_{τ,k} as a mapping of X into the Hilbert space L_{2}(L_{2}, μ) which has the required properties.

The following theorem is a generalization of the Gluing Lemma in [22]. In particular, it is important for us that part (2) treats x and y symmetrically, unlike in [22].

Theorem 4.5 (Inter-scale gluing). Given any n-point metric space (X, d) and constants A, B ≥ 1, and for every m ∈ ℤ, a 1-Lipschitz map ϕ_{m} : X → L_{2}, there exists a map φ : X → L_{2} which satisfies

1. ||φ||_{Lip} ≤ O(\sqrt{log n log(AB)}).

2. For every x, y ∈ X we have

||φ(x) − φ(y)||_{2} ≥ max_{m∈ℤ}(\sqrt{⌊log \frac{|B(x, 2^{m+1}A)|}{|B(x, 2^{m}/B)|}⌋} · min \{\frac{2^{m}}{B} , ||ϕ_{m}(x) − ϕ_{m}(y)||_{2}\}) .

Proof. Let ρ : X → ℝ_{+} be any 2B-Lipschitz map with ρ ≡ 1 on [1/B, 2A], and ρ ≡ 0 outside [1/2B, 4A]. For x ∈ X and t ≥ 0, define

R(x, t) = sup{R : |B(x, R)| ≤ 2^{t}},

and observe that R(·, t) is 1-Lipschitz for every value of t. And for each m ∈ ℤ, define

ρ_{m,t}(x) = ρ (\frac{R(x, t)}{2^{m}}) .

Write ϕ̂_{m} = G_{2^{m}/B} ∘ ϕ_{m}, where G_{2^{m}/B} is as in (6). Now, for each t ∈ {1, 2, …, ⌈log_{2} n⌉}, define ψ_{t} : X → ℓ_{2}(L_{2}),

ψ_{t}(x) = ⨁_{m∈ℤ}ρ_{m,t}(x) · ϕ̂_{m}(x).

Finally, let φ = ψ_{1} ⊕ ψ_{2} ⊕ ⋯ ⊕ ψ_{⌈log_{2} n⌉}.

First, we bound ||ψ_{t}||_{Lip} as follows.

||ψ_{t}(x) − ψ_{t}(y)||_{2}^{2} = ∑_{\begin{matrix}m∈ℤ \\ ρ_{m,t}(x)+ρ_{m,t}(y)>0 \end{matrix}} ||ρ_{m,t}(x)ϕ̂_{m}(x) − ρ_{m,t}(y)ϕ̂_{m}(y)||_{2}^{2}.

The number of non-zero summands above is at most O(log A+log B). Furthermore, each summand can be bounded as follows.

||ρ_{m,t}(x)ϕ̂_{m}(x) − ρ_{m,t}(y)ϕ̂_{m}(y)||_{2} ≤ ||ϕ̂_{m}(x)||_{2}|ρ_{m,t}(x) − ρ_{m,t}(y)| + ||ϕ̂_{m}(x) − ϕ̂_{m}(y)||_{2}|ρ_{m,t}(y)|
≤ (||ρ_{m,t}||_{Lip} · \frac{2^{m}}{B} + ||ϕ_{m}||_{Lip}) d(x, y)
≤ 4 d(x, y).

Thus ||ψ_{t}||_{Lip} ≤ O(\sqrt{log(AB)}). It follows that ||φ||_{Lip} ≤ O(\sqrt{log n log(AB)}), as claimed.

It remains to prove the lower bound. To this end, fix m ∈ ℤ, x, y ∈ X and observe that if ρ_{m,t}(x) = 1, then

||ψ_{t}(x) − ψ_{t}(y)||_{2} ≥ ∥ϕ̂_{m}(x) − ϕ̂_{m}(y)||_{2} − (1 − ρ_{m,t}(y)) · ∥ϕ̂_{m}(y)∥_{2}
≥ \frac{1}{2} min \{\frac{2^{m}}{B} , ||ϕ_{m}(x) − ϕ_{m}(y)||_{2}\} − \frac{2^{m}}{B} · (1 − ρ_{m,t}(y)).  (7)

On the other hand

||ψ_{t}(x) − ψ_{t}(y)||_{2} ≥ ∥ϕ̂_{m}(x) − ρ_{m,t}(y)ϕ̂_{m}(y)∥_{2}
≥ ∥ϕ̂_{m}(x)∥_{2} − ρ_{m,t}(y)∥ϕ̂_{m}(y)∥_{2} = \frac{2^{m}}{B} · (1 − ρ_{m,t}(y)).  (8)

Averaging (7) and (8) we get that

||ψ_{t}(x) − ψ_{t}(y)||_{2} ≥ \frac{1}{4} min \{\frac{2^{m}}{B} , ||ϕ_{m}(x) − ϕ_{m}(y)||_{2}\} .  (9)

Hence it suffices to count the number of values of t for which ρ_{m,t}(x) = 1. By our definitions we have that

ρ_{m,t}(x) = 1 ⟺ \frac{2^{m}}{B} ≤ R(x, t) ≤ 2^{m+1}A ⟺ t ∈ [log |B(x, 2^{m}/B)|, log |B(x, 2^{m+1}A)|].

This completes the proof since the lower bound (9) holds for ⌊log \frac{|B(x,2^{m+1}A)|}{|B(x,2^{m}/B)|}⌋ values of t.

We also present the following base case which is a variant of Bourgain’s argument [7].

Claim 4.6 (Small ratios). Let X be an n-point metric space, and λ ≥ 1. For each τ > 0, define the subset

J_{λ}(τ) = {x ∈ X : |B(x, τ/2)| ≤ λ|B(x, τ/4)|} .

Then there exists a map F : X → L_{2} with ∥F ∥_{Lip} ≤ O (\sqrt{log n}), and such that for every x, y ∈ X with x ∈ J_{λ}(τ) and d(x, y) ≥ τ, we have

||F (x) − F (y)||_{2} ≥ ϵ(λ)τ,

where ϵ(λ) > 0 is a constant depending only on λ.

Proof. For each t ∈ {1, 2, …, ⌈log n⌉}, let W_{t} ⊆ X be a random subset which contains each point of X independently with probability 2^{−t}. Let g_{t}(x) = d(x, W_{t}), and consider the random map f = g_{1} ⊕ ⋯ ⊕ g_{⌈log n⌉} ∈ ℓ_{2}^{n}. Finally, we define F : X → L_{2}(ℓ_{2}^{n}, μ) by F (x) = f(x), where μ is the distribution over which the random subsets \{W_{t}\} are defined. Observe that ∥F ∥_{Lip} ≤ O (\sqrt{log n}).

Fix x, y ∈ X such that d(x, y) ≥ τ and x ∈ J_{λ}(τ). Let t ∈ ℕ be such that 2^{t} ≤ |B(x, τ/2)| ≤ 2^{t+1}. Let E_{far} be the event {d(x, W_{t}) ≥ τ/2} and let E_{close} be the event {d(x, W_{t}) ≤ τ/4}. Also, define the event E_{close}^{y} = {d(y, W_{t}) < τ/2}. Observe that each of the events E_{close}, E_{far} are independent of E_{close}^{y} since the former events depend only on W_{t} ∩ B^{∘}(x, τ/2), and the latter on W_{t} ∩ B^{∘}(y, τ/2), where B^{∘}(·, ·) denotes an open ball in X. It follows that

∥F (x) − F (y)∥_{L_{2}(μ)}^{2} = 𝔼_{μ} ∥f(x) − f(y)∥_{2}^{2}
≥ 𝔼_{μ} |g_{t}(x) − g_{t}(y)|_{2}^{2}
≥ Pr(E_{close}^{y}) · min \{Pr(E_{far}), Pr(E_{close})\} · (\frac{1}{2} · \frac{τ}{4} )^{2} + Pr(¬E_{close}^{y}) · Pr(E_{close}) · (\frac{τ}{4} )^{2}
≥ ϵ(λ)τ^{2}.

The final inequality holds true because x ∈ J_{λ}(τ) implies that each of Pr(E_{far}) and Pr(E_{close}) can be bounded from below by some ϵ′(λ) > 0.

We are now in position to conclude the proof of Theorem 4.1

Proof of Theorem 4.1. We claim that for every K ∈ [2, n] there exists a map f_{K} : X → L_{2} which satisfies

1. ||f_{K}||_{Lip} ≤ O(\sqrt{log n · log log n}).

2. For every m ∈ ℤ and x ∈ S_{2^{m}}(K), y ∈ X we have

||f_{K}(x) − f_{K}(y)||_{2}^{2} ≳ ⌊log \frac{|B(x, 2^{m+3}α_{X})|}{|B(x, 2^{m}/[12C(log K)^{ε}])|}⌋ · \frac{2^{2m}}{C^{2}(log K)^{2ε}} .

Indeed, f_{K} is obtained from an application of Theorem 4.5 to the mappings {Λ_{2^{m},K}}_{m∈ℤ} from Lemma 4.4 with A = 4α_{X} and B = 12C(log K)^{ε} (and using the fact that α_{X} = O(log n)).

Observe that for every m ∈ ℤ, S_{2^{m}}(n) = X. Hence, defining K_{0} = n and K_{j+1} = \sqrt{K_{j}}, as long as K_{j} ≥ 4, we obtain mappings f_{0}, …, f_{j} : X → L_{2} satisfying

1. ∥f_{j}∥_{Lip} ≤ O(\sqrt{log n · log log n}).

2. For all x ∈ S_{2^{m}}(K_{j}) \ S_{2^{m}}(K_{j+1}) and y ∈ X such that d(x, y) ∈ [2^{m}, 2^{m+1}] and we have

||f_{j}(x) − f_{j}(y)||_{2}^{2} ≳ ⌊log \frac{|B(x, 2^{m+3}α_{X})|}{|B(x, 2^{m}/[12C(log K_{j})^{ε}])|}⌋ · \frac{2^{2m}}{C^{2}(log K_{j})^{2ε}}
≳ ⌊log \frac{|B(x, 2^{m+3}α_{X})|}{|B(x, 2^{m}/[12C(log K_{j+1})^{ε}])|}⌋ · \frac{d(x, y)^{2}}{C^{2}(log K_{j})^{2ε}}  (10)
≳ ⌊log K_{j+1}⌋ · \frac{d(x, y)^{2}}{C^{2}(log K_{j})^{2ε}}  (11)
≳ \frac{d(x, y)^{2}}{C^{2}(log K_{j})^{2ε−1}} ,  (12)

where in (10) we used the fact that K_{j+1} ≤ K_{j} and d(x, y) ≤ 2^{m+1}, in (11) we used the fact that x ∉ S_{2^{m}}(K_{j+1}), and in (12) we used the fact that K_{j+1} = \sqrt{K_{j}} ≥ 2.

This procedure ends after N steps, where N ≤ O(log log n). Every x ∈ S_{2^{m}}(K_{N}) satisfies

|B(x, 2^{m+3}α_{X})| ≤ 4|B(x, 2^{m}/[12C])|.

In particular, using the notation of Claim 4.6, x ∈ J_{4}(2^{m}). By Claim 4.6, there is a mapping f_{N+1} : X → L_{2} which is Lipschitz with constant O(\sqrt{log n}) and for every x, y ∈ S_{2^{m}}(K_{N}) ⊆ J_{4}(2^{m}), ∥f_{N+1}(x) − f_{N+1}(y)∥_{2} ≳ d(x, y).

Consider the map Φ = ⨁_{j=0}^{N+1} f_{j}, which is Lipschitz with constant O (\sqrt{log n} · log log n). For every x, y ∈ X choose m ∈ ℤ such that d(x, y) ∈ [2^{m}, 2^{m+1}]. If x, y ∈ S_{2^{m}}(K_{N}) then

∥Φ(x) − Φ(y)∥_{2} ≥ ∥f_{N+1}(x) − f_{N+1}(y)∥_{2} ≳ d(x, y).

Otherwise, without loss of generality there is j ∈ {0, …, N −1} such that x ∈ S_{2^{m}}(K_{j})\S_{2^{m}}(K_{j+1}), in which case by (12)

∥Φ(x) − Φ(y)∥_{2} ≥ ∥f_{j+1}(x) − f_{j+1}(y)∥_{2} ≳ \frac{d(x, y)}{C(log K_{j})^{ε− \frac{1}{2}}} ≥ \frac{d(x, y)}{C(log n)^{ε− \frac{1}{2}}} .

5 The sparsest cut problem with general demands

This section is devoted to the proof of Theorem 1.2. Our argument follows the well known approach for deducing the algorithmic Theorem 1.2 from the embedding result contained in Theorem 1.1 (see e.g. [27, 5, 16]).

5.1 Computing the Euclidean distortion

In this section, we remark that the maps used to prove Theorem 1.1 have a certain “autoextendability” property which will be used in the next section. We also recall that it is possible to find near-optimal Euclidean embeddings using semi-definite programming [27].

Corollary 5.1. Let (Y, d) be an arbitrary metric space, and fix a k-point subset X ⊆ Y. If the space (X, d) is a metric of negative type, then there exists a 1-Lipschitz map f : Y → L_{2} such that the map f|_{X} : X → L_{2} has distortion O (\sqrt{log k} · log log k).

Proof. We observe that the maps used to prove Theorem 1.1, i.e. those produced in Lemma 3.5 and Claim 4.6, are of Fréchet-type. In other words, there is a probability space (Ω, μ) over subsets A_{ω} ⊆ X for ω ∈ Ω, and we obtain a maps φ_{S,τ} : X → L_{2}(μ) given by φ_{S,τ} (x)(ω) = d(x, A_{ω}). We can then define the extension φ_{S,τ} : Y → L_{2}(μ) by

φ_{S,τ} (y)(ω) = d(y, A_{ω}).

Thus by extending the ensemble of maps {φ_{S,τ} } to the larger space Y before the application of Theorem 4.1, we can ensure that the final embedding is 1-Lipschitz on Y.

Now we suppose that (Y, d) is an n-point metric space and X ⊆ Y is a k-point subset.

Claim 5.2. There exists a polynomial-time algorithm (in terms of n) which, given X and Y, computes a map f : Y → L_{2} such that f|_{X} has minimal distortion among all 1-Lipschitz maps f.

Proof. We give a semi-definite program computing the optimal f, which can be solved in polynomial time using the methods of [17].

\underline{SDP (5.1)}
max  ε
s.t. x_{u} ∈ ℝ^{n} ∀u ∈ Y
∥x_{u} − x_{v}∥_{2}^{2} ≤ d(u, v)^{2}  ∀u, v ∈ Y
∥x_{u} − x_{v}∥_{2}^{2} ≥ ε d(u, v)^{2}  ∀u, v ∈ X

5.2 The Sparsest Cut

Let V be an n-point set with two symmetric weights on pairs w_{N}, w_{D} : V ×V → ℝ_{+} (i.e. w_{N}(x, y) = w_{N}(y, x) and w_{D}(x, y) = w_{D}(y, x)). For a subset S ⊆ V, we define the sparsity of S by

Φ_{w_{N} ,w_{D}}(S) = \frac{∑_{u∈S,v∈V \S} w_{N}(u, v)}{∑_{u∈S,v∈V \S} w_{D}(u, v)},

and we let Φ^{∗}(V, w_{N}, w_{D}) = min_{S⊆V} Φ_{w_{N} ,w_{D}}(S). (The set V is usually thought of as the vertex set of a graph with w_{N}(u, v) supported only on edges (u, v), but this is unnecessary since we allow arbitrary weight functions.)

Computing the value of Φ^{∗}(V, w_{N}, w_{D}) is NP-hard [30]. The following semi-definite program is well known to be a relaxation of Φ^{∗}(V, w_{N}, w_{D}) (see e.g. [16]).

\underline{SDP (5.2)}
min ∑_{u,v∈V} w_{N}(u, v) ∥x_{u} − x_{v}∥_{2}^{2}
s.t. x_{u} ∈ ℝ^{n}  ∀u ∈ V
∑_{u,v∈V} w_{D}(u, v) ∥x_{u} − x_{v}∥_{2}^{2} = 1
∥x_{u} − x_{v}∥_{2}^{2} ≤ ∥x_{u} − x_{w}∥_{2}^{2} + ∥x_{w} − x_{v}∥_{2}^{2}
∀u, v, w ∈ V

Furthermore, an optimal solution to this SDP can be computed in polynomial time [17, 16].

The algorithm. We now give our algorithm for rounding SDP (5.2). Suppose that the weight function w_{D} is supported only on pairs u, v for which u, v ∈ U ⊆ V, and let k = |U|. Denote M = 20 log n.

1. Solve SDP (5.2), yielding a solution {x_{u}}_{u∈V} ⊆ ℝ^{n}.

2. Consider the metric space (V, d) given by d(u, v) = ∥x_{u} − x_{v}∥_{2}^{2}.

3. Applying SDP (5.1) to U and (V, d) (where Y = V and X = U), compute the optimal map f : V → ℝ^{n}.

4. Choose β_{1}, …, β_{M} ∈ {−1, +1}^{n} independently and uniformly at random.

5. For each 1 ≤ i ≤ M, arrange the points of V as v_{1}^{i}, …, v_{n}^{i} so that

⟨β_{i}, f(v_{j}^{i})⟩ ≤ ⟨β_{i}, f(v_{j+1}^{i})⟩ for each 1 ≤ j ≤ n − 1.

6. Output the sparsest of the Mn cuts

({v_{1}^{i}, …, v_{m}^{i}}, {v_{m+1}^{i}, …, v_{n}^{i}}), 1 ≤ m ≤ n − 1, 1 ≤ i ≤ M.

Claim 5.3. With constant probability over the choice of β_{1}, …, β_{M}, the cut (S, V \ S) returned by the algorithm has

Φ_{w_{N} ,w_{D}}(S) ≤ O (\sqrt{log k} log log k) Φ^{∗}(V, w_{N}, w_{D}).  (13)

Proof. Let S ⊆ ℝ^{n} be the image of V under the map f. Consider the map g : S → ℓ_{1}^{M} given by g(x) = (⟨β_{1}, x⟩, …, ⟨β_{M}, x⟩). It is well-known (see, e.g. [1, 32]) that, with constant probability over the choice of {β_{i}}_{i=1}^{M} ⊆ S^{n−1}, g has distortion O(1) (where S is equipped with the Euclidean metric). In this case, we claim that (13) holds.

To see this, let S_{1}, S_{2}, …, S_{Mn} ⊆ V be the Mn cuts which are tested in line (6). It is a standard fact [27, 12] that there exist constants α_{1}, α_{2}, …, α_{Mn} ≥ 0 such that for every x, y ∈ V,

||g(f(x)) − g(f(y))||_{1} = ∑_{i=1}^{Mn} α_{i}ρ_{S_{i}}(x, y),

where ρ_{S_{i}}(x, y) = 1 if x and y are on opposite sides of the cut (S_{i}, V \ S_{i}) and ρ_{S_{i}}(x, y) = 0 otherwise.

Assume (by scaling) that g ∘ f : Y → ℓ_{1}^{M} is 1-Lipschitz. Let Λ be the distortion of g ∘ f. By Corollary 5.1, Λ = O (\sqrt{log k} log log k). Recalling that w_{D}(u, v) > 0 only when u, v ∈ U,

Φ^{∗}(V, w_{N}, w_{D}) ≥ \frac{∑_{u,v∈V} w_{N}(u, v)∥x_{u} − x_{v}∥_{2}^{2}}{∑_{u,v∈U} w_{D}(u, v)∥x_{u} − x_{v}∥_{2}^{2}}

≥ \frac{1}{Λ} \frac{∑_{u,v∈V} w_{N}(u, v) ||g(f(u)) − g(f(v))||_{1}}{∑_{u,v∈U} w_{D}(u, v) ||g(f(u)) − g(f(v))||_{1}}

= \frac{1}{Λ} \frac{∑_{i=1}^{Mn} α_{i} ∑_{u,v∈V} w_{N}(u, v)ρ_{S_{i}}(u, v)}{∑_{i=1}^{Mn} α_{i} ∑_{u,v∈U} w_{D}(u, v)ρ_{S_{i}}(u, v)}

≥ \frac{1}{Λ} min_{i} \frac{∑_{u,v∈V} w_{N}(u, v)ρ_{S_{i}}(u, v)}{∑_{u,v∈U} w_{D}(u, v)ρ_{S_{i}}(u, v)}
= \frac{Φ_{w_{N} ,w_{D}}(S)}{Λ}.

This completes the proof.

6 Concluding remarks

• There are two factors of O(\sqrt{log log n}) which keep our bound from being optimal up to a constant factor. One factor of \sqrt{log log n} arises because Theorem 4.5 is applied with A, B ∼ polylog(n). The need for such values arises out of a certain non-locality property which seems inherent to the method of proof in [4]. We remark that achieving A = O(1) is probably possible, and it seems that B is the difficult factor.

The other factor arises because, in proving Theorem 1.1, we invoke Theorem 4.5 for O(log log n) different values of the parameter K. It is likely removable by a more technical induction, but we chose to present the simpler proof.

• It is an interesting open problem to understand the exact distortion required to embed n-point negative type metrics into L_{1}. As mentioned, the best-known lowerbound is Ω(log log n)^{δ} [20]. We also note that assuming a strong form of the Unique Games Conjecture is true, the general Sparsest Cut problem is hard to approximate within a factor of Ω (log log n) [11, 20].

• For the uniform case of Sparsest Cut, it is possible to achieve a O(\sqrt{log n}) approximation in quadratic time without solving an SDP [3]. Whether such an algorithm exists for the general case is an open problem.

• There is no asymptotic advantage in embedding n-point negative type metrics into L_{p} for some p ∈ (1, ∞), p ≠ 2 (observe that since L_{2} is isometric to a subset of L_{p} for all p ≥ 1, our embedding into Hilbert space is automatically also an embedding into L_{p}). Indeed, for 1 < p < 2 it is shown in [24] that there are arbitrarily large n-point subsets of L_{1} that require distortion Ω(\sqrt{(p − 1) log n}) in any embedding into L_{p}. For 2 < p < ∞ it follows from [35, 33] that there are arbitrarily large n-point subsets of L_{1} whose minimal distortion into L_{p} is 1+Θ (\sqrt{\frac{log n}{p}}) (the dependence on n follows from [35], and the optimal dependence on p follows from the results of [33]). Thus, up to multiplicative constants depending on p (and the double logarithmic factor in Theorem 1.1), our result is optimal for all p ∈ (1, ∞).

• Let (X, d_{X}), (Y, d_{Y}) be metric spaces and η : [0, ∞) → [0, ∞) a strictly increasing function. A one to one mapping f : X ↪ Y is called a quasisymmetric embedding with modulus η if for every x, a, b ∈ X such that x ≠ b,

\frac{d_{Y} (f(x), f(a))}{d_{Y} (f(x), f(b))} ≤ η (\frac{d_{X}(x, a)}{d_{X}(x, b)}) .

We refer to [18] for an account of the theory of quasisymmetric embeddings. Observe that metrics of negative type embed quasisymmetrically into Hilbert space. It turns out that our embedding result generalizes to any n point metric space which embeds quasisymmetrically into Hilbert space. Indeed, if (X, d) embeds quasisymmetrically into L_{2} with modulus η then, as shown in the full version of [22], there exists constants p = p(η) and C = C(η), depending only on η, such that ζ(X; p) ≤ C\sqrt{log n}.

Acknowledgements

We thank Satish Rao for useful discussions.

References

[1] D. Achlioptas. Database-friendly random projections: Johnson-Lindenstrauss with binary coins. J. Comput. System Sci., 66(4):671–687, 2003. Special issue on PODS 2001 (Santa Barbara, CA).

[2] A. Agrawal, P. Klein, R. Ravi, and S. Rao. Approximation through multicommodity flow. In 31st Annual Symposium on Foundations of Computer Science, pages 726–737. IEEE Computer Soc., Los Alamitos, CA, 1990.

[3] S. Arora, E. Hazan, and S. Kale. O(\sqrt{log n}) approximation to SPARSEST CUT in Õ(n^{2}) time. In 45th Annual Syposium on Foundations of Computer Science, pages 238–247. IEEE Computer Society, 2004.

[4] S. Arora, S. Rao, and U. Vazirani. Expander flows, geometric embeddings, and graph partitionings. In 36th Annual Symposium on the Theory of Computing, pages 222–231, 2004.

[5] Y. Aumann and Y. Rabani. An O(log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput., 27(1):291–301 (electronic), 1998.

[6] Y. Bartal. Probabilistic approximations of metric space and its algorithmic application. In 37th Annual Symposium on Foundations of Computer Science, pages 183–193, Oct. 1996.

[7] J. Bourgain. On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math., 52(1-2):46–52, 1985.

[8] 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, pages 514–523, 2003.

[9] G. Calinescu, H. Karloff, and Y. Rabani. Approximation algorithms for the 0-extension problem. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 8–16, Philadelphia, PA, 2001.

[10] S. Chawla, A. Gupta, and H. Räcke. Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 102–111, Vancouver, 2005.

[11] S. Chawla, R. Krauthgamer, R. Kumar, Y. Rabani, and D. Sivakumar. On embeddability of negative type metrics into ℓ_{1}. In Proceedings of the 20th Annual IEEE Conference on Computational Complexity, pages 144–153, 2005.

[12] M. M. Deza and M. Laurent. Geometry of cuts and metrics, volume 15 of Algorithms and Combinatorics. Springer-Verlag, Berlin, 1997.

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

[14] J. Fakcharoenphol, S. Rao, and K. Talwar. A tight bound on approximating arbitrary metrics by tree metrics. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pages 448–455, 2003.

[15] T. Figiel, J. Lindenstrauss, and V. D. Milman. The dimension of almost spherical sections of convex bodies. Acta Math., 139(1-2):53–94, 1977.

[16] M. X. Goemans. Semidefinite programming and combinatorial optimization. Mathematical Programming, 49:143–161, 1997.

[17] M. Grötschel, L. L. Lovász, and A. Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1:169–197, 1981.

[18] J. Heinonen. Lectures on analysis on metric spaces. Universitext. Springer-Verlag, New York, 2001.

[19] 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.

[20] S. Khot and N. Vishnoi. The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into ℓ_{1}. In Proceedings of the 46th Annual IEEE Conference on Foundations of Computer Science, 2005. To appear.

[21] R. Krauthgamer, J. R. Lee, M. Mendel, and A. Naor. Measured descent: A new embedding method for finite metrics. Geom. Funct. Anal., 2004. To appear.

[22] J. R. Lee. On distance scales, embeddings, and efficient relaxations of the cut cone. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 92– 101, Vancouver, 2005.

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

[24] 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.

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

[26] T. Leighton and S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM, 46(6):787–832, 1999.

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

[28] N. Linial and M. Saks. Low diameter graph decompositions. Combinatorica, 13(4):441–454, 1993.

[29] J. Matoušek. Lectures on discrete geometry, volume 212 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2002.

[30] D. W. Matula and F. Shahrokhi. The maximum concurrent flow problem. J. ACM, 37(2):318– 334, 1990.

[31] M. Mendel and A. Naor. Euclidean quotients of finite metric spaces. Adv. Math., 189(2):451– 494, 2004.

[32] 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.

[33] A. Naor, Y. Peres, O. Schramm, and S. Sheffield. Markov chains in smooth normed spaces and Gromov hyperbolic metric spaces. Preprint, 2004.

[34] A. Naor, Y. Rabani, and A. Sinclair. Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs. J. Funct. Anal. To appear.

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

[36] S. Rao. Small distortion and volume preserving embeddings for planar and Euclidean metrics. In Proceedings of the 15th Annual Symposium on Computational Geometry, pages 300–306, New York, 1999.

[37] D. B. Shmoys. Cut problems and their application to divide-and-conquer. In Approximation Algorithms for NP-hard Problems, (D.S. Hochbaum, ed.), pages 192–235. PWS, 1997.

[38] V. V. Vazirani. Approximation algorithms. Springer-Verlag, Berlin, 2001.