Proceedings of the International Congress of Mathematicians Hyderabad, India, 2010

L_{1} embeddings of the Heisenberg group and fast estimation of graph isoperimetry

Assaf Naor^{∗}

Abstract. We survey connections between the theory of bi-Lipschitz embeddings and the Sparsest Cut Problem in combinatorial optimization. The story of the Sparsest Cut Problem is a striking example of the deep interplay between analysis, geometry, and probability on the one hand, and computational issues in discrete mathematics on the other. We explain how the key ideas evolved over the past 20 years, emphasizing the interactions with Banach space theory, geometric measure theory, and geometric group theory. As an important illustrative example, we shall examine recently established connections to the structure of the Heisenberg group, and the incompatibility of its Carnot-Carathéodory geometry with the geometry of the Lebesgue space L_{1}.

Mathematics Subject Classification (2000). 46B85, 30L05, 46B80, 51F99.

Keywords. Bi-Lipschitz embeddings, Sparsest Cut Problem, Heisenberg group.

1. Introduction

Among the common definitions of the Heisenberg group ℍ, it will be convenient for us to work here with ℍ modeled as ℝ^{3}, equipped with the group product

(a, b, c) · (a′, b′, c′) =^{def} (a + a′, b + b′, c + c′ + ab′ − ba′). The integer lattice ℤ^{3} is

then a discrete cocompact subgroup of ℍ, denoted by ℍ(ℤ), which is generated by the finite symmetric set {(±1, 0, 0), (0, ±1, 0), (0, 0, ±1)}. The word metric on ℍ(ℤ) induced by this generating set will be denoted by d_{W}.

As noted by Semmes [66], a differentiability result of Pansu [61] implies that the metric space (ℍ(ℤ), d_{W}) does not admit a bi-Lipschitz embedding into ℝ^{n} for any n ∈ ℕ. This was extended by Pauls [62] to bi-Lipschitz non-embeddability results of (ℍ(ℤ), d_{W}) into metric spaces with either lower or upper curvature bounds in the sense of Alexandrov. In [52, 27] it was observed that Pansu’s differentiability argument extends to Banach space targets with the Radon-Nikodým property (see [14, Ch. 5]), and hence ℍ does not admit a bi-Lipschitz embedding into, say, a Banach space which is either reflexive or is a separable dual; in particular ℍ does not admit a bi-Lipschitz embedding into any L_{p}(μ) space, 1 < p < ∞, or into the sequence space ℓ_{1}.

∗Research supported in part by NSF grants CCF-0635078 and CCF-0832795, BSF grant 2006009, and the Packard Foundation.

The embeddability of ℍ(ℤ) into the function space L_{1}(μ), when μ is non-atomic, turned out to be much harder to settle. This question is of particular importance since it is well understood that for μ non-atomic, L_{1}(μ) is a space for which the differentiability results quoted above manifestly break down. Nevertheless, Cheeger and Kleiner [26, 25] introduced a novel notion of differentiability for which they could prove a differentiability theorem for Lipschitz maps from the Heisenberg group to L_{1}(μ), thus establishing that ℍ(ℤ) does not admit a bi-Lipschitz embedding into any L_{1}(μ) space.

Another motivation for the L_{1}(μ) embeddability question for ℍ(ℤ) originates from [52], where it was established that it is connected to the Sparsest Cut Problem in the field of combinatorial optimization. For this application it was of importance to obtain quantitative estimates in the L_{1}(μ) non-embeddability results for ℍ(ℤ). It turns out that establishing such estimates is quite subtle, as they require overcoming finitary issues that do not arise in the infinite setting of [25, 28]. The following two theorems were proved in [29, 30]. Both theorems follow painlessly from a more general theorem that is stated and discussed in Section 5.4.

Theorem 1.1. There exists a universal constant c > 0 such that any embedding into L_{1}(μ) of the restriction of the word metric d_{W} to the n×n×n grid {1, …, n}^{3} incurs distortion ≳ (log n)^{c}.

Following Gromov [38], the compression rate of f : ℍ(ℤ) → L_{1}(μ), denoted ω_{f}(·), is defined as the largest non-decreasing function such that for all x, y ∈ ℍ(ℤ) we have ∥f(x)−f(y)∥_{1} ⩾ ω_{f}(d_{W} (x, y)) (see [7] for more information on this topic).

Theorem 1.2. There exists a universal constant c > 0 such that for every function f : ℍ(ℤ) → L_{1}(μ) which is 1-Lipschitz with respect to the word metric d_{W}, we have ω_{f}(t) ≲ t/(log t)^{c} for arbitrarily large t.

Evaluating the supremum of those c > 0 for which Theorem 1.1 holds true remains an important open question, with geometric significance as well as importance to theoretical computer science. Conceivably we could get c in Theorem 1.1 to be arbitrarily close to \frac{1}{2}, which would be sharp since the results of [8, 64] imply (see the explanation in [41]) that the metric space ({1, …, n}^{3}, d_{W} ) embeds into ℓ_{1} with distortion ≲ \sqrt{log n}. Similarly, we do not know the best possible c in Theorem 1.2; \frac{1}{2} is again the limit here since it was shown in [69] that there exists a 1-Lipschitz mapping f : ℍ(ℤ) → ℓ_{1} for which ω_{f}(t) ≳ t/(\sqrt{log t} · log log t).

The purpose of this article is to describe the above non-embeddability results for the Heisenberg group. Since one of the motivations for these investigations is the application to the Sparsest Cut Problem, we also include here a detailed discussion of this problem from theoretical computer science, and its deep connections to metric geometry. Our goal is to present the ideas in a way that is accessible to mathematicians who do not necessarily have background in computer science.

Acknowledgements. I am grateful to the following people for helpful comments and suggestions on earlier versions of this manuscript: Tim Austin, Keith Ball, Subhash Khot, Bruce Kleiner, Russ Lyons, Manor Mendel, Mikhail Ostrovskii, Gideon Schechtman, Lior Silberman.

2. Embeddings

A metric space (ℳ , d_{ℳ} ) is said to embed with distortion D ⩾ 1 into a metric space (𝒴 , d_{𝒴} ) if there exists a mapping f : ℳ → 𝒴 , and a scaling factor s > 0, such that for all x, y ∈ ℳ we have sd_{ℳ} (x, y) ⩽ d_{𝒴} (f(x), f(y)) ⩽ Dsd_{ℳ} (x, y). The infimum over those D ⩾ 1 for which (ℳ , d_{ℳ} ) embeds with distortion D into (𝒴 , d_{𝒴} ) is denoted by c_{𝒴} (ℳ). If (ℳ , d_{ℳ} ) does not admit a bi-Lipschitz embedding into (𝒴 , d_{𝒴} ), we will write c_{𝒴} (ℳ) = ∞.

Throughout this paper, for p ⩾ 1, the space L_{p} will stand for L_{p}([0, 1], λ), where λ is Lebesgue measure. The spaces ℓ_{p} and ℓ_{p}^{n} will stand for the space of p-summable infinite sequences, and ℝ^{n} equipped with the ℓ_{p} norm, respectively. Much of this paper will deal with bi-Lipschitz embeddings of finite metric spaces into L_{p}. Since every n-point subset of an L_{p}(Ω, μ) space embeds isometrically into ℓ_{p}^{n(n−1)/2} (see the discussion in [12]), when it comes to embeddings of finite metric spaces, the distinction between different L_{p}(Ω, μ) spaces is irrelevant. Nevertheless, later, in the study of the embeddability of the Heisenberg group, we will need to distinguish between sequence spaces and function spaces.

For p ⩾ 1 we will use the shorter notation c_{p}(ℳ) = c_{L_{p}}(ℳ). The parameter c_{2}(ℳ) is known as the Euclidean distortion of ℳ. Dvoretzky’s theorem says that if 𝒴 is an infinite dimensional Banach space then c_{𝒴} (ℓ_{2}^{n}) = 1 for all n ∈ ℕ. Thus, for every finite metric space ℳ and every infinite dimensional Banach space 𝒴 , we have c_{2}(ℳ) ⩾ c_{𝒴} (ℳ).

The following famous theorem of Bourgain [15] will play a key role in what follows:

Theorem 2.1 (Bourgain’s embedding theorem [15]). For every n-point metric space (ℳ , d_{ℳ} ), we have

c_{2}(ℳ) ≲ log n.  (1)

Bourgain proved in [15] that the estimate (1) is sharp up to an iterated logarithm factor, i.e., that there exist arbitrarily large n-point metric spaces ℳ_{n} for which c_{2}(ℳ_{n}) ≳ \frac{log n}{log log n}. The log log n term was removed in the important paper [56] of Linial, London and Rabinovich, who showed that the shortest path metric on bounded degree n-vertex expander graphs has Euclidean distortion ≳ log n.

If one is interested only in embeddings into infinite dimensional Banach spaces, then Theorem 2.1 is stated in the strongest possible form: as noted above, it implies that for every infinite dimensional Banach space 𝒴 , we have c_{𝒴} (ℳ) ≲ log n. Below, we will actually use Theorem 2.1 for embeddings into L_{1}, i.e., we will use the fact that c_{1}(ℳ) ≲ log n. The expander based lower bound of Linial, London and Rabinovich [56] extends to embeddings into L_{1} as well, i.e., even this weaker form of Bourgain’s embedding theorem is asymptotically sharp. We refer to [58, Ch. 15] for a comprehensive discussion of these issues, as well as a nice presentation of the proof of Bourgain’s embedding theorem.

3. L_{1} as a metric space

Let (Ω, μ) be a measure space. Define a mapping T : L_{1}(Ω, μ) → L_{∞}(Ω×ℝ, μ×λ), where λ is Lebesgue measure, by:

