Lecture Notes on the ARV Algorithm for Sparsest Cut
Thomas Rothvoss∗
University of Washington, Seattle

arXiv:1607.00854v1 [cs.DS] 4 Jul 2016

July 5, 2016

Abstract
p
One of the landmarks in approximation algorithms is the O( log n)-approximation algorithm for
the Uniform Sparsest Cut problem by Arora, Rao and Vazirani from 2004. The algorithm is based on a
semidefinite program that finds an embedding of the nodes respecting the triangle inequality. Their
core argument shows that a random
p hyperplane approach will find two large sets of Θ(n) many nodes
each that have a distance of Θ(1/ log n) to each other if measured in terms of k · k22 .
Here we give a detailed set of lecture notes describing the algorithm. For the proof of the Structure
Theorem we use a cleaner argument based on expected maxima over k-neighborhoods that significantly simplifies the analysis.

1 Introduction
Let G = (V, E ) be a complete, undirected graph on |V | = n nodes and let c : E → R≥0 be a cost function
on the edges. For a subset S ⊆ V of nodes, let δ(S) := {{i , j } ∈ E | |{i , j } ∩ S| = 1} be the induced cut. We
P
abbreviate c(δ(S)) := e∈δ(S) c(e) as the cost of the cut. The (Uniform) Sparsest Cut problem is then to
find the cut that minimizes the cost-over-separated-pairs ratio:
½
¾
c(δ(U ))
min
| ; ⊂U ⊂ V .
|U | · |V \U |
There is also a non-uniform version of the problem where each pair i , j ∈ V has an associated demand
d (i , j ) ≥ 0 and one aims for the cut minimizing the ratio c(δ(S))/d
(δ(S)). We will now see the celebrated
p
algorithm by Arora, Rao and Vazirani [ARV04] that finds a O( log n)-approximation in polynomial time.
For the algorithm we will not try to optimize any constant. To fix some notation, we will denote any
vector in bold font, like v i ∈ Rm . If we write i ∼ V , then we mean that i is a uniform random node from V .
We denote N (0, 1) as the 1-dimensional Gaussian distribution with mean 0 and variance 1. In particular,
2
a random variable g ∼ N (0, 1) has density p1 e −x /2 . If we write g ∼ N m (0, 1), then we mean that g is
2π
an m-dimensional Gaussian. Recall that the vector g = (g 1 , . . . , g m ) can be generated by sampling each
coordinate independently with g i ∼ N (0, 1). In reverse, for any pair of orthonormal vectors u, v ∈ Rm , the
inner products 〈g , u〉 , 〈g , v 〉 are independently distributed from N (0, 1).
∗ Email: rothvoss@uw.edu. Supported by NSF grant 1420180 with title “Limitations of convex relaxations in combinatorial
optimization” and an Alfred P. Sloan Research Fellowship.

1

2 A semidefinite program
Sparsest Cut is an unusual problem in the sense that it minimizes the ratio of two functions. Let us
assume for the sake of simplicity that we guessed the cost C ∗ and the size S ∗ of an optimum cut, say with
S ∗ ≤ n2 . Then we define a semidefinite programming relaxation
X

X

i ∈V

V
2

{i , j }∈(

X

{i , j }∈E

)

kv i k22

kv i − v j k22

c i j kv i − v j k22
kv i − v j k22
kv i k22
kv 0 k22

= S∗

(I )

= S ∗ · (n − S ∗ )

(I I )

= C∗

(I I I )

≤ kv i − v k k22 + kv k − v j k22
≤ 1
= 0

∀i , j , k ∈ V ∪ {0}
∀i ∈ V

(I V )
(V )
(V I )