T (f)(ω, x) =^{def} \{ \begin{matrix}1 & 0 < x ⩽ f(ω), \\ −1 & f(ω) < x < 0, \\ 0 & otherwise. \end{matrix}

For all f, g ∈ L_{1}(Ω, μ) we have:

|T (f)(ω, x) − T (g)(ω, x)| = \{ \begin{matrix}1 & g(ω) < x ⩽ f(ω) or f(ω) < x ⩽ g(ω), \\ 0 & otherwise. \end{matrix}

Thus, for all p > 0 we have,

∥T (f) − T (g)∥_{L_{p}(Ω×ℝ,μ×λ)}^{p} = ∫_{Ω} (∫_{(g(ω),f(ω)]⊔(f(ω),g(ω)]} dλ) dμ(ω)

= ∫_{Ω} |f(ω) − g(ω)|dμ(ω) = ∥f − g∥_{L_{1}(Ω,μ)}. (2)

Specializing (2) to p = 2, we see that:

∥T (f) − T (g)∥_{L_{2}(Ω×ℝ,μ×λ)} = \sqrt{∥f − g∥_{L_{1}(Ω,μ)}}.

Corollary 3.1. The metric space (L_{1}(Ω, μ), ∥f − g∥_{L_{1}(Ω,μ)}^{1/2}) admits an isometric embedding into Hilbert space.

Another useful corollary is obtained when (2) is specialized to the case p = 1. Take an arbitrary finite subset X ⊆ L_{1}(Ω, μ). For every (ω, x) ∈ Ω × ℝ consider the set S(ω, x) = {f ∈ X : x ⩽ f(ω)} ⊆ X. For every S ⊆ X we can define a measurable subset E_{S} = {(ω, x) ∈ Ω × ℝ : S(ω, x) = S} ⊆ Ω × ℝ. By the definition of T, for every f, g ∈ X we have

∥f − g∥_{L_{1}(Ω,μ)} =^{(2)} ∥T (f) − T (g)∥_{L_{1}(Ω×ℝ,μ×λ)}
= ∫_{Ω×ℝ} |1_{S(w,x)}(f) − 1_{S(w,x)}(g)| d(μ × λ)(ω, x)
= ∑_{S⊆X}(μ × λ)(E_{S})|1_{S}(f) − 1_{S}(g)|,

where here, and in what follows, 1_{S}(·) is the characteristic function of S. Writing β_{S} = (μ × λ)(E_{S}), we have the following important corollary:

Corollary 3.2. Let X ⊆ L_{1}(Ω, μ) be a finite subset of L_{1}(Ω, μ). Then there exist nonnegative numbers {β_{S}}_{S⊆X} ⊆ [0, ∞) such that for all f, g ∈ X we have:

∥f − g∥_{L_{1}(Ω,μ)} = ∑_{S⊆X} β_{S}|1_{S}(f) − 1_{S}(g)|.  (3)

A metric space (ℳ , d_{ℳ} ) is said to be of negative type if the metric space (ℳ , d_{ℳ}^{1/2}) admits an isometric embedding into Hilbert space. Such metrics will play a crucial role in the ensuing discussion. This terminology (see e.g., [33]) is due to a classical theorem of Schoenberg [65], which asserts that (ℳ , d_{ℳ} ) is of negative type if and only if for every n ∈ ℕ and every x_{1}, …, x_{n} ∈ X, the matrix (d_{ℳ} (x_{i}, x_{j}))_{i,j=1}^{n} is negative semidefinite on the orthogonal complement of the main diagonal in ℂ^{n}, i.e., for all ζ_{1}, …, ζ_{n} ∈ ℂ with ∑_{j=1}^{n} ζ_{j} = 0 we have ∑_{i=1}^{n} ∑_{j=1}^{n} ζ_{i}\overline{ζ_{j}}d_{ℳ} (x_{i}, x_{j}) ⩽ 0. Corollary (3.1) can be restated as saying that L_{1}(Ω, μ) is a metric space of negative type.

Corollary (3.2) is often called the cut cone representation of L_{1} metrics. To explain this terminology, consider the set 𝒞 ⊆ ℝ^{n^{2}} of all n × n real matrices A = (a_{ij}) such that there is a measure space (Ω, μ) and f_{1}, …, f_{n} ∈ L_{1}(Ω, μ) with a_{ij} = ∥f_{i} − f_{j}∥_{L_{1}(Ω,μ)} for all i, j ∈ {1, …, n}. If f_{1}, …, f_{n} ∈ L_{1}(Ω_{1}, μ_{1}) and g_{1}, …, g_{n} ∈ L_{1}(Ω_{2}, μ_{2}) then for all c_{1}, c_{2} ⩾ 0 and i, j ∈ {1, …, n} we have

c_{1}∥f_{i} − f_{j}∥_{L_{1}(Ω_{1},μ_{1})} + c_{2}∥g_{i} − g_{j}∥_{L_{1}(Ω_{2},μ_{2})} = ∥h_{i} − h_{j}∥_{L_{1}(Ω_{1}⊔Ω_{2},μ_{1}⊔μ_{2})},

where h_{1}, …, h_{n} are functions defined on the disjoint union Ω_{1} ⊔ Ω_{2} as follows: h_{i}(ω) = c_{1}f_{i}(ω)1_{Ω_{1}}(ω) + c_{2}g_{i}(ω)1_{Ω_{2}}(ω). This observation shows that 𝒞 is a cone (of dimension n(n − 1)/2). Identity (3) says that the cone 𝒞 is generated by the rays induced by cut semimetrics, i.e., by matrices of the form a_{ij} = |1_{S}(i) − 1_{S}(j)| for some S ⊆ {1, …, n}. It is not difficult to see that these rays are actually the extreme rays of the cone 𝒞. Carathéodory’s theorem (for cones) says that we can choose the coefficients {β_{S}}_{S⊆X} in (3) so that only n(n−1)/2 of them are non-zero.

4. The Sparsest Cut Problem

Given n ∈ ℕ and two symmetric functions C, D : {1, …, n} × {1, …, n} → [0, ∞) (called capacities and demands, respectively), and a subset ∅ ≠ S ⊊ {1, …, n}, write

Φ(S) =^{def} \frac{∑_{i=1}^{n} ∑_{j=1}^{n} C(i, j) · |1_{S}(i) − 1_{S}(j)|}{∑_{i=1}^{n} ∑_{j=1}^{n} D(i, j) · |1_{S}(i) − 1_{S}(j)|}.  (4)

The value

Φ^{∗}(C, D) =^{def} min_{∅≠S⊊{1,...,n}} Φ(S)  (5)

is the minimum over all cuts (two-part partitions) of {1, …, n} of the ratio between the total capacity crossing the boundary of the cut and the total demand crossing the boundary of the cut.

Finding in polynomial time a cut for which Φ^{∗}(C, D) is attained up to a definite multiplicative constant is called the Sparsest Cut problem. This problem is used as a subroutine in many approximation algorithms for NP-hard problems; see the survey articles [68, 22], as well as [53, 1] and the references in [6, 5] for some of the vast literature on this topic. Computing Φ^{∗}(C, D) exactly has been long known to be NP-hard [67]. More recently, it was shown in [31] that there exists ε_{0} > 0 such that it is NP-hard to approximate Φ^{∗}(C, D) to within a factor smaller than 1 + ε_{0}. In [47, 24] it was shown that it is Unique Games hard to approximate Φ^{∗}(C, D) to within any constant factor (see [44, 45] for more information on the Unique Games Conjecture; we will return to this issue in Section 4.3.3).

It is customary in the literature to highlight the support of the capacities function C: this allows us to introduce a particulary important special case of the Sparsest Cut Problem. Thus, a different way to formulate the above setup is via an n-vertex graph G = (V, E), with a positive weight (called a capacity) C(e) associated to each edge e ∈ E, and a nonnegative weight (called a demand) D(u, v) associated to each pair of vertices u, v ∈ V. The goal is to evaluate in polynomial time (and in particular, while examining only a negligible fraction of the subsets of V) the quantity:

Φ^{∗}(C, D) = min_{∅≠S⊊V} \frac{∑_{uv∈E} C(uv) |1_{S}(u) − 1_{S}(v)|}{∑_{u,v∈V} D(u, v) |1_{S}(u) − 1_{S}(v)|} .

To get a feeling for the meaning of Φ^{∗}, consider the case C(e) = D(u, v) = 1 for all e ∈ E and u, v ∈ V. This is an important instance of the Sparsest Cut problem which is called “Sparsest Cut with Uniform Demands”. In this case Φ^{∗} becomes:

Φ^{∗} = min_{∅≠S⊊V} \frac{#\{edges joining S and V \ S\}}{|S| · |V \ S|} .

Thus, in the case of uniform demands, the Sparsest Cut problem essentially amounts to solving efficiently the combinatorial isoperimetric problem on G: determining the subset of the graph whose ratio of edge boundary to its size is as small as possible.

In the literature it is also customary to emphasize the size of the support of the demand function D, i.e., to state bounds in terms of the number k of pairs {i, j} ⊆ {1, …, n} for which D(i, j) > 0. For the sake of simplicity of exposition, we will not adopt this convention here, and state all of our bounds in terms of n rather than the number of positive demand pairs k. We refer to the relevant references for the simple modifications that are required to obtain bounds in terms of k alone.

From now on, the Sparsest Cut problem will be understood to be with general capacities and demands; when discussing the special case of uniform demands we will say so explicitly. In applications, general capacities and demands are used to tune the notion of “interface” between S and V \S to a wide variety of combinatorial optimization problems, which is one of the reasons why the Sparsest Cut problem is so versatile in the field of approximation algorithms.

4.1. Reformulation as an optimization problem over L_{1}. Al-

though the Sparsest Cut Problem clearly has geometric flavor as a discrete isoperimetric problem, the following key reformulation of it, due to [11, 56], explicitly relates it to the geometry of L_{1}.

Lemma 4.1. Given symmetric C, D : {1, …, n} × {1, …, n} → [0, ∞), we have:

Φ^{∗}(C, D) = min_{f_{1},...,f_{n}∈L_{1}} \frac{∑_{i=1}^{n} ∑_{j=1}^{n} C(i, j)∥f_{i} − f_{j}∥_{1}}{∑_{i=1}^{n} ∑_{j=1}^{n} D(i, j)∥f_{i} − f_{j}∥_{1}} .  (6)

Proof. Let ϕ denote the right hand side of (6), and write Φ^{∗} = Φ^{∗}(C, D). Given a subset S ⊆ {1, …, n}, by considering f_{i} = 1_{S}(i) ∈ {0, 1} ⊆ L_{1} we see that that ϕ ⩽ Φ^{∗}. In the reverse direction, if X = {f_{1}, …, f_{n}} ⊆ L_{1} then let {β_{S}}_{S⊆X} be the non-negative weights from Corollary 3.2. For S ⊆ X define a subset of {1, …, n} by S′ = {i ∈ {1, …, n} : f_{i} ∈ S}. It follows from the definition of Φ^{∗} that for all S ⊆ X we have,

∑_{i=1}^{n} ∑_{j=1}^{n} C(i, j)|1_{S}(f_{i}) − 1_{S}(f_{j})| =^{(4)} Φ(S′) ∑_{i=1}^{n} ∑_{j=1}^{n} D(i, j)|1_{S}(f_{i}) − 1_{S}(f_{j})|

⩾^{(5)} Φ^{∗} ∑_{i=1}^{n} ∑_{j=1}^{n} D(i, j)|1_{S}(f_{i}) − 1_{S}(f_{j})|. (7)

Thus

∑_{i=1}^{n} ∑_{j=1}^{n} C(i, j)∥f_{i} − f_{j}∥_{1} =^{(3)} ∑_{S⊆X} β_{S} ∑_{i=1}^{n} ∑_{j=1}^{n} C(i, j)|1_{S}(f_{i}) − 1_{S}(f_{j})|

⩾^{(7)} Φ^{∗} ∑_{S⊆X} β_{S} ∑_{i=1}^{n} ∑_{j=1}^{n} D(i, j)|1_{S}(f_{i}) − 1_{S}(f_{j})| =^{(3)} ∑_{i=1}^{n} ∑_{j=1}^{n} D(i, j)∥f_{i} − f_{j}∥_{1}.

It follows that ϕ ⩾ Φ^{∗}, as required.

4.2. The linear program. Lemma 4.1 is a reformulation of the Sparsest Cut Problems in terms of a continuous optimization problem on the space L_{1}. Being a reformulation, it shows in particular that solving L_{1} optimization problems such as the right hand side of (6) is NP-hard.

In the beautiful paper [53] of Leighton and Rao it was shown that there exists a polynomial time algorithm that, given an n-vertex graph G = (V, E), computes a number which is guaranteed to be within a factor of ≲ log n of the uniform Sparsest Cut value (4). The Leighton-Rao algorithm uses combinatorial ideas which do not apply to Sparsest Cut with general demands. A breakthrough result, due to Linial-London-Rabinovich [56] and Aumann-Rabani [9], introduced embedding methods to this field, yielding a polynomial time algorithm which computes Φ^{∗}(C, D) up to a factor ≲ log n for all C, D : {1, …, n} × {1, …, n} → [0, ∞).

The key idea of [56, 9] is based on replacing the finite subset {f_{1}, …, f_{n}} of L_{1} in (6) by an arbitrary semimetric on {1, …, n}. Specifically, by homogeneity we can always assume that the denominator in (6) equals 1, in which case Lemma 4.1 says that Φ^{∗}(C, D) equals the minimum of ∑_{i=1}^{n} ∑_{j=1}^{n} C(i, j)d_{ij}, given that ∑_{i=1}^{n} ∑_{j=1}^{n} D(i, j)d_{ij} = 1 and there exist f_{1}, …, f_{n} ∈ L_{1} for which d_{ij} = ∥f_{i} − f_{j}∥_{1} for all i, j ∈ {1, …, n}. We can now ignore the fact that d_{ij} was a semimetric that came from a subset of L_{1}, i.e., we can define M^{∗}(C, D) to be the minimum of ∑_{i=1}^{n} ∑_{j=1}^{n} C(i, j)d_{ij}, given that ∑_{i=1}^{n} ∑_{j=1}^{n} D(i, j)d_{ij} = 1, d_{ii} = 0, d_{ij} ⩾ 0, d_{ij} = d_{ji} for all i, j ∈ {1, …, n} (n(n − 1)/2 symmetry constraints) and d_{ij} ⩽ d_{ik} + d_{kj} for all i, j, k ∈ {1, …, n} (⩽ n^{3} triangle inequality constraints).

Clearly M^{∗}(C, D) ⩽ Φ^{∗}(C, D), since we are minimizing over all semimetrics rather than just those arising from subsets of L_{1}. Moreover, M^{∗}(C, D) can be computed in polynomial time up to arbitrarily good precision [40], since it is a linear program (minimizing a linear functional in the variables (d_{ij}) subject to polynomially many linear constraints).

The linear program produces a semimetric d_{ij}^{∗} on {1, …, n} which satisfies M^{∗}(C, D) = ∑_{i=1}^{n} ∑_{j=1}^{n} C(i, j)d_{ij}^{∗} and ∑_{i=1}^{n} ∑_{j=1}^{n} D(i, j)d_{ij}^{∗} = 1 (ignoring arbitrarily small errors). By Lemma 4.1 we need to somehow relate this semimetric to L_{1}. It is at this juncture that we see the power of Bourgain’s embedding theorem 2.1: the constraints of the linear program only provide us the information that d_{ij}^{∗} is a semimetric, and nothing else. So, we need to be able to somehow handle arbitrary metric spaces—precisely what Bourgain’s theorem does, by furnishing f_{1}, …, f_{n} ∈ L_{1} such that for all i, j ∈ {1, …, n} we have

\frac{d_{ij}^{∗}}{log n} ≲ ∥f_{i} − f_{j}∥_{1} ⩽ d_{ij}^{∗}.  (8)

Now,

Φ^{∗}(C, D) ⩽^{(6)} \frac{∑_{i=1}^{n} ∑_{j=1}^{n} C(i, j)∥f_{i} − f_{j}∥_{1}}{∑_{i=1}^{n} ∑_{j=1}^{n} D(i, j)∥f_{i} − f_{j}∥_{1}}

≲^{(8)} log n · \frac{∑_{i=1}^{n} ∑_{j=1}^{n} C(i, j)d_{ij}^{∗}}{∑_{i=1}^{n} ∑_{j=1}^{n} D(i, j)d_{ij}^{∗}} = log n · M^{∗}(C, D). (9)

Thus, \frac{Φ^{∗}(C,D)}{log n} ≲ M^{∗}(C, D) ⩽ Φ^{∗}(C, D), i.e., the polynomial time algorithm of computing M^{∗}(C, D) is guaranteed to produce a number which is within a factor ≲ log n of Φ^{∗}(C, D).

Remark 4.2. In the above argument we only discussed the algorithmic task of fast estimation of the number Φ^{∗}(C, D), rather than the problem of producing in polynomial time a subset ∅ ≠ S ⊊ {1, …, n} for which Φ^{∗}(S) is close up to a certain multiplicative guarantee to the optimum value Φ^{∗}(C, D). All the algorithms discussed in this paper produce such a set S, rather than just approximating the number Φ^{∗}(C, D). In order to modify the argument above to this setting, one needs to go into the proof of Bourgain’s embedding theorem, which as currently stated as just an existential result for f_{1}, …, f_{n} as in (8). This issue is addressed in [56], which provides an algorithmic version of Bourgain’s theorem. Ensuing algorithms in this paper can be similarly modified to produce a good cut S, but we will ignore this issue from now on, and continue to focus solely on algorithms for approximate computation of Φ^{∗}(C, D).

4.3. The semidefinite program. We have already stated in Section 2 that the logarithmic loss in the application (8) of Bourgain’s theorem cannot be improved. Thus, in order to obtain a polynomial time algorithm with approximation guarantee better than ≲ log n, we need to impose additional geometric restrictions on the metric d_{ij}^{∗}; conditions that will hopefully yield a class of metric spaces for which one can prove an L_{1} distortion bound that is asymptotically smaller than the ≲ log n of Bourgain’s embedding theorem. This is indeed possible, based on a quadratic variant of the discussion in Section 4.2; an approach due to Goemans and Linial [37, 55, 54].

The idea of Goemans and Linial is based on Corollary 3.1, i.e., on the fact that the metric space L_{1} is of negative type. We define M^{∗∗}(C, D) to be the minimum of ∑_{i=1}^{n} ∑_{j=1}^{n} C(i, j)d_{ij}, subject to the constraint that ∑_{i=1}^{n} ∑_{j=1}^{n} D(i, j)d_{ij} = 1 and d_{ij} is a semimetric of negative type on {1, …, n}. The latter condition can be equivalently restated as the requirement that, in addition to d_{ij} being a semimetric on {1, …, n}, there exist vectors v_{1}, …, v_{n} ∈ L_{2} such that d_{ij} = ∥v_{i} − v_{j}∥_{2}^{2} for all i, j ∈ {1, …, n}. Equivalently, there exists a symmetric positive semidefinite n × n matrix (a_{ij}) (the Gram matrix of v_{1}, …, v_{n}), such that d_{ij} = a_{ii} + a_{jj} − 2a_{ij} for all i, j ∈ {1, …, n}.

Thus, M^{∗∗}(C, D) is the minimum of ∑_{i=1}^{n} ∑_{j=1}^{n} C(i, j)(a_{ii} + a_{jj} − 2a_{ij}), a linear function in the variables (a_{ij}), subject to the constraint that (a_{ij}) is a symmetric positive semidefinite matrix, in conjunction with the linear constraints ∑_{i=1}^{n} ∑_{j=1}^{n} D(i, j)(a_{ii} + a_{jj} − 2a_{ij}) = 1 and for all i, j, k ∈ {1, …, n}, the triangle inequality constraint a_{ii} + a_{jj} − 2a_{ij} ⩽ (a_{ii} + a_{kk} − 2a_{ik}) + (a_{kk} + a_{jj} − 2a_{kj}). Such an optimization problem is called a semidefinite program, and by the methods described in [40], M^{∗∗}(C, D) can be computed with arbitrarily good precision in polynomial time.

Corollary 3.1 and Lemma 4.1 imply that M^{∗}(C, D) ⩽ M^{∗∗}(C, D) ⩽ Φ^{∗}(C, D). The following breakthrough result of Arora, Rao and Vazirani [6] shows that for Sparsest Cut with uniform demands the Goemans-Linial approach does indeed yield an improved approximation algorithm:

Theorem 4.3 ([6]). In the case of uniform demands, i.e., if C(i, j) ∈ {0, 1} and D(i, j) = 1 for all i, j ∈ {1, …, n}, we have

\frac{Φ^{∗}(C, D)}{\sqrt{log n}} ≲ M^{∗∗}(C, D) ⩽ Φ^{∗}(C, D).  (10)

In the case of general demands we have almost the same result, up to lower order factors:

Theorem 4.4 ([5]). For all symmetric C, D : {1, …, n} × {1, …, n} → [0, ∞) we have

\frac{Φ^{∗}(C, D)}{(log n)^{\frac{1}{2} +o(1)}} ≲ M^{∗∗}(C, D) ⩽ Φ^{∗}(C, D).  (11)

The o(1) term in (11) is ≲ \frac{log log log n}{log log n}. We conjecture that it could be removed altogether, though at present it seems to be an inherent artifact of complications in the proof in [5].

Before explaining some of the ideas behind the proofs of Theorem 4.3 and Theorem 4.4 (the full details are quite lengthy and are beyond the scope of this survey), we prove, following [58, Prop. 15.5.2], a crucial identity (attributed in [58] to Y. Rabinovich) which reformulates these results in terms of an L_{1} embeddability problem.

Lemma 4.5. We have

sup \{\frac{Φ^{∗}(C, D)}{M^{∗∗}(C, D)} : C, D : \{1, …, n\} × \{1, …, n\} → (0, ∞)\}

= sup {c_{1}({1, …, n}, d) : d is a metric of negative type}. (12)

Proof. The proof of the fact that the left hand side of (12) is at most the right hand side of (12) is identical to the way (9) was deduced from (8).

In the reverse direction, let d^{∗} be a metric of negative type on {1, …, n} for which c_{1}({1, …, n}, d^{∗}) =^{def} c is maximal among all such metrics. Let 𝒞 ⊆ ℝ^{n^{2}} be the cone in the space of n × n symmetric matrices from the last paragraph of Section 3, i.e., 𝒞 consists of all matrices of the form (∥f_{i} − f_{j}∥_{1}) for some f_{1}, …, f_{n} ∈ L_{1}.

Fix ε ∈ (0, c − 1) and let 𝒦_{ε} ⊆ ℝ^{n^{2}} be the set of all symmetric matrices (a_{ij}) for which there exists s > 0 such that sd^{∗}(i, j) ⩽ a_{ij} ⩽ (c − ε)sd^{∗}(i, j) for all i, j ∈ {1, …, n}. By the definition of c, the convex sets 𝒞 and 𝒦_{ε} are disjoint, since otherwise d^{∗} would admit an embedding into L_{1} with distortion c − ε. It follows that there exists a symmetric matrix (h_{ij}^{ε}) ∈ ℝ^{n^{2}} \ {0} and α ∈ ℝ, such that ∑_{i=1}^{n} ∑_{j=1}^{n} h_{ij}^{ε}a_{ij} ⩽ α for all (a_{ij}) ∈ 𝒦_{ε}, and ∑_{i=1}^{n} ∑_{j=1}^{n} h_{ij}^{ε}b_{ij} ⩾ α for all (b_{ij}) ∈ 𝒞. Since both 𝒞 and 𝒦_{ε} are closed under multiplication by positive scalars, necessarily α = 0.

Define C^{ε}(i, j) =^{def} h_{ij}^{ε}1_{{h_{ij}^{ε}⩾0}} and D^{ε}(i, j) =^{def} |h_{ij}^{ε}|1_{{h_{ij}^{ε}⩽0}}. By definition of

M^{∗∗}(C^{ε}, D^{ε}),

∑_{i=1}^{n} ∑_{j=1}^{n} C^{ε}(i, j)d_{ij}^{∗} ⩾ M^{∗∗}(C^{ε}, D^{ε}) · ∑_{i=1}^{n} ∑_{j=1}^{n} D^{ε}(i, j)d_{ij}^{∗}.  (13)

By considering a_{ij} =^{def} ((c − ε)1_{{h_{ij}^{ε}⩾0}} + 1_{{h_{ij}^{ε}<0}}) d^{∗}(i, j) ∈ 𝒦_{ε}, the inequality ∑_{i=1}^{n} ∑_{j=1}^{n} h_{ij}^{ε}a_{ij} ⩽ 0 becomes:

∑_{i=1}^{n} ∑_{j=1}^{n} D^{ε}(i, j)d_{ij}^{∗} ⩾ (c − ε) ∑_{i=1}^{n} ∑_{j=1}^{n} C^{ε}(i, j)d_{ij}^{∗}.  (14)

A combination of (13) and (14) implies that (c − ε)M^{∗∗}(C^{ε}, D^{ε}) ⩽ 1. At the same time, for all f_{1}, …, f_{n} ∈ L_{1}, the inequality ∑_{i=1}^{n} ∑_{j=1}^{n} h_{ij}^{ε}∥f_{i} − f_{j}∥_{1} ⩾ 0 is the same as ∑_{i=1}^{n} ∑_{j=1}^{n} C^{ε}(i, j)∥f_{i} − f_{j}∥_{1} ⩾ ∑_{i=1}^{n} ∑_{j=1}^{n} D^{ε}(i, j)∥f_{i} − f_{j}∥_{1}, which by Lemma 6 means that Φ^{∗}(C^{ε}, D^{ε}) ⩾ 1. Thus Φ^{∗}(C^{ε}, D^{ε})/M^{∗∗}(C^{ε}, D^{ε}) ⩾ c − ε, and since this holds for all ε ∈ (0, c − 1), the proof of Lemma 4.5 is complete.

In the case of Sparsest Cut with uniform demands, we have the following result which is analogous to Lemma 4.5, where the L_{1} bi-Lipschitz distortion is replaced by the smallest possible factor by which 1-Lipschitz functions into L_{1} can distort the average distance. The proof is a slight variant of the proof of Lemma 4.5; the simple details are left to the reader. This connection between Sparsest Cut with uniform demands and embeddings that preserve the average distance is due to Rabinovich [63].

Lemma 4.6. The supremum of Φ^{∗}(C, D)/M^{∗∗}(C, D) over all instances of uniform demands, i.e., when C(i, j) ∈ {0, 1} and D(i, j) = 1 for all i, j ∈ {1, …, n}, equals the infimum over A > 0 such that for all metrics d on {1, …, n} of negative type, there exist f_{1}, …, f_{n} ∈ L_{1} satisfying ∥f_{i} − f_{j}∥_{1} ⩽ d(i, j) for all i, j ∈ {1, …, n} and A ∑_{i=1}^{n} ∑_{j=1}^{n} ∥f_{i} − f_{j}∥_{1} ⩾ ∑_{i=1}^{n} ∑_{j=1}^{n} d(i, j).

4.3.1. L_{2} embeddings of negative type metrics. The proof of Theorem 4.3 in [6] is based on a clever geometric partitioning procedure for metrics of negative type. Building heavily on ideas of [6], in conjunction with some substantial additional combinatorial arguments, an alternative approach to Theorem 4.3 was obtained in [59], based on a purely graph theoretical statement which is of independent interest. We shall now sketch this approach, since it is modular and general, and as such it is useful for additional geometric corollaries. We refer to [59] for more information on these additional applications, as well as to [6] for the original proof of Theorem 4.3.

Let G = (V, E) be an n-vertex graph. The vertex expansion of G, denoted h(G), is the largest h ⩾ 0 such that every S ⊆ V with |S| ⩽ n/2 has at least h|S| neighbors in V \ S. The edge expansion of G, denoted α(G), is the largest α ⩾ 0 such that for every S ⊆ V with |S| ⩽ n/2, the number of edges joining S and V \S is at least α|S| · \frac{|E|}{n}. The main combinatorial statement of [59] relates these two notions of expansion of graphs:

Theorem 4.7 (Edge Replacement Theorem [59]). For every graph G = (V, E) with h(G) ⩾ \frac{1}{2} there is a set of edges E′ on V with α(V, E′) ≳ 1, and such that for every uv ∈ E′ we have d_{G}(u, v) ≲ \sqrt{log |V |}. Here d_{G} is the shortest path metric on G (with respect to the original edge set E), and all implicit constants are universal.

It is shown in [59] that the ≲ \sqrt{log |V |} bound on the length of the new edges in Theorem 4.7 is asymptotically tight. The proof of Theorem 4.7 is involved, and cannot be described here: it has two components, a combinatorial construction, as well a purely Hilbertian geometric argument based on, and simpler than, the original algorithm of [6]. We shall now explain how Theorem 4.7 implies Theorem 4.3 (this is somewhat different from the deduction in [59], which deals with a different semidefinite program for Sparsest Cut with uniform demands).

Proof of Theorem 4.3 assuming Theorem 4.7. An application of (the easy direction of) Lemma 4.6 shows that in order to prove Theorem 4.3 it suffices to show that if (ℳ , d) is an n-point metric space of negative type, with \frac{1}{n^{2}} ∑_{x,y∈ℳ} d(x, y) = 1, then there exists a mapping F : ℳ → ℝ which is 1-Lipschitz and such that \frac{1}{n^{2}} ∑_{x,y∈ℳ} |F (x) − F (y)| ≳ 1/\sqrt{log n}. In what follows we use the standard notation for closed balls: for x ∈ ℳ and t ⩾ 0, set B(x, t) = {y ∈ ℳ : d(x, y) ⩽ t}.

Choose x_{0} ∈ ℳ with \frac{1}{n} ∑_{y∈ℳ} d(x_{0}, y) = r =^{def} min_{x∈ℳ} \frac{1}{n} ∑_{y∈ℳ} d(x, y). Then

r ⩽ \frac{1}{n^{2}} ∑_{x,y∈ℳ} d(x, y) = 1, implying 1 ⩾ \frac{1}{n} ∑_{y∈ℳ} d(x_{0}, y) > \frac{2}{n}|ℳ \ B(x_{0}, 2)|, or |B(x_{0}, 2)| > n/2. Similarly |B(x_{0}, 4)| > 3n/4.

Assume first that \frac{1}{n^{2}} ∑_{x,y∈B(x_{0},4)} d(x, y) ⩽ \frac{1}{4} (this will be the easy case). Then

1 = \frac{1}{n^{2}} ∑_{x,y∈ℳ} d(x, y) ⩽ \frac{1}{4} + \frac{2}{n^{2}} ∑_{x∈ℳ} ∑_{y∈ℳ \B(x_{0},4)} (d(x, x_{0}) + d(x_{0}, y))

= \frac{1}{4} + \frac{2r}{n} |ℳ \ B(x_{0}, 4)| + \frac{2}{n} ∑_{y∈ℳ \B(x_{0},4)} d(x_{0}, y) ⩽ \frac{3}{4} + \frac{2}{n} ∑_{y∈ℳ \B(x_{0},4)} d(x_{0}, y),

or \frac{1}{n} ∑_{y∈ℳ \B(x_{0},4)} d(x_{0}, y) ⩾ \frac{1}{8}. Define a 1-Lipschitz mapping F : ℳ → ℝ by F (x) = d(x, B(x_{0}, 2)) = min_{y∈B(x_{0},2)} d(x, y). The triangle inequality implies that for every y ∈ ℳ \ B(x_{0}, 4) we have F (y) ⩾ \frac{1}{2}d(y, x_{0}). Thus

\frac{1}{n^{2}} ∑_{x,y∈ℳ} |F (x) − F (y)| ⩾ \frac{|B(x_{0}, 2)|}{n^{2}} ∑_{y∈ℳ \B(x_{0},4)} d(y, B(x_{0}, 2))

> \frac{1}{2n} ∑_{y∈ℳ \B(x_{0},4)} \frac{1}{2}d(y, x_{0}) ≳ 1 = \frac{1}{n^{2}} ∑_{x,y∈ℳ} d(x, y).

This completes the easy case, where there is even no loss of 1/\sqrt{log n} (and we did not use yet the assumption that d is a metric of negative type).

We may therefore assume from now on that \frac{1}{n^{2}} ∑_{x,y∈B(x_{0},4)} d(x, y) ⩾ \frac{1}{4}. The fact that d is of negative type means that there are vectors {v_{x}}_{x∈ℳ} ⊆ L_{2} such that d(x, y) = ∥v_{x} − v_{y}∥_{2}^{2} for all x, y ∈ ℳ.

We will show that for a small enough universal constant ε > 0, there are two sets S_{1}, S_{2} ⊆ B(x_{0}, 4) such that |S_{1}|, |S_{2}| ⩾ εn and d(S_{1}, S_{2}) ⩾ ε^{2}/\sqrt{log n}. Once this is achieved, the mapping F : ℳ → ℝ given by F (x) = d(x, S_{1}) will satisfy \frac{1}{n^{2}} ∑_{x,y∈ℳ} |F (x) − F (y)| ⩾ \frac{2}{n^{2}} |S_{1}| · |S_{2}|\frac{ε^{2}}{\sqrt{log n}} ⩾ \frac{2ε^{4}}{\sqrt{log n}}, as desired.

Assume for contradiction that no such S_{1}, S_{2} exist. Define a set of edges E_{0}

on B(x_{0}, 4) by E_{0} =^{def} \{\{x, y\} ⊆ B(x_{0}, 4) : x ≠ y ∧ d(x, y) < ε^{2}/\sqrt{log n}\}.

Our contrapositive assumption says that any two subsets S_{1}, S_{2} ⊆ B(x_{0}, 4) with |S_{1}|, |S_{2}| ⩾ εn ⩾ ε|B(x_{0}, 4)| are joined by an edge from E_{0}. By a (simple) general graph theoretical lemma (see [59, Lem 2.3]), this implies that, provided ε ⩽ 1/10, there exists a subset V ⊆ B(x_{0}, 4) with |V | ⩾ (1 − ε)|B(x_{0}, 4)| ≳ n, such that the graph induced by E_{0} on V, i.e., G = (V, E = E_{0} ∩ \binom{V}{2}), has h(G) ⩾ \frac{1}{2}.

We are now in position to apply the Edge Replacement Theorem, i.e., Theorem 4.7. We obtain a new set of edges E′ on V such that α(V, E′) ≳ 1 and for every xy ∈ E′ we have d_{G}(x, y) ≲ \sqrt{log n}. The latter condition means that there exists a path \{x = x_{0}, x_{1}, …, x_{m} = y\} ⊆ V such that m ≲ \sqrt{log n} and x_{i}x_{i−1} ∈ E for every i ∈ {1, …, m}. By the definition of E, this implies that

xy ∈ E′ ⟹ d(x, y) ⩽ ∑_{i=1}^{n} d(x_{i}, x_{i−1}) ⩽ m\frac{ε^{2}}{\sqrt{log n}} ≲ ε^{2}.  (15)

It is a standard fact (the equivalence between edge expansion and a Cheeger inequality) that for every f : V → L_{1} we have

\frac{1}{|E′|} ∑_{xy∈E′} ∥f(x) − f(y)∥_{1} ⩾ \frac{α(V, E′)}{2|V |^{2}} ∑_{x,y∈V} ∥f(x) − f(y)∥_{1}.  (16)

For a proof of (16) see [59, Fact 2.1]: this is a simple consequence of the cut cone representation, i.e., Corollary 3.2, since the identity (3) shows that it suffices to prove (16) when f(x) = 1_{S}(x) for some S ⊆ V, in which case the desired inequality follows immediately from the definition of the edge expansion α(V, E′).

Since L_{2} is isometric to a subset of L_{1} (see, e.g., [71]), it follows from (16) and the fact that α(V, E′) ≳ 1 that

ε ≳^{(15)} \frac{1}{|E′|} ∑_{xy∈E′} \sqrt{d(x, y)} = \frac{1}{|E′|} ∑_{xy∈E′} ∥v_{x} − v_{y}∥_{2}

≳ \frac{1}{|V |^{2}} ∑_{x,y∈V} ∥v_{x} − v_{y}∥_{2} ≳ \frac{1}{n^{2}} ∑_{x,y∈V} \sqrt{d(x, y)}. (17)

Now comes the point where we use the assumption \frac{1}{n^{2}} ∑_{x,y∈B(x_{0},4)} d(x, y) ⩾ \frac{1}{4}. Since for any x, y ∈ B(x_{0}, 4) we have d(x, y) ⩽ 8, it follows that the number of pairs (x, y) ∈ B(x_{0}, 4) × B(x_{0}, 4) with d(x, y) ⩾ 1/8 is at least n^{2}/64. Since |V | ⩾ (1 − ε)|B(x_{0}, 4)|, the number of such pairs which are also in V × V is at least \frac{n^{2}}{64} − 3εn^{2} ≳ n^{2}, provided ε is small enough. Thus \frac{1}{n^{2}} ∑_{x,y∈V} \sqrt{d(x, y)} ≳ 1, and (17) becomes a contradiction for small enough ε.

Remark 4.8. The above proof of Theorem 4.7 used very little of the fact that d is a metric of negative type. In fact, all that was required was that d admits a quasisymmetric embedding into L_{2}; see [59].

It remains to say a few words about the proof of Theorem 4.4. Unfortunately, the present proof of this theorem is long and involved, and it relies on a variety of results from metric embedding theory. It would be of interest to obtain a simpler proof. Lemma 4.5 implies that Theorem 4.4 is a consequence of the following embedding result:

Theorem 4.9 ([5]). Every n-point metric space of negative type embeds into Hilbert space with distortion ≲ (log n)^{\frac{1}{2} +o(1)}.

Theorem 4.9 improves over the previously known [23] bound of ≲ (log n)^{3/4} on the Euclidean distortion of n-point metric spaces of negative type. As we shall explain below, Theorem 4.9 is tight up to the o(1) term.

The proof of Theorem 4.9 uses the following notion from [5]:

Definition 4.10 (Random zero-sets [5]). Fix Δ, ζ > 0, and p ∈ (0, 1). A metric space (ℳ , d) is said to admit a random zero set at scale Δ, which is ζ-spreading with probability p, if there is a probability distribution μ over subsets Z ⊆ ℳ such that μ ({Z : y ∈ Z ∧ d(x, Z) ⩾ Δ/ζ}) ⩾ p for every x, y ∈ ℳ with d(x, y) ⩾ Δ. We denote by ζ(ℳ; p) the least ζ > 0 such that for every Δ > 0, ℳ admits a random zero set at scale Δ which is ζ-spreading with probability p.

The connection to metrics of negative type is due to the following theorem, which can be viewed as the main structural consequence of [6]. Its proof uses [6] in conjunction with two additional ingredients: an analysis of the algorithm of [6] due to [50], and a clever iterative application of the algorithm of [6], due to [23], while carefully reweighting points at each step.

Theorem 4.11 (Random zero sets for negative type metrics). There exists a universal constant p > 0 such that any n-point metric space (ℳ , d) of negative type satisfies ζ(ℳ; p) ≲ \sqrt{log n}.

Random zero sets are related to embeddings as follows. Fix Δ > 0. Let (ℳ , d) be a finite metric space, and fix S ⊆ ℳ. 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) ⩾ Δ we have μ ({Z ⊆ S : y ∈ Z ∧ d(x, Z) ⩾ Δ/ζ(S; p)}) ⩾ p. Define φ_{S,Δ} : ℳ → L_{2}(μ) by φ_{S,Δ}(x) = d(x, Z). Then φ_{S,Δ} is 1-Lipschitz, and for every x, y ∈ S with d(x, y) ⩾ Δ,

∥φ_{S,Δ}(x) − φ_{S,Δ}(y)∥_{L_{2}(μ)} = (∫_{2^{S}} [d(x, Z) − d(y, Z)]^{2} dμ(Z))^{1/2} ⩾ \frac{Δ\sqrt{p}}{ζ(S; p)}. (18)

The remaining task is to “glue” the mappings {φ_{S,Δ} : Δ > 0, S ⊆ ℳ } to form an embedding of ℳ into Hilbert space with the distortion claimed in Theorem 4.9. A key ingredient of the proof of Theorem 4.9 is the embedding method called “Measured Descent”, that was developed in [48]. The results of [48] were stated as embedding theorems rather than a gluing procedure; the realization that a part of the arguments of [48] can be formulated explicitly as a general “gluing lemma” is due to [50]. In [5] it was necessary to enhance the Measured Descent technique in order to prove the following key theorem, which together with (18) and Theorem 4.11 implies Theorem 4.9. See also [4] for a different enhancement of Measured Descent, which also implies Theorem 4.9. The proof of Theorem 4.12 is quite intricate; we refer to [5] for the details.

Theorem 4.12. Let (ℳ , d) be an n-point metric space. Suppose that there is ε ∈ [1/2, 1] such that for every Δ > 0, and every subset S ⊆ ℳ, there exists a 1-Lipschitz map φ_{S,Δ} : ℳ → L_{2} with ||φ_{S,Δ}(x)−φ_{S,Δ}(y)||_{2} ≳ Δ/(log |S|)^{ε} whenever x, y ∈ S and d(x, y) ⩾ Δ. Then c_{2}(ℳ) ≲ (log n)^{ε} log log n.

The following corollary is an obvious consequence of Theorem 4.9, due to the fact that L_{1} is a metric space of negative type.

Corollary 4.13. Every X ⊆ L_{1} embeds into L_{2} with distortion ≲ (log |X|)^{\frac{1}{2} +o(1)}.

We stated Corollary 4.13 since it is of special importance: in 1969, Enflo [34] proved that the Hamming cube, i.e., {0, 1}^{k} equipped with the metric induced from ℓ_{1}^{k}, has Euclidean distortion \sqrt{k}. Corollary 4.13 says that up to lower order factors, the Hamming cube is among the most non-Euclidean subsets of L_{1}. There are very few known results of this type, i.e., (almost) sharp evaluations of the largest Euclidean distortion of an n-point subset of a natural metric space. A notable such result is Matoušek’s theorem [57] that any n-point subset of the infinite binary tree has Euclidean distortion ≲ \sqrt{log log n}, and consequently, due to [20], the same holds true for n-point subsets of, say, the hyperbolic plane. This is tight due to Bourgain’s matching lower bound [16] for the Euclidean distortion of finite depth complete binary trees.

4.3.2. The Goemans-Linial conjecture. Theorem 4.4 is the best known approximation algorithm for the Sparsest Cut Problem (and Theorem 4.3 is the best known algorithm in the case of uniform demands). But, a comparison of Lemma 4.5 and Theorem 4.9 reveals a possible avenue for further improvement: Theorem 4.9 produces an embedding of negative type metrics into L_{2} (for which the bound of Theorem 4.9 is sharp up to lower order factors), while for Lemma 4.5 all we need is an embedding into the larger space L_{1}. It was conjectured by Goemans and Linial (see [37, 55, 54] and [58, pg. 379–380]) that any finite metric space of negative type embeds into L_{1} with distortion ≲ 1. If true, this would yield, via the Goemans-Linial semidefinite relaxation, a constant factor approximation algorithm for Sparsest Cut.

As we shall see below, it turns out that the Goemans-Linial conjecture is false, and in fact there exist [30] arbitrarily large n-point metric spaces ℳ_{n} of negative type for which c_{1}(ℳ_{n}) ⩾ (log n)^{c}, where c is a universal constant. Due to the duality argument in Lemma 4.5, this means that the algorithm of Section 4.3 is doomed to make an error of at least (log n)^{c}, i.e., there exist capacity and demand functions C_{n}, D_{n} : {1, …, n} × {1, …, n} → [0, ∞) for which we have M^{∗∗}(C_{n}, D_{n}) ≲ Φ^{∗}(C_{n}, D_{n})/(log n)^{c}. Such a statement is referred to in the literature as the fact that the integrality gap of the Goemans-Linial semidefinite relaxation of Sparsest Cut is at least (log n)^{c}.

4.3.3. Unique Games hardness and the Khot-Vishnoi integrality gap. Khot’s Unique Games Conjecture [44] is that for every ε > 0 there exists a prime p = p(ε) such that there is no polynomial time algorithm that, given n ∈ ℕ and a system of m-linear equations in n-variables of the form x_{i} − x_{j} = c_{ij} mod p for some c_{ij} ∈ ℕ, determines whether there exists an assignment of an integer value to each variable x_{i} such that at least (1 − ε)m of the equations are satisfied, or whether no assignment of such values can satisfy more than εm of the equations (if neither of these possibilities occur, then an arbitrary output is allowed). This formulation of the conjecture is due to [46], where it is shown that it is equivalent to the original formulation in [44]. The Unique Games Conjecture is by now a common assumption that has numerous applications in computational complexity; see the survey [45] (in this collection) for more information.

In [47, 24] it was shown that the existence of a polynomial time constant factor approximation algorithm for Sparsest Cut would refute the Unique Games Conjecture, i.e., one can use a polynomial time constant factor approximation algorithm for Sparsest Cut to solve in polynomial time the above algorithmic task for linear equations.

For a period of time in 2004, this computational hardness result led to a strange situation: either the complexity theoretic Unique Games Conjecture is true, or the purely geometric Goemans-Linial conjecture is true, but not both. In a remarkable tour de force, Khot and Vishnoi [47] delved into the proof of their hardness result and managed to construct from it a concrete family of arbitrarily large n-point metric spaces ℳ_{n} of negative type for which c_{1}(ℳ_{n}) ≳ (log log n)^{c}, where c is a universal constant, thus refuting the Goemans-Linial conjecture. Subsequently, these Khot-Vishnoi metric spaces ℳ_{n} were analyzed in [49], resulting in the lower bound c_{1}(ℳ_{n}) ≳ log log n. Further work in [32] yielded a ≳ log log n integrality gap for Sparsest Cut with uniform demands, i.e., “average distortion” L_{1} embeddings (in the sense of Lemma 4.6) of negative type metrics were ruled out as well.

4.3.4. The Bretagnolle, Dacunha-Castelle, Krivine theorem and invariant metrics on Abelian groups. A combination of Schoenberg’s classical characterization [65] of metric spaces that are isometric to subsets of Hilbert space, and a theorem of Bretagnolle, Dacunha-Castelle and Krivine [18] (see also [70]), implies that if p ∈ [1, 2] and (X, ∥ · ∥_{X}) is a separable Banach space such that the metric space (X, ∥x − y∥_{X}^{p/2}) is isometric to a subset of Hilbert space, then X is (linearly) isometric to a subspace of L_{p}. Specializing to p = 1 we see that the Goemans-Linial conjecture is true for Banach spaces. With this motivation for the Goemans-Linial conjecture in mind, one notices that the Goemans-Linial conjecture is part of a natural one parameter family of conjectures which attempt to extend the theorem of Bretagnolle, Dacunha-Castelle and Krivine to general metric spaces rather than Banach spaces: is it true that for p ∈ [1, 2) any metric space (ℳ , d) for which (ℳ , d^{p/2}) is isometric to a subset of L_{2} admits a bi-Lipschitz embedding into L_{p}? This generalized Goemans-Linial conjecture turns out to be false for all p ∈ [1, 2); our example based on the Heisenberg group furnishes counter-examples for all p.

It is also known that certain invariant metrics on Abelian groups satisfy the Goemans-Linial conjecture:

Theorem 4.14 ([10]). Let G be a finite Abelian group, equipped with an invariant metric ρ. Suppose that 2 ⩽ m ∈ ℕ satisfies mx = 0 for all x ∈ G. Denote D = c_{2} (G, \sqrt{ρ}). Then c_{1}(G, ρ) ≲ D^{4} log m.

It is an interesting open question whether the dependence on the exponent m of the group G in Theorem 4.14 is necessary. Can one construct a counter-example to the Goemans-Linial conjecture which is an invariant metric on the cyclic group C_{n} of order n? Or, is there for every D ⩾ 1 a constant K(D) such that for every invariant metric ρ on C_{n} for which c_{2} (G, \sqrt{ρ}) ⩽ D we have c_{1}(G, ρ) ⩽ K(D)?

One can view the above discussion as motivation for why one might consider the Heisenberg group as a potential counter-example to the Goemans-Linial conjecture. Assuming that we are interested in invariant metrics on groups, we wish to depart from the setting of Abelian groups or Banach spaces, and if at the same time we would like our example to have some useful analytic properties (such as invariance under rescaling and the availability of a group norm), the Heisenberg group suggests itself as a natural candidate. This plan is carried out in Section 5.

5. Embeddings of the Heisenberg group

The purpose of this section is to discuss Theorem 1.1 and Theorem 1.2 from the introduction. Before doing so, we have an important item of unfinished business: relating the Heisenberg group to the Sparsest Cut Problem. We will do this in Section 5.1, following [52].

In preparation, we need to recall the Carnot-Carathéodory geometry of the continuous Heisenberg group ℍ, i.e., ℝ^{3} equipped with the non-commutative product (a, b, c) · (a′, b′, c′) = (a + a′, b + b′, c + c′ + ab′ − ba′). Due to lack of space, this will have to be a crash course, and we refer to the relevant introductory sections of [29] for a more thorough discussion.

The identity element of ℍ is e = (0, 0, 0), and the inverse element of (a, b, c) ∈ ℍ is (−a, −b, −c). The center of ℍ is the z-axis {0} × {0} × ℝ. For g ∈ ℍ the horizontal plane at g is defined as ℍ_{g} = g(ℝ × ℝ × {0}). An affine line L ⊆ ℍ is called a horizontal line if for some g ∈ ℍ it passes through g and is contained in the affine plane ℍ_{g}. The standard scalar product ⟨·, ·⟩ on ℍ_{e} naturally induces a scalar product ⟨·, ·⟩_{g} on ℍ_{g} by ⟨gx, gy⟩_{g} = ⟨x, y⟩. Consequently, we can define the Carnot-Carathéodory metric d^{ℍ} on ℍ by letting d^{ℍ}(g, h) be the infimum of lengths of smooth curves γ : [0, 1] → ℍ such that γ(0) = g, γ(1) = h and for all t ∈ [0, 1] we have γ′(t) ∈ H_{γ(t)} (and, the length of γ′(t) is computed with respect to the scalar product ⟨·, ·⟩_{γ(t)}). The ball-box principle (see [39]) implies that d^{ℍ}((a, b, c), (a′, b′, c′)) is bounded above and below by a constant multiple of |a − a′| + |b − b′| + \sqrt{|c − c′ + ab′ − ba′|}. Moreover, since the integer grid ℍ(ℤ) is a discrete cocompact subgroup of ℍ, the word metric d_{W} on ℍ(ℤ) is bi-Lipschitz equivalent to the restriction of d^{ℍ} to ℍ(ℤ) (see, e.g, [19]). For θ > 0 define the dilation operator δ_{θ} : ℍ → ℍ by δ_{θ}(a, b, c) = (θa, θb, θ^{2}c). Then for all g, h ∈ ℍ we have d^{ℍ}(δ_{θ}(g), δ_{θ}(h)) = θd^{ℍ}(g, h). The Lebesgue measure ℒ_{3} on ℝ^{3} is a Haar measure of ℍ, and the volume of a d^{ℍ}-ball of radius r is proportional to r^{4}.

5.1. Heisenberg metrics with isometric L_{p} snowflakes. For ev-

ery (a, b, c) ∈ ℍ and p ∈ [1, 2), define

M_{p}(a, b, c) = \sqrt[4]{(a^{2} + b^{2})^{2} + 4c^{2}} · (cos (\frac{p}{2} arccos (\frac{a^{2} + b^{2}}{\sqrt{(a^{2} + b^{2})^{2} + 4c^{2}}} )))^{1/p} .

It was shown in [52] that M_{p} is a group norm on ℍ, i.e., for all g, h ∈ ℍ and θ ⩾ 0 we have M_{p}(gh) ⩽ M_{p}(g) + M_{p}(h), M_{p}(g^{−1}) = M_{p}(g) and M_{p}(δ_{θ}(g)) = θM_{p}(g). Thus d_{p}(g, h) =^{def} M_{p}(g^{−1}h) is a left-invariant metric on ℍ. The metric d_{p} is bi-Lipschitz equivalent to d^{ℍ} with distortion of order 1/\sqrt{2 − p} (see [52]). Moreover, it was shown in [52] that (ℍ, d_{p}^{p/2}) admits an isometric embedding into L_{2}. Thus, in particular, the metric space (ℍ, d_{1}), which bi-Lipschitz equivalent to (ℍ, d^{ℍ}), is of negative type.

The fact that (ℍ, d^{ℍ}) does not admit a bi-Lipschitz embedding into L_{p} for any 1 ⩽ p < ∞ will show that the generalized Goemans-Linial conjecture (see Section 4.3.4) is false. In particular, (ℍ, d_{1}), and hence by a standard rescaling argument also (ℍ(ℤ), d_{1}), is a counter-example to the Goemans-Linial conjecture. Note that it is crucial here that we are dealing with the function space L_{p} rather than the sequence space ℓ_{p}, in order to use a compactness argument to deduce from this statement that there exist arbitrarily large n-point metric spaces (ℳ_{n}, d) such that (ℳ_{n}, d^{p/2}) is isometric to a subset of L_{2}, yet lim_{n→∞} c_{p}(ℳ_{n}) = ∞. The fact that this statement follows from non-embeddability into L_{p} is a consequence of a well known ultrapower argument (see [42]), yet for ℓ_{p} this statement is false (e.g., ℓ_{2} does not admit a bi-Lipschitz embedding into ℓ_{p}, but all finite subsets of ℓ_{2} embed isometrically into ℓ_{p}). Unfortunately, this issue creates substantial difficulties in the case of primary interest p = 1. In the reflexive range p > 1, or for a separable dual space such as ℓ_{1} (= c_{0}^{∗}), the non-embeddability of ℍ follows from a natural extension of a classical result of Pansu [61], as we explain in Section 5.2. This approach fails badly when it comes to embeddings into L_{1}: for this purpose a novel method of Cheeger and Kleiner [25] is needed, as described in Section 5.3.

5.2. Pansu differentiability. Let X be a Banach space and f : ℍ → X. Following [61], f is said to have a Pansu derivative at x ∈ ℍ if for every y ∈ ℍ the limit D_{f}^{x}(y) =^{def} lim_{θ→0} (f(xδ_{θ}(y)) − f(x))/θ exists, and D_{f}^{x} : ℍ → X is a group homomorphism, i.e., for all y_{1}, y_{2} ∈ ℍ we have D_{f}^{x}(y_{1}y_{2}^{−1}) = D_{f}^{x}(y_{1}) − D_{f}^{y}(y_{2}). Pansu proved [61] that every f : ℍ → ℝ^{n} which is Lipschitz in the metric d^{ℍ} is Pansu differentiable almost everywhere. It was observed in [52, 27] that this result holds true if the target space ℝ^{n} is replaced by any Banach space with the Radon-Nikodým property, in particular X can be any reflexive Banach space such as L_{p} for p ∈ (1, ∞), or a separable dual Banach space such as ℓ_{1}. As noted by Semmes [66], this implies that ℍ does not admit a bi-Lipschitz embedding into any Banach space X with the Radon-Nikodým property: a bi-Lipschitz condition for f implies that at a point x ∈ ℍ of Pansu differentiability, D_{f}^{x} is also bi-Lipschitz, and in particular a group isomorphism. But that’s impossible since ℍ is non-commutative, unlike the additive group of X.

5.3. Cheeger-Kleiner differentiability. Differentiability theorems fail

badly when the target space is L_{1}, even for functions defined on ℝ; consider Aronszajn’s example [3] of the “moving indicator function” t ↦ 1_{[0,t]} ∈ L_{1}. For L_{1}- valued Lipschitz functions on ℍ, Cheeger and Kleiner [25, 28] developed an alternative differentiation theory, which is sufficiently strong to show that ℍ does not admit a bi-Lipschitz embedding into L_{1}. Roughly speaking, a differentiation theorem states that in the infinitesimal limit, a Lipschitz mapping converges to a mapping that belongs to a certain “structured” subclass of mappings (e.g., linear mappings or group homomorphisms). The Cheeger-Kleiner theory shows that, in a sense that will be made precise below, L_{1}-valued Lipschitz functions on ℍ are in the infinitesimal limit similar to Aronszajn’s moving indicator.

For an open subset U ⊆ ℍ let Cut(U) denote the space of (equivalences classes up to measure zero) of measurable subsets of U. Let f : U → L_{1} be a Lipschitz function. An infinitary variant of the cut-cone decomposition of Corollary 3.2 (see [25]) asserts that there exists a measure Σ_{f} on Cut(U), such that for all x, y ∈ U we have ∥f(x) − f(y)∥_{1} = ∫_{Cut(U)} |1_{E}(x) − 1_{E}(y)|dΣ_{f}(E). The measure Σ_{f} is called the cut measure of f. The idea of Cheeger and Kleiner is to detect the “infinitesimal regularity” of f in terms of the infinitesimal behavior of the measure Σ_{f}; more precisely, in terms of the shape of the sets E in the support of Σ_{f}, after passing to an infinitesimal limit.

Theorem 5.1 (Cheeger-Kleiner differentiability theorem [25, 28]). For almost every x ∈ U there exists a measure Σ_{f}^{x} on Cut(ℍ) such that for all y, z ∈ ℍ we have

lim_{θ→0} \frac{∥f(xδ_{θ}(y)) − f(xδ_{θ}(z))∥_{1}}{θ} = ∫_{Cut(ℍ)} |1_{E}(y) − 1_{E}(z)|dΣ_{f}^{x}(E). (19)

Moreover, the measure Σ_{f}^{x} is supported on affine half-spaces whose boundary is a vertical plane, i.e., a plane which isn’t of the form ℍ_{g} for some g ∈ ℍ (equivalently, an inverse image, with respect to the orthogonal projection from ℝ^{3} onto ℝ×ℝ×{0}, of a line in ℝ × ℝ × {0}).

Theorem 5.1 is incompatible with f being bi-Lipschitz, since the right hand side of (19) vanishes when y, z lie on the same coset of the center of ℍ, while if f is bi-Lipschitz the left hand side of (19) is at least a constant multiple of d^{ℍ}(y, z).

5.4. Compression bounds for L_{1} embeddings of the Heisen-

berg group. Theorem 1.1 and Theorem 1.2 are both a consequence of the following result from [29]:

Theorem 5.2 (Quantitative central collapse [29]). There exists a universal constant c ∈ (0, 1) such that for every p ∈ ℍ, every 1-Lipschitz f : B(p, 1) → L_{1}, and every ε ∈ (0, \frac{1}{4}), there exists r ⩾ ε such that with respect to Haar measure, for at least half of the points x ∈ B(p, 1/2), at least half of the pairs of points (x_{1}, x_{2}) ∈ B(x, r) × B(x, r) which lie on the same coset of the center with d^{ℍ}(x_{1}, x_{2}) ∈ [εr/2, 3εr/2] satisfy:

∥f(x_{1}) − f(x_{2})∥_{1} ⩽ \frac{d^{ℍ}(x_{1}, x_{2})}{(log(1/ε))^{c}} .

It isn’t difficult to see that Theorem 5.2 implies Theorem 1.1 and Theorem 1.2. For example, in the setting of Theorem 1.1 we are given a bi-Lipschitz embedding f : {1, …, n}^{3} → L_{1}, and using either the general extension theorem of [51] or a partition of unity argument, we can extend f to a Lipschitz (with respect to d^{ℍ}) mapping f̄: [1, n]^{3} → L_{1}, whose Lipschitz constant is at most a constant multiple of the Lipschitz constant of f. Theorem 5.2 (after rescaling by n) produces a pair of points y, z ∈ [1, n]^{3} of distance ≳ \sqrt{n}, whose distance is contracted under f̄ by ≳ (log n)^{c}. By rounding y, z to their nearest integer points in {1, …, n}^{3}, we conclude that f itself must have bi-Lipschitz distortion ≳ (log n)^{c}. The deduction of Theorem 1.2 from Theorem 5.2 is just as simple; see [29].

Theorem 5.2 is a quantitative version of Theorem 5.1, in the sense that it gives a definite lower bound on the macroscopic scale at which a given amount of collapse of cosets of the center, as exhibited by the differentiation result (19), occurs. As explained in [29, Rem. 2.1], one cannot hope in general to obtain rate bounds in differentiation results such as (19). Nevertheless, there are situations where “quantitative differentiation results” have been successfully proved; important precursors of Theorem 5.2 include the work of Bourgain [17], Jones [43], Matoušek [57], and Bates, Johnson, Lindenstrauss, Preiss, Schechtman [13]. Specifically, we should mention that Bourgain [17] obtained a lower bound on ε > 0 such that any embedding of an ε-net in a unit ball of an n-dimensional normed space X into a normed space Y has roughly the same distortion as the distortion required to embed all of X into Y, and Matoušek [57], in his study of embeddings of trees into uniformly convex spaces, obtained quantitative bounds on the scale at which “metric differentiation” is almost achieved, i.e., a scale at which discrete geodesics are mapped by a Lipschitz function to “almost geodesics”. These earlier results are in the spirit of Theorem 5.2, though the proof of Theorem 5.2 in [29] is substantially more involved.

We shall now say a few words on the proof of Theorem 5.2; for lack of space this will have to be a rough sketch, so we refer to [29] for more details, as well as to the somewhat different presentation in [30]. Cheeger and Kleiner obtained two different proofs of Theorem 5.1. The first proof [25] started with the important observation that the fact that f is Lipschitz forces the cut measure Σ_{f} to be supported on sets with additional regularity, namely sets of finite perimeter. Moreover, there is a definite bound on the total perimeter: ∫_{Cut(U)} PER(E, B(p, 1))dΣ_{f}(E) ≲ 1, where PER(E, B(p, 1)) denotes the perimeter of E in the ball B(p, 1) (we refer to the book [2], and the detailed explanation in [25, 29] for more information on these notions). Theorem 5.2 is then proved in [25] via an appeal to results [35, 36] on the infinitesimal structure of sets of finite perimeter in ℍ. A different proof of Theorem 5.2 was found in [28]. It is based on the notion of metric differentiation, which is used in [28] to reduce the problem to mappings f : ℍ → L_{1} for which the cut measure is supported on monotone sets, i.e., sets E ⊆ ℍ such that for every horizontal line L, up to a set of measure zero, both L ∩ E and L ∩ (ℍ \ E) are either empty or subrays of L. A non-trivial classification of monotone sets is then proved in [28]: such sets are up to measure zero half-spaces.

This second proof of Theorem 5.2 avoids completely the use of perimeter bounds. Nevertheless, the starting point of the proof of Theorem 5.2 can be viewed as a hybrid argument, which incorporates both perimeter bounds, and a new classification of almost monotone sets. The quantitative setting of Theorem 5.2 leads to issues that do not have analogues in the non-quantitative proofs (e.g., the approximate classification results of “almost” monotone sets in balls cannot be simply that such sets are close to half-spaces in the entire ball; see [29, Example 9.1]).

In order to proceed we need to quantify the extent to which a set E ⊆ B(x, r) is monotone. For a horizontal line L ⊆ ℍ define the non-convexity NC_{B(x,r)}(E, L) of (E, L) on B(x, r) as the infimum of ∫_{L∩B(x,r)} |1_{I} − 1_{E∩L∩B(x,r)}| dH_{L}^{1} over all sub-intervals I ⊆ L ∩ B(x, r). Here H_{L}^{1} is the 1-dimensional Hausdorff measure on L (induced from the metric d^{ℍ}). The non-monotonicity of (E, L) on B(x, r) is defined to be NM_{B(x,r)}(E, L) =^{def} NC_{B(x,r)}(E, L) + NC_{B(x,r)}(ℍ \ E, L). The total non-monotonicity of E on B(x, r) is defined as:

NM_{B(x,r)}(E) =^{def} \frac{1}{r^{4}} ∫_{lines(B(x,r))} NM_{B(x,r)}(E, L)dN (L),

where lines(U) denotes the set of horizontal lines in ℍ which intersect U, and N is the left invariant measure on lines(ℍ), normalized so that the measure of lines(B(e, 1)) is 1.

The following stability result for monotone sets constitutes the bulk of [29]:

Theorem 5.3. There exists a universal constant a > 0 such that if a measurable set E ⊆ B(x, r) satisfies NM_{B(x,r)}(E) ⩽ ε^{a} then there exists a half-space P such that

\frac{ℒ_{3} ((E ∩ B(x, εr))△P)}{ℒ_{3}(B(x, εr))} < ε^{1/3}.

Perimeter bounds are used in [29, 30] for two purposes. The first is finding a controlled scale r such that at most locations, apart from a certain collection of cuts, the mass of Σ_{f} is supported on subsets which satisfy the assumption of Theorem 5.3 (see [30, Sec. 9]). But, the excluded cuts may have infinite measure with respect to Σ_{f}. Nonetheless, using perimeter bounds once more, together with the isoperimetric inequality in ℍ (see [60, 21]), it is shown that their contribution to the metric is negligibly small (see [30, Sec. 8]).

By Theorem 5.3, it remains to deal with the situation where all the cuts in the support of Σ_{f} are close to half-spaces: note that we are not claiming in Theorem 5.3 that the half-space is vertical. Nevertheless, a simple geometric argument shows that even in the case of cut measures that are supported on general (almost) halfspaces, the mapping f must significantly distort some distances. The key point here is that if the cut measure is actually supported on half spaces, then it follows (after the fact) that for every affine line L, if x_{1}, x_{2}, x_{3} ∈ L and x_{2} lies between x_{1} and x_{3} then ∥f(x_{1}) − f(x_{3})∥_{1} = ∥f(x_{1}) − f(x_{2})∥_{1} + ∥f(x_{2}) − f(x_{3})∥_{1}. But if L is vertical then d^{ℍ}|_{L} is bi-Lipschitz to the square root of the difference of the z-coordinates, and it is trivial to verify that this metric on L is not bi-Lipschitz equivalent to a metric on L satisfying this additivity condition. For the details of (a quantitative version of) this final step of the argument see [30, Sec. 10].

References

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

[2] L. Ambrosio, N. Fusco, and D. Pallara. Functions of bounded variation and free discontinuity problems. Oxford Mathematical Monographs. The Clarendon Press Oxford University Press, New York, 2000.

[3] N. Aronszajn. Differentiability of Lipschitzian mappings between Banach spaces. Studia Math., 57(2):147–190, 1976.

[4] S. Arora, J. R. Lee, and A. Naor. Fréchet embeddings of negative type metrics. Discrete Comput. Geom., 38(4):726–739, 2007.

[5] S. Arora, J. R. Lee, and A. Naor. Euclidean distortion and the sparsest cut. J. Amer. Math. Soc., 21(1):1–21 (electronic), 2008.

[6] S. Arora, S. Rao, and U. Vazirani. Expander flows, geometric embeddings and graph partitioning. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pages 222–231 (electronic), New York, 2004. ACM.

[7] G. Arzhantseva, C. Drutu, and M. Sapir. Compression functions of uniform embeddings of groups into Hilbert and Banach spaces. J. Reine Angew. Math., 633:213–235, 2009.

[8] P. Assouad. Plongements Lipschitziens dans R^{n}. Bull. Soc. Math. France, 111(4):429–448, 1983.

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

[10] T. Austin, A. Naor, and A. Valette. The Euclidean distortion of the lamplighter group. Preprint, 2007. To appear in Discrete Comput. Geom.

[11] D. Avis and M. Deza. The cut cone, L^{1} embeddability, complexity, and multicommodity flows. Networks, 21(6):595–617, 1991.

[12] K. Ball. Isometric embedding in l_{p}-spaces. European J. Combin., 11(4):305–311, 1990.

[13] S. Bates, W. B. Johnson, J. Lindenstrauss, D. Preiss, and G. Schechtman. Affine approximation of Lipschitz functions and nonlinear quotients. Geom. Funct. Anal., 9(6):1092–1127, 1999.

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

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

[16] J. Bourgain. The metrical interpretation of superreflexivity in Banach spaces. Israel J. Math., 56(2):222–230, 1986.

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

[18] J. Bretagnolle, D. Dacunha-Castelle, and J.-L. Krivine. Lois stables et espaces L^{p}. Ann. Inst. H. Poincaré Sect. B (N.S.), 2:231–259, 1965/1966.

[19] D. Burago, Y. Burago, and S. Ivanov. A course in metric geometry, volume 33 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, [20] S. Buyalo and V. Schroeder. Embedding of hyperbolic spaces in the product of trees.

Geom. Dedicata, 113:75–93, 2005.

[21] L. Capogna, D. Danielli, and N. Garofalo. The geometric Sobolev embedding for vector fields and the isoperimetric inequality. Comm. Anal. Geom., 2(2):203–215, 1994.

[22] S. Chawla. Sparsest cut. In M.-Y. Kao, editor, Encyclopedia of Algorithms. Springer, 2008.

[23] S. Chawla, A. Gupta, and H. Räcke. Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut. ACM Trans. Algorithms, 4(2):Art. 22, 18, 2008.

[24] S. Chawla, R. Krauthgamer, R. Kumar, Y. Rabani, and D. Sivakumar. On the hardness of approximating multicut and sparsest-cut. Comput. Complexity, 15(2):94– 114, 2006.

[25] J. Cheeger and B. Kleiner. Differentiating maps into L^{1} and the geometry of BV functions. To appear in Ann. Math., preprint available at http://arxiv.org/abs/math/0611954, 2006.

[26] J. Cheeger and B. Kleiner. Generalized differentiation and bi-Lipschitz nonembedding in L^{1}. C. R. Math. Acad. Sci. Paris, 343(5):297–301, 2006.

[27] J. Cheeger and B. Kleiner. On the differentiability of Lipschitz maps from metric measure spaces to Banach spaces. In Inspired by S. S. Chern, volume 11 of Nankai Tracts Math., pages 129–152. World Sci. Publ., Hackensack, NJ, 2006.

[28] J. Cheeger and B. Kleiner. Metric differentiation, monotonicity and maps to L^{1}.

Preprint available at http://arxiv.org/abs/0907.3295, 2009.

[29] J. Cheeger, B. Kleiner, and A. Naor. Compression bounds for Lipschitz maps from the Heisenberg group to L_{1}. Preprint, 2009. http://arxiv.org/abs/0910.2026.

[30] J. Cheeger, B. Kleiner, and A. Naor. A (log n)^{Ω(1)} integrality gap for the Sparsest Cut SDP. In Proceedings of 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), pages 555–564, 2009.

[31] J. Chuzhoy and S. Khanna. Polynomial flow-cut gaps and hardness of directed cut problems [extended abstract]. In STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pages 179–188. ACM, New York, 2007.

[32] N. R. Devanur, S. A. Khot, R. Saket, and N. K. Vishnoi. Integrality gaps for sparsest cut and minimum linear arrangement problems. In STOC’06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages 537–546. ACM, New York, 2006.

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

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

[35] B. Franchi, R. Serapioni, and F. Serra Cassano. Rectifiability and perimeter in the Heisenberg group. Math. Ann., 321(3):479–531, 2001.

[36] B. Franchi, R. Serapioni, and F. Serra Cassano. On the structure of finite perimeter sets in step 2 Carnot groups. J. Geom. Anal., 13(3):421–466, 2003.

[37] M. X. Goemans. Semidefinite programming in combinatorial optimization. Math. Programming, 79(1-3, Ser. B):143–161, 1997. Lectures on mathematical programming (ismp97) (Lausanne, 1997).

[38] M. Gromov. Asymptotic invariants of infinite groups. In Geometric group theory, Vol. 2 (Sussex, 1991), volume 182 of London Math. Soc. Lecture Note Ser., pages 1–295. Cambridge Univ. Press, Cambridge, 1993.

[39] M. Gromov. Carnot-Carathéodory spaces seen from within. In Sub-riemannian geometry, Progr. in Math., pages 79–323. Birkhäuser, Basel, 1996.

[40] M. Grötschel, L. Lovász, and A. Schrijver. Geometric algorithms and combinatorial optimization, volume 2 of Algorithms and Combinatorics. Springer-Verlag, Berlin, second edition, 1993.

[41] A. Gupta, R. Krauthgamer, and J. R. Lee. Bounded geometries, fractals, and lowdistortion embeddings. In FOCS, pages 534–543. IEEE Computer Society, 2003.

[42] S. Heinrich. Ultraproducts in Banach space theory. J. Reine Angew. Math., 313:72– 104, 1980.

[43] P. W. Jones. Lipschitz and bi-Lipschitz functions. Rev. Mat. Iberoamericana, 4(1):115–121, 1988.

[44] S. Khot. On the power of unique 2-prover 1-round games. In Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, pages 767–775 (electronic), New York, 2002. ACM.

[45] S. Khot. Inapproximability of NP-complete problems, discrete Fourier analysis, and geometry. To appear in Proceedings of the International Congress of Mathematicians, (Hyderabad, 2010), 2010.

[46] S. Khot, G. Kindler, E. Mossel, and R. O’Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput., 37(1):319–357 (electronic), 2007.

[47] 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 (FOCS 2005), pages 53–62, 2005.

[48] R. Krauthgamer, J. R. Lee, M. Mendel, and A. Naor. Measured descent: a new embedding method for finite metrics. Geom. Funct. Anal., 15(4):839–858, 2005.

[49] R. Krauthgamer and Y. Rabani. Improved lower bounds for embeddings into L_{1}. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1010–1017, New York, 2006. ACM.

[50] J. R. Lee. On distance scales, embeddings, and efficient relaxations of the cut cone. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 92–101 (electronic), New York, 2005. ACM.

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

[52] J. R. Lee and A. Naor. L_{p} metrics on the Heisenberg group and the Goemans-Linial conjecture. In Proceedings of 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pages 99–108. IEEE Computer Society, 2006.

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

[54] N. Linial. Finite metric-spaces—combinatorics, geometry and algorithms. In Proceedings of the International Congress of Mathematicians, Vol. III (Beijing, 2002), pages 573–586, Beijing, 2002. Higher Ed. Press.

[55] N. Linial. Squared ℓ_{2} metrics into ℓ_{1}. In Open problems on embeddings of finite metric spaces, edited by J. Matoušek, page 5. 2002.

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

[57] J. Matoušek. On embedding trees into uniformly convex Banach spaces. Israel J. Math., 114:221–237, 1999.

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

[59] A. Naor, Y. Rabani, and A. Sinclair. Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs. J. Funct. Anal., 227(2):273–303, 2005.

[60] P. Pansu. Une inégalité isopérimétrique sur le groupe de Heisenberg. C. R. Acad. Sci. Paris Sér. I Math., 295(2):127–130, 1982.

[61] P. Pansu. Métriques de Carnot-Carathéodory et quasiisométries des espaces symétriques de rang un. Ann. of Math. (2), 129(1):1–60, 1989.

[62] S. D. Pauls. The large scale geometry of nilpotent Lie groups. Comm. Anal. Geom., 9(5):951–982, 2001.

[63] Y. Rabinovich. On average distortion of embedding metrics into the line. Discrete Comput. Geom., 39(4):720–733, 2008.

[64] S. Rao. Small distortion and volume preserving embeddings for planar and Euclidean metrics. In Proceedings of the Fifteenth Annual Symposium on Computational Geometry (Miami Beach, FL, 1999), pages 300–306 (electronic), New York, 1999. ACM.

[65] I. J. Schoenberg. Metric spaces and positive definite functions. Trans. Amer. Math. Soc., 44(3):522–536, 1938.

[66] S. Semmes. On the nonexistence of bi-Lipschitz parameterizations and geometric problems about A_{∞}-weights. Rev. Mat. Iberoamericana, 12(2):337–410, 1996.

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

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

[69] R. Tessera. Quantitative property A, Poincaré inequalities, L^{p}-compression and L^{p}-distortion for metric measure spaces. Geom. Dedicata, 136:203–220, 2008.

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

[71] P. Wojtaszczyk. Banach spaces for analysts, volume 25 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1991.

New York University, Courant Institute of Mathematical Sciences, 251 Mercer Street, New York, NY 10012, USA E-mail: naor@cims.nyu.edu