where we use an artificial index 0 with v 0 := 0, so that the triangle inequality also holds for the origin.
Lemma 1. If there is cut U ∗ ⊆ V of cost C ∗ and size S ∗ , then the above SDP has a solution.
Proof. One could choose 1-dimensional vectors by defining
(
1 if i ∈ U ∗
v i :=
0 if i ∉ U ∗ .
Then the only non-trivial case is verifying the triangle inequalities in (I V ). These are satisfied by our
choice of v i ∈ {0, 1} since if kv i − v j k22 = 1, then i and j have to be on different sides of the cut U ∗ and any
node k has to be either not on the side of i or not on the side of j .
We can solve the semi-definite program (SDP) in polynomial time [GLS93]; let {v i }i ∈V ⊆ Rm be the
solution. Due to the triangle inequalities (IV) we can define a metric d : V × V → R≥0 by setting d (i , j ) :=
kv i − v j k22 . Note that while k·k2 is always a metric, k·k22 is not a metric on all points sets. For sets of nodes
A, B ⊆ V we define d (i , A) := min{d (i , j ) : j ∈ A} and d (A, B ) := min{d (i , j ) : i ∈ A, j ∈ B }.

3 A ball rounding scheme
Given that family {v i }i ∈V of SDP vectors, there are several natural rounding procedures that would come
to mind. For example one could try the hyperplane rounding that Goemans and Williamson [GW94]
have used for MaxCut. The natural algorithm for Sparsest Cut would be to take a random Gaussian
g ∼ N m (0, 1) and set U := {i ∈ V | 〈g , v i 〉 ≥ 0}. Assume for the sake of simplicity that we are in the balanced
case of Sparsest Cut with S ∗ = Θ(n). Then an edge (i , j ) ∈ E has a contribution to the objective function
of Θ(d (i , j )/n 2 ). On the other hand, the probability that (i , j ) is separated is roughly proportional to the
Euclidean distance kv i − v j k2 and even if the hyperplane generates
p perfectly balanced cuts, the expected
contribution of an edge (i , j ) to the hyperplane cut would be Θ( d (i , j )/n 2 ). In other words, short edges
would be separated far too likely.
The second best idea that one might have, would be to select a node i ∈ V and take a random cut
U := { j ∈ V | d (i , j ) ≤ r } where r ∼ [0, 1]. Now every edge is cut with a probability not exceeding d (i , j ).
On the other hand, this argument seems to not give any guarantee on the size of U and V \U , hence the
2

objective function can be arbitrarily bad again. But a slight fix of this rounding argument can work. We
only need a large “core” of nodes so that the remaining nodes still have a decently large distance to it.
Lemma 2. Suppose we have a set of nodes A ⊆ V with |A| ≥ αn and
2
cut of the form {i ∈ V | d (i , A) ≤ r } is a αβ
-approximation.
Proof. Recall that the optimum value of the objective function is
and take U := U (r ) := {i ∈ V | d (i , A) ≤ r } as a random cut.

P

i ∈V

d (i , A) ≥ β · S ∗ . Then the best

C∗
.
S ∗ ·(n−S ∗ )

Suppose we sample r ∼ [0, 1]

U := U (r )
r

A

Then for an edge (i , j ) ∈ E , say with d (i , A) ≤ d ( j , A), we have
Pr [(i , j ) ∈ δ(U )] = Pr [d (i , A) ≤ r ≤ d ( j , A)]

r ∼[0,1]

triangle inequality

r ∼[0,1]

≤

d (i , j ).

Hence the expected cost of the cut U is
E [c(δ(U ))] ≤

r ∼[0,1]

X

(i , j )∈E

d (i , j ) = C ∗ .

Note that in any case |U | ≥ |A| ≥ αn. We know that d (i , A) ≤ 2 for all i ∈ V and hence Prr ∼[0,1] [i ∉ U ] =
Prr ∼[0,1] [r < d (i , A)] ≥ 12 d (i , A). Hence
E [|V \U |] ≥

r ∼[0,1]

1X
β
d (i , A) ≥ · S ∗ .
2 i ∈V
2

αβ

Then Er ∼[0,1] [|U | · |V \U |] ≥ 2 · S ∗ · n. In other words, the random cut seems to have the right expected
nominator and denominator to satisfy the claim. But this is not enough to argue that their ratio satisfies
c(δ(U ))
2
C∗
· S ∗ ·(n−S
Er ∼[0,1] [ |U |·|V \U | ] ≤ αβ
∗ ) . The following insight comes to rescue:
Fact. Let a, b ∈ Rm
≥0 be non-negative numbers and D be a distribution over indices in [m].
Then
½ ¾
ai
Ei ∼D [a i ]
.
≤
min
i ∈{1,...,m} b i
Ei ∼D [b i ]
Now, this fact implies that best choice of U (over all r ∈ [0, 1]) will indeed satisfy the claim and the lemma
is proven.
We should also remark that if A is given, we can find the cut U in polynomial time as we only need to
try out at most n 2 many values of r .

3

4 The case of heavy clusters
Let B (i , r ) := { j ∈ V | d (i , j ) ≤ r } be the “ball” of radius r around node i . A slight annoyance of the ARV
algorithm is that it requires a case split. If we can find a cluster center i ∗ ∈ V , then we can use Lemma 2
to get a constant factor approximation by just taking a ball around the center i ∗ .
∗

Lemma 3. Suppose there is a node i ∗ ∈ V ∪ {0} with |B (i ∗ , 18 · Sn )| ≥ n4 . Then in polynomial time one can
find a cut that gives a O(1)-approximation.
∗

Proof. We set A := B (i ∗ , 18 · Sn ). Then by assumption |A| ≥ n4 . Moreover, bounding the average distance
of pairs of nodes from above and from below gives
³
triangle ineq.
1 S ∗ S ∗ n − S ∗ (I I )
1 S∗ ´
.
·
≤
·
≤ E [d (i , j )]
≤
2 · E d (i , A) + ·
2 n
n | {z
n }
8 n
i , j ∼V
i ∼V
≥1/2

∗

This can be rearranged to Ei ∼V [d (i , A)] ≥ 81 · Sn . We obtain a 64-approximation by applying Lemma 2.

5 An algorithm for the main case
From now on we make the assumption that no cluster exists:
¯ ³
∗ ´¯¯
¯
¯B i , 1 · S ¯ < n ∀i ∈ V ∪ {0}.
¯
8 n ¯ 4

∗

We will prove that in this case, there are sets L, R ⊆ V of size |L|, |R| ≥ Ω(n) with d (L, R) ≥ ∆ · Sn for ∆ :=
p
Θ(1/ log n). Then choosing Lemma 2 with A := L will give a O( ∆1 )-approximation. Before we start prov∗
ing this, we want to further simplify the situation. Note that by (I ) we have Ei ∼V [d (i , 0)] = Sn , and hence
∗
∗
at most half the nodes can have a distance of more than 2 · Sn to 0. Moreover we have |B (0, 18 · Sn )| ≤ n4 .
∗
∗
Then we only loose a constant factor if we delete those nodes and assume that 18 · Sn ≤ d (i , 0) ≤ 2 · Sn for
p
all remaining nodes. Next we scale the vectors v i by a factor of n/S ∗ , which scales the distances d (i , j )
by a factor of Sn∗ . After this transformation it suffices to prove the following structure theorem:
Theorem 4 (ARV Structure Theorem). Given any set of |V | = n vectors {v i }i ∈V ⊆ Rm with
and |B (i , 18 )| ≤ 43 n for all i ∈ V that satisfy the triangle inequalities

1
8

≤ kv i k22 ≤ 2

kv i − v j k22 ≤ kv i − v k k22 + kv k − v j k22 ∀i , j , k ∈ V.

Then there is a polynomial time algorithm
pthat with constant probability finds sets L, R ⊆ V of size
|L|, |R| ≥ Ω(n) with d (L, R) ≥ ∆ for ∆ := Θ(1/ log n).

From now on, we complete ignore the cost function and only use the properties given in the Structure Theorem. Such sets L and R with d (L, R) ≥ ∆ are called ∆-separated. Let c ′ > 0 be a small enough
constants. The algorithm to produce the ∆-separated sets is as follows:

4

Well-separated sets algorithm
Input: Vectors {v i }i ∈V ⊆ Rm satisfying the triangle inequality with
3
4 n for all i ∈ V ∪ {0}.

Output: Either ∆-separated sets L ′ , R ′ of size |L ′ |, |R ′ | ≥
(1)
(2)
(3)
(4)
(5)
(6)

c′
2n

1
8

≤ kv i k22 ≤ 2 and |B (i , 18 )| ≤

or FAIL

m

Pick a random Gaussian g ∼ N (0, 1)
Set L := {i ∈ V | 〈v i , g 〉 ≤ −1} and R := {i ∈ V | 〈v i , g 〉 ≥ 1}
If either |L| ≤ c ′ n or |R| ≤ c ′ n then FAIL
Compute any inclusion-wise maximal matching M (g ) ⊆ {(i , j ) ∈ L × R | d (i , j ) ≤ ∆}
′
If |M (g )| > c2 n then FAIL
Return L ′ := {i ∈ L | i not covered by M (g )} and R ′ := {i ∈ V | i not covered by M (g )}

Observe that any pair i ∈ L ′ and j ∈ R ′ that remains will have d (i , j ) > ∆ as otherwise the matching M (g )
′
would not have been maximal. Also, if the algorithm reaches (6), then min{|L ′ |, |R ′ |} ≥ c2 n.
L

R

L′

R′

i

∈ M (g )

j

d (i , j ) ≤ ∆
g
The first step is to argue that with constant probability both L and R have size at least Ω(n).
Lemma 5. There is an absolute constant c ′ > 0 so that Prg ∼N m (0,1) [min{|L|, |R|} ≥ c ′ n] ≥ c ′ .
Proof. We will prove that E[|L| · |R|] ≥ Ω(n 2 ) which then implies the claim. Fix any i ∈ V and select one of
the at least 41 n nodes j with d (i , j ) ≥ 81 . Let w be the orthogonal projection of v j on v i , see figure below.
Let α ∈ [0, π2 ] be the angle between v i − v j and w and let β ∈ [0, π2 ] be the angle between v j and w . Due to
the triangle inequalities, the angle spanned by the points 0, v i and v j is non-obtuse and α + β ≤ π2 . Then
we have either α ≤ π4 and
1
kw k2 = cos(α) · kv i − v j k2 ≥
| {z } | {z } 4
p
p
≥1/ 8

≥1/ 2

or otherwise we have β ≤

π
4

and

1
kw k2 = cos(β) · kv j k2 ≥
| {z } | {z } 4
p
≥1/ 2

5

p
≥1/ 8

Either way, kw k2 ≥ 41 . Since v i ⊥ w , the inner products 〈g , v i 〉 and 〈g , w 〉 are independent random variables and we can estimate
Pr[i ∈ L and j ∈ R] ≥ Pr[−2 ≤ 〈g , v i 〉 ≤ −1 and 〈g , w 〉 ≥ 3]
h
h
vi
1
2 i
3 i
w
〉≤−
〉≥
≤ 〈g ,
= Pr −
>0
· Pr 〈g ,
kv i k2
kv i k2
kv i k2
kw k2
kw k
| {z 2}
| {z
}
∈[ p1 , p1 ]
8

≤12

2

which is some tiny, yet absolute constant. Note that in case the latter event happens, then indeed
〈v i , v j 〉
〈g , v j 〉 = 〈g , v i 〉 ·
+ 〈g , w 〉 ≥ 1.
| {z } kv i k2 | {z }
2
| {z }
≥−2
≥3
∈[0,1]

vi

w

p

2

0

α
β

vj

p1
8

This implies that with a constant probability, the algorithm does not fail in (3). The main technical
part lies in proving that Eg ∼N m (0,1) [|M (g )|] ≤ cn where we can make the constant c as small as we want,
′
′
′
at the expense of a smaller value of ∆. If we choose c := ( c2 )2 , then Pr[|M (g )| > c2 ] ≤ c2 and the success
probability of the algorithm is at least

c′
.
2

6 The proof of the Structure Theorem
p
The following geometric theorem by Arora, Rao and Vazirani is the heart of their O( log n)-approximation
−2/3
for Sparsest Cut. To be precise, the original ARV
)
p result [ARV04] only showed this theorem for ∆ = Θ((log n)
and needed a lot of extra work to get the O( log n)-approximation. The claim as it is stated here was first
proven by Lee [Lee05]. For an edge set E ′ , let β(E ′ ) be the size of the maximum matching.
p
Theorem 6 ([ARV04, Lee05]). For any constant c > 0 there is a choice of ∆ := Θc (1/ log n) so that the
following holds: Let {v i }i ∈V ⊆ Rm be a set of |V | = n vectors satisfying the triangle inequality

kv i − v j k22 ≤ kv i − v k k22 + kv k − v j k22 ∀i , j , k ∈ V.

For a vector g ∈ Rm define

©
ª
E (g ) := (i , j ) ∈ V × V | 〈v j − v i , g 〉 ≥ 2 and kv i − v j k22 ≤ ∆ .

Then Eg ∼N m (0,1) [β(E (g ))] ≤ cn .

6

Here we think of E (g ) as directed edges. Let M (g ) be a maximum matching attaining β(E (g )). We
will assume the existence of such a matching M (g ) and lead this to a contradiction. By inducing on a
subgraph and reducing the constant c one can even assume that for every node the probability of having
an outgoing edge is at least c and the same is true for ingoing edges. First, there is no harm in assuming
that M (g ) has the reverse edges of M (−g ), which implies that each node has an outgoing edge with the
same probability as it has an incoming edge.
Lemma 7. Assume that Theorem 6 is false for vectors {v i }i ∈V ⊆ Rm . Then there is a subset V ′ ⊆ V of size
|V ′ | ≥ cn and a matching M ′ (g ) ⊆ M (g ) on V ′ so that every node i ∈ V ′ has an outgoing edge in M ′ (g )
with probability at least c8 and an ingoing edge with probability at least c8 .
Proof. For each node i ∈ V define p(i ) := Prg ∼N m (0,1) [i has outgoing edge in M (g )]. If there is a node
i with p(i ) ≤ 8c , then we imagine to delete the node from the graph and remove from M (g ) any edge
containing node i . Note that this decreases the expected size of the matching by at most 2· 8c . We continue
this procedure until no such node exists anymore. Let V ′ be the remaining set of nodes with M ′ (g ) :=
M (g ) ∩ (V ′ × V ′ ). Then Eg ∼N m (0,1) [|M ′ (g )|] ≥ Eg ∼N m (0,1) [|M (g )|] − n · 4c ≥ c2 n. Then there must be at least
|V ′ | ≥ cn many nodes left.
After changing the constants and adapting the value of n, we assume to have n nodes and for every
node i ∈ V , the matching M (g ) has an outgoing and an incoming edge with probability at least c.
We call an edge (i , j ) ∆-short if d (i , j ) ≤ ∆. For a node i ∈ V , let Γ(i ) := { j ∈ V | d (i , j ) ≤ ∆} be the
neighborhood of i with respect to the graph of ∆-short edges. Moreover, let Γk (i ) := Γk−1 (Γ(i )) be the
nodes that can be reached from i via at most k many ∆-short edges.
Lemma 8. For any k ∈ Z≥0 and i ′ ∈ Γk (i ) one has kv i − v i ′ k2 ≤

p
k∆.

Proof. We have kv i − v i ′ k22 = d (i , i ′ ) ≤ k · ∆ by the SDP triangle inequality. Taking square roots gives the
claim.
At the heart of the arguments lies the fact that the value of Lipschitz functions is well concentrated.
Recall that a function F : Rm → R is called L-Lipschitz, if |F (x) − F (y )| ≤ L · kx − y k2 for all x, y ∈ Rm .
Lemma 9 (Concentration for Lipschitz Functions (Sudakov-Tsirelson, Borrell)). Let F : Rm → R be an L 1
2
Lipschitz function with Gaussian mean µ := Eg ∼N m (0,1) [F (g )]. Then Prg ∼N m (0,1) [|F (g )−µ| ≥ α] ≤ 2e − 2 ·(α/L)
for any α ≥ 0.
We define a function
F i ,k (g ) := max{〈g , v i − v j 〉 | j ∈ Γk (i )}.
In other words, F i ,k (g ) gives the maximum inner product 〈g , v i − v j 〉 over all nodes j ∈ V that are within
k many ∆-short edges of node i . Note that F i ,k (g ) ≥ 〈g , v i − v i 〉 = 0 for all g ∈ Rm as i ∈ Γk (i ).
Lemma 10. The function F i ,k : Rm → R is

p
k · ∆-Lipschitz.

Proof. Fix g , g ′ ∈ Rm and assume for the sake of symmetry that F (g ) ≥ F (g ′ ). Let j , j ′ ∈ Γk (i ) be the nodes

7

attaining F (g ) and F (g ′ ), resp. Then
Cauchy-Schwarz

|F (g ) − F (g ′ )| = 〈g , v i − v j 〉 − 〈g ′ , v i − v j ′ 〉 ≤ 〈g − g ′ , v i − v j 〉

≤

kg − g ′ k2 · kv i − v j k2 .
| {z }
p
≤ k·∆ by Lem. 8

Here we used in the first inequality that j ′ ∈ Γk (i ) maximizes 〈g ′ , v i − v j ′ 〉.

Now, let µi ,k := Eg ∼N m (0,1) [F i ,k (g )] be the expected maximum inner product over k-neighbors of node
i ∈ V . One useful argument will be a nice relation between expectations of neighbors:
Lemma 11. For any node i ∈ V and i ′ ∈ Γ(i ) and k ∈ Z≥0 one has µi ′ ,k+1 ≥ µi ,k .
Proof. We have
µi ′ ,k+1

=

Em

g ∼N (0,1)

′

Γk+1 (i )⊇Γk (i )

≥

Em

g ∼N (0,1)

h
£

n
oi
max 〈v i ′ − v i , g 〉 + 〈v i − v j , g 〉 | j ∈ Γk+1 (i ′ )

©
ª¤
max 〈v i − v j , g 〉 | j ∈ Γk (i ) +

E

[〈v i ′ − v i , g 〉] = µi ,k .
{z
}

g ∼N m (0,1)

|

=0

On the other hand, we can get the following upper bound:
p
p
Lemma 12. For any k ∈ Z≥0 and any i ∈ V one has µi ,k ≤ 10 log n · k∆.

Proof. For any j ∈ Γk (i ) we have kv i − v j k2 ≤
Pr

g ∼N m (0,1)

h

p

k∆ and generously

q
p i Z∞
〈v i − v j , g 〉 ≥ 8 log n · k∆ ≤ p
8

logn

2
1
1
.
p e −x /2 d x ≤
2n
2π

p
p
p
m (0,1) [F i ,k (g ) ≤ 8
That means
log n· k∆] ≥ 1/2. Again, F i ,k is k∆-Lipschitz, hence Prg ∼N m (0,1) [|F i ,k (g )−
p Prg ∼N
p
µi ,k | ≥ 2 k∆] ≤ 12 and 2 ≤ 2 log(n) for n ≥ 2.

6.1 Extend or expand
The core argument to get to a contradiction is the following:
1
log(1/c) · ∆1 } be parameters and U ⊆ {i ∈ V | µi ,k ≥ δ} be a set
Lemma 13. Let ∆ > 0, δ ∈ R and k ∈ {0, . . . , 100
of nodes. Then

(A) either there is a subset U ′ ⊆ Γ(U ) so that |U ′ | ≥ 4c · |U | and µi ,k+1 ≥ δ + 1 for all i ∈ U ′ .
(B) or the neighborhood U ′ := Γ(U ) satisfies |U ′ | ≥ c4 · |U | and µi ,k+1 ≥ δ for all i ∈ U ′ .
Proof. If |Γ(U )| ≥ 4c · |U |, then every node in i ∈ Γ(U ) has µi ,k+1 ≥ δ by Lemma 11 and we are in case (B).
So suppose that |Γ(U )| < c4 · |U |. Consider the random matching
n
1o
M̃(g ) := (i , j ) ∈ M (g ) | i ∈ U and F i ,k (g ) ≥ δ −
2

8

that is the restriction of M (g ) to edges that are going out
p of U and where F i ,k (g ) is large enough. Note
m
that µi ,k = Eg ∼N (0,1) [F i ,k (g )] ≥ δ for all i ∈ U and F i ,k is k∆-Lipschitz. Hence by Lemma 10 we have
³
h
1 ´ c
1i
≤ 2 exp −
<
F i ,k (g ) < δ −
(0,1)
2
8k∆
2

Pr
m

g ∼N

∀i ∈ U .

This implies that each node in U will have an outgoing edge in M̃ (g ) with probability at least 2c . Now,
2

c
define U ′ := { j ∈ Γ(U ) | Pr[ j has incoming edge from M̃ (g )] ≥ 16
}. Since M̃(g ) is a matching we have

c
c2
c
· |U | ≤ E[|M̃ (g )|] ≤
· |Γ(U ) \U ′ | +|U ′ | ≤ · |U | + |U ′ |
|
{z
}
2
16
4
≤(4/c)·|U |

which implies that |U ′ | ≥ 4c · |U |. Now fix a node j ∈ U ′ . It remains to argue that µ j ,k+1 ≥ δ + 1 for all
j ∈ U ′ . First, condition on the event that M̃ (g ) has an edge incoming to j . We denote that edge by
(i (g ), j ) ∈ M̃ (g ) with i (g ) ∈ U 1 . We know by the definition of M̃ (g ) that 〈v j − v i (g ) , g 〉 ≥ 2. Moreover, we
know that there is a node h(g ) ∈ Γk (i (g )) so that 〈v i (g ) − v h(g ) , g 〉 ≥ δ − 12 .
Γ(U )
U
Γk (i (g ))

U′
M̃ (g )

h(g )

i (g )

j

Then 〈v j − v h(g ) , g 〉 = 〈v j − v i (g ) , g 〉 + 〈v i (g ) − v h(g ) , g 〉 ≥ δ + 32 . In other words, Prg ∼N m (0,1) [F j ,k+1(g ) ≥ δ +
p
3
c2
2 ] ≥ 16 . Again, the function F j ,k+1 is (k + 1)∆-Lipschitz and
´ c2
³
h
1
1 i Lem. 9
<
≤ 2 exp −
|F j ,k+1(g ) − µ j ,k+1 | ≥
(0,1)
2
8(k + 1)∆
16

Pr
m

g ∼N

and hence µ j ,k+1 ≥ δ + 1. This shows the claim.
Now, suppose we run Lemma 13 iteratively, starting with U := V and in each iteration we replace
the current U by the set U ′ . We iterate this until the upper bound on k is reached. Note that case (B)
1
cannot happen more often than case (A) as always |Γ(U )| ≤ n. Then after being k = 100∆
log(1/c) times
in Case (A) and ℓ ∈ {0, . . . k} times in Case (B), we end up with a set U ⊆ V with |U | ≥ n · ( 4c )k−ℓ ≥ n · ( 4c )k
p
p
and µi ,2k ≥ µi ,k+ℓ ≥ k for allp
i ∈ U . On the other hand, µi ,2k ≤ 10 log n · 2k∆ by Lemma 12. Choosing
∆ := Θc ( p 1 ) and k := Θc ( log n) with proper choice of constants, then gives a contradiction.
logn

Acknowledgement. The author is very grateful to James R. Lee, Harishchandra Ramadas, Rebecca Hoberg
and Alireza Rezaei for helpful discussion and comments.
1 Here we write i (g ) to indicate that this node will depend on the choice of g .

9

References
[ARV04] Sanjeev Arora, Satish Rao, and Umesh V. Vazirani. Expander flows, geometric embeddings and
graph partitioning. In László Babai, editor, Proceedings of the 36th Annual ACM Symposium on
Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pages 222–231. ACM, 2004.
[GLS93] Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algorithms and combinatorial optimization, volume 2 of Algorithms and Combinatorics. Springer-Verlag, Berlin, second
edition, 1993.
[GW94] Michel X. Goemans and David P. Williamson. .879-approximation algorithms for MAX CUT
and MAX 2sat. In Frank Thomson Leighton and Michael T. Goodrich, editors, Proceedings of
the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal,
Québec, Canada, pages 422–431. ACM, 1994.
[Lee05] James 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, SODA 2005,
Vancouver, British Columbia, Canada, January 23-25, 2005, pages 92–101. SIAM, 2005.

10

