$\textsc{BalSparseCut}_{\alpha,\lambda}(\cdot,\psi)$ with sparsity parameters
$\psi\in(0,1)$ that satisfy $\psi\leq\frac{1}{10\alpha}$.

From Lemma 6.1 one readily obtains the theorems by either using a brute force
$(1,1)$-BSCA or a polynomial time $(O(\log^{3}n),O(1))$-BSCA.

###### Proof of Theorem 2.1.

It is easy to get an exponential time $(1,1)$-BSCA as per Definition 5.2.
Given a graph and a parameter $\psi\in(0,1)$, one can do this by brute-forcing
all possible cuts in the input graph: either return $\omega=\bot$ if all the
cuts are $\psi$-expanding, or return $\omega=(R,\nu)$ where $R$ is the
$\psi$-sparse cut with maximum volume, and $\nu$ is its volume. The space
requirement of this algorithm is linear in the size of its input.

We then have parameters $\alpha=1,\lambda=1$, and we set $k=\log n$. Hence,
for any $b\leq 1/\log^{2}n$ and $\epsilon\leq b\log n$, we meet the
preconditions of Lemma 6.1: $b\leq 1/\log n$, $\alpha=1\leq\frac{1}{b\log n}$,
$\lambda=O(1)$, $k\leq\log n$, and

$\frac{\log{n^{5}\alpha}}{\log\frac{1}{\lambda\sqrt{b}}}\leq\frac{O(\log
n)}{\Omega(\log\log n)}\leq k\,,$

where the first inequality follows because $\alpha=\lambda=1$, and $b\leq
1/\log^{2}n$. Therefore, by Lemma 6.1 there is a dynamic stream algorithm that
with high probability outputs a $(b,\epsilon,\phi,\gamma)$-BLD of $G$ where

$\phi=\Omega\left(\frac{\epsilon}{\alpha\log
n}\right)=\Omega\left(\frac{\epsilon}{\log n}\right)\quad\text{ and
}\quad\gamma=O(\alpha^{k+1})=O(1)\,.$

Its space complexity is

$\widetilde{O}(k\cdot n/b^{3})\cdot\alpha^{O(k)}=\widetilde{O}(n/b^{3})\,,$

since for the brute force algorithm we have $S(p,q)=\widetilde{O}(q)$. The
running time is $2^{O(n)}$ since the brute force algorithm has
$T(p,q)=\widetilde{O}(q)\cdot 2^{p}$. ∎

###### Proof of Theorem 2.2.

For the polynomial time version, we use the following BSCA.

######  Theorem 6.2 ([SW19, LNPS23]).

For $p$-vertex $q$-edge input graphs with polynomially bounded edge weights
and self-loops, there is a
$(c_{\operatorname*{\textsc{bsc}}}\log^{3}p,C_{\operatorname*{\textsc{bsc}}})$-BSCA
that runs in time $\widetilde{O}(p+q)$ and works with high probability for
every input sparsity parameter
$0<\psi\leq\frac{1}{10c_{\operatorname*{\textsc{bsc}}}\log^{3}p}$, where
$c_{\operatorname*{\textsc{bsc}}},C_{\operatorname*{\textsc{bsc}}}\geq 1$ are
absolute constants.

This easily follows from the ED-based BSCA of [SW19], combined with the faster
ED algorithm of [LNPS23], except that here we explicitly allow for input
graphs with arbitrary self-loops. We defer to Appendix A.1 a discussion on how
to reduce from inputs with self-loops to self-loop free ones. Another
technical detail is that the algorithm from Theorem 6.2 is a balanced sparse
cut algorithm on any input with high probability. First note that we can boost
the success probability of this algorithm to $1-1/\operatorname*{poly}(n)$
even when it is applied on graphs much smaller than $n$, simply by doing
$\log^{O(1)}n$ independent repetitions. Also, one can see that the decoding of
Lemma 6.1 (i.e. Algorithms 3 and 4) calls
$\textsc{BalSparseCut}_{\alpha,\lambda}$ on disjoint portions of
$\widetilde{O}(1/b)\cdot\alpha^{O(k)}$ sparsifiers (see the proof of Lemma
6.1). Since the running time of this BSCA (with the probability boosting) is
$\widetilde{O}(p+q)\log^{O(1)}n$ on $p$-vertex $q$-edge graphs, we have that
it uses at most as many random bits. Then, because this is applied to disjoint
portions of $\widetilde{O}(1/b)\cdot\alpha^{O(k)}$ sparsifiers, each having at
most $\widetilde{O}(n/b^{2})\cdot\alpha^{O(k)}$ edges, we only need
$\widetilde{O}(n/b^{3})\cdot\alpha^{O(k)}$ random bits in order to avoid
adaptivity and at the same time ensure that all the calls work correctly with
probability $1-1/\operatorname*{poly}(n)$. As this fits into our claimed space
budget, we can then pretend that this BSCA is deterministic. From Lemma 6.1 we
also know that the algorithm never calls
$\textsc{BalSparseCut}_{\alpha,\lambda}$ with sparsity parameters larger than
$\frac{1}{10\alpha}$, so if we set
$\alpha=c_{\operatorname*{\textsc{bsc}}}\log^{3}n\geq
c_{\operatorname*{\textsc{bsc}}}\log^{3}p$ our setting matches the requirement
of Theorem 6.2.

Now we plug
$\alpha=c_{\operatorname*{\textsc{bsc}}}\log^{3}n,\lambda=C_{\operatorname*{\textsc{bsc}}}$
and set $k=\frac{\log{n^{5}\alpha}}{\log{b^{-1/2}}/{\lambda}}$, and verify the
preconditions of Lemma 6.1. For any $b\leq 1/\log^{5}n$ and $\epsilon\leq
b\log n$, have that $\lambda=C_{\operatorname*{\textsc{bsc}}}=O(1)$ and

$\alpha=c_{\operatorname*{\textsc{bsc}}}\log^{3}n\leq\log^{4}n\leq\frac{1}{b\log
n}\,.$

We also have that $k=O(\log n/\log\log n)\leq\log n$, since
$\alpha=O(\log^{3}n)$, $\lambda=O(1)$, and $b\leq 1/\log^{5}n$. Therefore, the
lemma gives a dynamic stream algorithm that with high probability outputs a
$(b,\epsilon,\phi,\gamma)$-BLD of $G$ where

$\phi=\Omega\left(\frac{\epsilon}{\alpha\log
n}\right)=\Omega\left(\frac{\epsilon}{\log^{4}n}\right)\quad\text{ and
}\quad\gamma=O(\alpha^{k+1})=\log^{O(\frac{\log n}{\log 1/b})}n\,.$

Since the BSCA from Theorem 6.2 runs in time $\widetilde{O}(q)$ on a $q$-edge
graph, its space requirement must also be $\widetilde{O}(q)$. Hence the
overall space complexity is

$\widetilde{O}(k\cdot
n/b^{3})\cdot\alpha^{O(k)}+\widetilde{O}(n/b^{2})\cdot\alpha^{O(k)}=\widetilde{O}(n/b^{3})\cdot\log^{O(\frac{\log
n}{\log 1/b})}n\,.$

The running time is $\operatorname*{poly}(n)$, since
$\textsc{BalSparseCut}_{\alpha,\lambda}$ takes at most
$\operatorname*{poly}(n)$ time, since in our setting for $b$, $k$, and
$\alpha$ we have $\widetilde{O}(n/b^{2})\cdot\alpha^{O(k)}\leq n^{O(1)}$. ∎

##### Overview of the algorithm.

We now give the BLD construction for Lemma 6.1. Algorithms 3 and 4 outline the
core procedure, which is almost the same as the one of [FKM23]. For BLD
parameters $b$ and $\epsilon$ we set $\phi$ appropriately in terms of
$\epsilon$, and our goal is to show that calling Algorithm 3 as
$\textsc{Decompose}(V,0)$ gives a BLD of $G$.

Algorithm 3 Decompose: space efficient implementation of Algorithm 1 for BLD
construction

1: $\triangleright$ _$b,\phi\in(0,1)$ are global BLD parameters_

2: $\triangleright$ _$\alpha,\lambda$ are the parameters of
$\textsc{BalSparseCut}_{\alpha,\lambda}$_

3: $\triangleright$ _$C\geq 1,\,c\in(0,1)$ are constant parameters_
$\textsc{Decompose}(U,\ell)$ $\triangleright$ cluster $U\subseteq V$,
recursion level $\ell\geq 0$

4:$H=(V,E^{\prime},w)\leftarrow\textsc{Sparsifier}^{c}_{\ell}(U,b)$
$\triangleright$ sparsifier for $U$ in this level

5:$\omega\leftarrow\textsc{BalSparseCut}_{\alpha,\lambda}(H[U]^{\circ},(1+\frac{1}{2\log
n})\cdot\phi)$

6:$\omega=\bot$ $\\{U\\}$ $\triangleright$ if $U$ is an expander, return

7:$(R,\nu)\leftarrow\omega$ $\triangleright$ otherwise, if $R$ is balanced
enough, recurse on both sides
$\nu\geq\frac{1}{C\lambda}\operatorname{vol}_{U}^{\circ\,w}(U)$
$\textsc{Decompose}(R,\ell+1)\,\cup\,\textsc{Decompose}(U\setminus R,\ell+1)$

8:

9:$(S,\exp)\leftarrow\textsc{Trim}(U,\ell)$ $\triangleright$ find an expander
inside $U$, or settle for a less sparse balanced cut $\exp=\top$
$\triangleright$ if $S$ induces an expander, recurse on the complementary only

10:$\\{S\\}\cup\textsc{Decompose}(U\setminus S,\ell+1)$ $\triangleright$
otherwise, $S$ should be decently sparse and balanced, so recurse on both
sides

11:$\textsc{Decompose}(S,\ell+1)\,\cup\,\textsc{Decompose}(U\setminus
S,\ell+1)$

Algorithm 4 Trim: trim some cuts to find an expander, or find a less sparse
but balanced cut

1: $\triangleright$ _$b,\phi\in(0,1)$ are global BLD parameters_

2: $\triangleright$ _$\alpha,\lambda$ are the parameters of
$\textsc{BalSparseCut}_{\alpha,\lambda}$_

3: $\triangleright$ _$C\geq 1,\,c\in(0,1)$ are constant parameters_

4: $\triangleright$ _$k$ is a positive integer_
$\textsc{Trim}(U,\ell)$$\triangleright$ cluster $U\subseteq V$, recursion
level $\ell\geq 0$

5:$b_{0}\leftarrow b,\,\,\,\phi_{0}\leftarrow\phi,\,\,\,A\leftarrow U$
$j=1,\dots,k+1$

6: $b_{j}\leftarrow\frac{b_{j-1}}{(1+\frac{1}{\log
n})\cdot\alpha},\,\,\,\phi_{j}\leftarrow\frac{\phi_{j-1}}{(1+\frac{1}{\log
n})\cdot\alpha}$

7:$h=1,2,\dots,\infty$

8:$H=(V,E^{\prime},w)\leftarrow\textsc{Sparsifier}^{c}_{\ell,j,h}(A,b_{j})$
$\triangleright$ sparsifier for $A$ in this level and iteration

9:$\omega\leftarrow\textsc{BalSparseCut}_{\alpha,\lambda}(H[A]^{\circ},(1+\frac{1}{2\log
n})\cdot\phi_{j})$

10:$\omega=\bot$ $(A,\top)$ $\triangleright$ $\top$ means $A$ is an expander

11:$(R,\nu)\leftarrow\omega$
$\nu\geq\frac{1}{C\lambda}\operatorname{vol}_{U}^{\circ\,w}(U)$ $(R,\bot)$
$\triangleright$ $\bot$ means $R$ is a cut

12:$\nu\geq\frac{1}{C\lambda}\left(\operatorname{vol}_{U}^{\circ\,w}(U)\right)^{1-({j-1})/{k}}$
$\triangleright$ trim

13:$A\leftarrow A\setminus R$ $\triangleright$ go to next outer loop
iteration, if this happens we should have $j\leq k$

14:break

Algorithm 3 is a space efficient implementation of Algorithm 1 for BLD. In
line (5), it uses a BSCA on a sparsifier either to certify that the given
cluster is already an expander, or to find a sparse cut in it. In the former
case it can simply return the cluster. In the latter case, if the condition
(7) finds the cut to be balanced enough, the algorithm can afford to recurse
on both sides keeping the recursion depth under control. Otherwise, it calls
Algorithm 4. This procedure is supposed to either trim off a small volume mass
from the cluster in line (13) so that the remainder induces an expander (see
return statement in line (10)), or find a less sparse but more balanced cut
than the one obtained in line (5) of Algorithm 3 (see return statement in line
(11)). In the former case, Algorithm 3 can then recurse only on the trimmed
part of the cluster (recursion of line (10)), whereas in the latter it is
still acceptable to recurse on both sides while keeping the recursion depth
under control (recursion of line (11)).

As both algorithms run a BSCA on weighted subgraphs of $G$, we use Lemma 5.3
to analyse their behaviour with respect to the input $G$. It is then crucial
that the graphs on which the BSCA is run are sparsifiers for the cluster at
hand. Therefore, we will implement lines (4) and (8) in Algorithms 3 and 4
respectively via the algorithm from Lemma 4.2. Crucially, we want to
instantiate enough independent copies of the sparsification algorithm, so that
lines (4) and (8) can always access a fresh sparsifier. The memory requirement
is then determined by the sparsifiers that we maintain, while the correctness
will be proved using Lemma 5.3.

##### Roadmap.

In the next sections we prove Lemma 6.1. In Section 6.1, we work under the
assumption that line (4) of Algorithm 3 and (8) of Algorithm 4 always behave
as expected, meaning that they return a sparsifier for the cluster at hand. In
this ideal setting, we show that Algorithm 3 outputs a BLD in small recursion
depth and few iterations. Then, with Lemma 4.2, in Section 6.2 we lift the
assumption that line (4) of Algorithm 3 and (8) of Algorithm 4 are
deterministically correct, thus concluding a proof of Lemma 6.1.

###  6.1 Offline analysis

The algorithms have hardwired parameters $k,\alpha,\lambda,C,c$. The BLD
parameters $b,\phi\in(0,1)$ are given as input (for now, we parametrize the
BLD by $b$ and $\phi$ instead of $b$ and $\epsilon$, and will later specify
how to define $\phi$ from $\epsilon$). Hereafter, whenever we use
$b,\phi,k,C,c,\alpha,\lambda,(b_{j})_{j},(\phi_{j})_{j}$, we are referring to
the corresponding parameter in Algorithms 3 and 4.

As one can see from the pseudocode, the input graph $G$ is not simply fed to
Algorithms 3 and 4, but they have restricted access to it: their interaction
with $G$ is limited to lines (4) and (8) respectively, i.e. they only have
sparsifier-access to it. In this section we work under the assumption that the
algorithms can always obtain a sparsifier that meets the precondition of Lemma
5.3, i.e. they are cluster sparsifiers with appropriate error (see Definition
4.1).

######  Assumption 1.

Every time line (4) of Algorithm 3 calls $\textsc{Sparsifier}^{c}_{\ell}(U,b)$
for some $\ell\geq 0,\,U\subseteq V$, it gets a graph $H=(V,E^{\prime},w)$
such that $H[U]\approx_{\delta}G[U]$, where $\delta=c^{2}b/\log n$.

######  Assumption 2.

Every time line (8) of Algorithm 4 calls
$\textsc{Sparsifier}^{c}_{\ell,j,h}(A,b_{j})$ for some $\ell~{}\geq~{}0$,
$j,h~{}\geq~{}1$, $A\subseteq V$, it gets a graph $H=(V,E^{\prime},w)$ such
that $H[A]\approx_{\delta_{j}}G[A]$, where $\delta_{j}=c^{2}b_{j}/\log n$.

Throughout this section, we will use the definition $\delta=c^{2}b/\log n$ and
$\delta_{j}=c^{2}b_{j}/\log n$ for all $j\in[k+1]$, as in 1 and 2. To
illustrate why in the second assumption we have $\delta_{j}$ instead of
$\delta$, we make the following observation.

######  Observation 6.3.

For a constant $c\leq 1/30$, $\phi<b$, $b\leq c$, $\alpha\leq\frac{1}{2b}$, a
cluster $A~{}\subseteq~{}V$, and a sparsifier $H=(V,E^{\prime},w)$ such that
$H[A]\approx_{\delta_{j}}G[A]$, Lemma 5.3 guarantees that calling an
$(\alpha,\lambda)$-BSCA as
$\textsc{BalSparseCut}_{\alpha,\lambda}(H[A]^{\circ},(1+\frac{1}{2\log
n})\cdot\phi_{j})$ gives a $(\phi_{j},(1+\frac{1}{\log
n})\alpha,(1+c)\lambda,c)$-BSCW of $G[A]^{\circ}$ (as in line (9) of Algorithm
4).

###### Proof of 6.3.

For a constant $c\leq 1/30$, parameters $b,\phi,\delta,\alpha$ such that
$\phi<b$, $b\leq c$, $\alpha\leq\frac{1}{2b}$, a cluster $A~{}\subseteq~{}V$,
and a sparsifier $H=(V,E^{\prime},w)$ such that $H[A]\approx_{\delta}G[A]$,
Lemma 5.3 guarantees that calling an $(\alpha,\lambda)$-BSCA as
$\textsc{BalSparseCut}_{\alpha,\lambda}(H[A]^{\circ},(1+0.5/{\log
n})\cdot\phi)$ gives a $(\phi,(1+\frac{1}{\log n})\alpha,(1+c)\lambda,c)$-BSCW
of $G[A]^{\circ}$. Then, we recall that $G[A]^{\circ}=G[A]^{b/\phi}$ and
$H[A]^{\circ}=H[A]^{b/\phi}$, so it also holds that
$G[A]^{\circ}=G[A]^{b_{j}/\phi_{j}}$ and $H[U]^{\circ}=H[U]^{b_{j}/\phi_{j}}$,
since we can see from Algorithm 4 that $b_{j}/\phi_{j}=b/\phi$ for all
$j\in[k+1]$. Moreover, observe the following: $\phi<b$ if and only if
$\phi_{j}<b_{j}$, $\alpha\leq\frac{1}{2b}$ implies
$\alpha\leq\frac{1}{2b_{j}}$ (by definition of $b_{j}$ in Algorithm 4), and
$b\leq c$ implies $b_{j}\leq c$ (again, by definition of $b_{j}$ in Algorithm
4). One can then use Lemma 5.3 replacing $b,\phi,\delta$ with
$b_{j},\phi_{j},\delta_{j}$ respectively, hence getting 6.3. ∎

The goal of this section is threefold: in Section 6.1.3, we bound the number
of iterations that any execution of Algorithm 4 can go through; in Section
6.1.4, we bound the recursion depth of Algorithm 3; in Section 6.1.5, we show
the output of calling Algorithm 3 as $\textsc{Decompose}(V,0)$ is a BLD of
$G$. Interestingly, Section 6.1.5 crucially uses the results from Section
6.1.3 and Section 6.1.4 about recursion depth and number of iterations.
Before, we give some preliminary results: in Section 6.1.1 we give properties
of cuts of boundary-linked subgraphs; in Section 6.1.2, we show how relations
between volume estimates (such as the comparisons performed by Algorithm 3 in
line (7) and by Algorithm 4 in lines (11) and (12)) translate to relations
between the actual volumes of the corresponding cuts.

####  6.1.1 Properties of nested cuts

When Algorithm 3 makes a cut in the input cluster $U$, this cut is then fed as
input to the recursive call in line (7), which will in turn try to find a cut
inside it. Similarly, Algorithm 4 makes a cut in the current cluster $A$ in
line (13), and in the next iteration it will try to find a cluster inside the
remainder of $A$. The leitmotif of these algorithms is that they try to make
cuts inside a cluster that is one side of a cut previously made. It is then
useful for the analysis to relate volume and sparsity of nested cuts.

######  Lemma 6.4 (Properties of nested cut).

Let $b,\phi\in(0,1)$ and $\delta>0$ be such that $\phi\leq b$, $\delta<1/b$.
Fix a cluster $U\subseteq V$, let $\emptyset\neq S\subsetneq U$ be a cut such
that $\Phi_{U}^{\circ}(S)<\delta\cdot\phi$, and let $T\subseteq S$. Then we
have the following relations between volumes:

$\operatorname{vol}_{U}^{\circ}(T)\overset{(1)}{\leq}\operatorname{vol}_{S}^{\circ}(T)\overset{(2)}{<}\operatorname{vol}_{U}^{\circ}(T)+\delta
b\cdot\min\\{\operatorname{vol}_{U}^{\circ}(S),\operatorname{vol}_{U}^{\circ}(U\setminus
S)\\}\overset{(3)}{\leq}\operatorname{vol}_{U}^{\circ}(U)\,.$

If it also holds that $\emptyset\neq T\subsetneq S$ has
$\Phi_{S}^{\circ}(T)<\delta\cdot\phi$ and
$\operatorname{vol}_{U}^{\circ}(T\cup(U\setminus
S))<\frac{1}{2}\operatorname{vol}_{U}^{\circ}(U)$ then

$\Phi_{U}^{\circ}(T\cup(U\setminus S))<\delta\cdot\phi\,.$

###### Proof.

For convenience let $\psi=\delta\cdot\phi$. Inequality (1) holds simply
because $T\subseteq S\subseteq U$, so the number of self-loops attached to $T$
cannot decrease when going from $G[U]^{\circ}$ to $G[S]^{\circ}$. Inequality
(2) can be obtained by rewriting the volumes in $G[S]^{\circ}$ as

$\displaystyle\operatorname{vol}_{S}^{\circ}(T)=\operatorname{vol}(T)+\frac{b-\phi}{\phi}\operatorname{bnd}_{S}(T)$
$\displaystyle=\operatorname{vol}_{U}^{\circ}(T)+\frac{b-\phi}{\phi}|E(T,U\setminus
S)|$ (6.1)
$\displaystyle\leq\operatorname{vol}_{U}^{\circ}(T)+\frac{b}{\phi}|E(T,U\setminus
S)|\,.$ (6.2)

Since $S$ is $\psi$-sparse in $G[U]^{\circ}$, we can upper-bound
$|E(T,U\setminus S)|$ by
${\partial}_{U}S<\psi\min\\{\operatorname{vol}_{U}^{\circ}(S),\operatorname{vol}_{U}^{\circ}(U\setminus
S)\\}$, thus getting the bound. For inequality (3), note
$\operatorname{vol}_{U}^{\circ}(T)\leq\operatorname{vol}_{U}^{\circ}(S)$
because $T\subseteq S$ and $\delta
b\cdot\min\\{\operatorname{vol}_{U}^{\circ}(S),\operatorname{vol}_{U}^{\circ}(U\setminus
S)\\}\leq\operatorname{vol}_{U}^{\circ}(U\setminus S)$ for $\delta\leq 1/b$.
Since
$\operatorname{vol}_{U}^{\circ}(S)+\operatorname{vol}_{U}^{\circ}(U\setminus
S)=\operatorname{vol}_{U}^{\circ}(U)$, we have the bound (3).

Suppose now that $\emptyset\neq T\subsetneq S$ has $\Phi_{S}^{\circ}(T)<\psi$
and $\operatorname{vol}_{U}^{\circ}(T\cup(U\setminus
S))<\frac{1}{2}\operatorname{vol}_{U}^{\circ}(U)$. First observe that because
$\Phi_{S}^{\circ}(T)<\psi$, the definition of $\Phi_{S}^{\circ}(T)$ yields
${\partial}_{S}T<\psi\operatorname{vol}_{S}^{\circ}(T)$. By Eq. 6.2, we also
have

${\partial}_{S}T<\psi\operatorname{vol}_{S}^{\circ}(T)\leq\psi\operatorname{vol}_{U}^{\circ}(T)+\frac{\psi
b}{\phi}\cdot|E(T,U\setminus
S)|\leq\psi\operatorname{vol}_{U}^{\circ}(T)+|E(T,U\setminus S)|\,,$ (6.3)

where we used that $\psi b/\phi\leq 1$ since $\psi=\delta\phi$ and $\delta\leq
1/b$. Due to $\operatorname{vol}_{U}^{\circ}(T\cup(U\setminus
S))<\frac{1}{2}\operatorname{vol}_{U}^{\circ}(U)$, the definition of
$\Phi_{U}^{\circ}(T\cup(U\setminus S))$ finally yields

$\displaystyle\Phi_{U}^{\circ}(T\cup(U\setminus S))$
$\displaystyle=\frac{{\partial}_{U}(T\cup(U\setminus
S))}{\operatorname{vol}_{U}^{\circ}(T\cup(U\setminus S))}$ since $T\subseteq
S$, so $T\cap(U\setminus S)=\emptyset$
$\displaystyle=\frac{{\partial}_{S}T+{\partial}_{U}S-|E(T,U\setminus
S)|}{\operatorname{vol}_{U}^{\circ}(T)+\operatorname{vol}_{U}^{\circ}(U\setminus
S)}$ by (6.3)
$\displaystyle<\frac{\psi\operatorname{vol}_{U}^{\circ}(T)+|E(T,U\setminus
S)|+{\partial}_{U}S-|E(T,U\setminus
S)|}{\operatorname{vol}_{U}^{\circ}(T)+\operatorname{vol}_{U}^{\circ}(U\setminus
S)}$
$\displaystyle=\frac{\psi\operatorname{vol}_{U}^{\circ}(T)+{\partial}_{U}S}{\operatorname{vol}_{U}^{\circ}(T)+\operatorname{vol}_{U}^{\circ}(U\setminus
S)}$
$\displaystyle\leq\max\left\\{\psi,\frac{{\partial}_{U}S}{\operatorname{vol}_{U}^{\circ}(U\setminus
S)}\right\\}=\max\left\\{\psi,\Phi_{U}^{\circ}(S)\right\\}$ since
$\Phi_{U}^{\circ}(S)<\psi$ $\displaystyle\leq\psi\,.$

∎

Algorithm 4 makes cuts iteratively. It finds a cut in the cluster, it trims it
off in line (13), it finds another cut in the remainder, it trims it off, and
so on, provided that these cuts verify certain conditions: their individual
volumes are neither too large (if one of them was very large in volume, the
algorithm would return in line (11)) nor too small (see condition (12)). The
following lemma proves properties of such cut sequences. Figure 3 should help
the reader to visualize the statement and the proof.

Figure 3: Sequence of nested cuts.

######  Lemma 6.5 (Properties of a sequence of nested cuts).

Let $b,\phi\in(0,1)$ be such that $\phi\leq b$, and $\delta\in(0,1]$. Fix a
cluster $U\subseteq V$, let $\theta\in\mathbb{R}_{\geq 0}$ be such that
$\theta\leq\frac{1}{5}\operatorname{vol}_{U}^{\circ}(U)$, and let
$R_{1},\dots,R_{t}$ be a sequence of cuts $\emptyset\neq R_{i}\subsetneq
U^{<i}$ where $U^{<i}=U\setminus(\cup_{z=1}^{i-1}R_{z})$ for all $i\in[t]$. If

  1. 1.

for all $\emptyset\neq X\subsetneq U$ with $\Phi_{U}^{\circ}(X)<\delta\phi$
and
$\operatorname{vol}_{U}^{\circ}(X)\leq\operatorname{vol}_{U}^{\circ}(U\setminus
X)$ one has $\operatorname{vol}_{U}^{\circ}(X)~{}<~{}\theta$, and

  2. 2.

for all $i\in[t]$ one has $\Phi_{U^{<i}}^{\circ}(R_{i})<\delta\phi$ and
$\operatorname{vol}_{U^{<i}}^{\circ}(R_{i})<\frac{1}{5}\operatorname{vol}_{U}^{\circ}(U)$,

then we have the following.

  1. 1.

For all $i\in[t]$, one has $\Phi_{U}^{\circ}(\cup_{z=1}^{i}R_{z})<\delta\phi$
and $\operatorname{vol}_{U}^{\circ}(\cup_{z=1}^{i}R_{z})<\theta$.

  2. 2.

For all $i\in[t]$, if there is
$\theta^{\operatorname*{low}}\in\mathbb{R}_{\geq 0}$ such that
$\operatorname{vol}_{U^{<i}}^{\circ}(R_{i})\geq\theta^{\operatorname*{low}}$
then one also has
$\operatorname{vol}_{U}^{\circ}(R_{i})\geq\theta^{\operatorname*{low}}-b\cdot\theta$.

  3. 3.

Let $U^{<t+1}=U\setminus(\cup_{z=1}^{t}R_{z})$. If $\emptyset\neq R\subsetneq
U^{<t+1}$ is a cut such that $\Phi_{U^{<t+1}}^{\circ}(R)<\delta\phi$ and
$\theta^{\operatorname*{low}}\leq\operatorname{vol}_{U^{<t+1}}^{\circ}(R)\leq\frac{5}{9}\operatorname{vol}_{U^{<t+1}}^{\circ}(U^{<t+1})$
for some
$\theta^{\operatorname*{low}}\leq\frac{4}{9}\operatorname{vol}_{U}^{\circ}(U)$,
then
$\Phi_{U}^{\circ}(R)<\delta\phi\cdot\frac{\operatorname{vol}_{U}^{\circ}(U)}{\theta^{\operatorname*{low}}-b\cdot\theta}$
and
$\theta^{\operatorname*{low}}-b\cdot\theta\leq\operatorname{vol}_{U}^{\circ}(R)\leq\frac{5}{9}\operatorname{vol}_{U}^{\circ}(U)$.

The end goal of part (1) is to upper bound the number of edges crossing and
the remaining volume when Algorithm 4 returns $(A,\top)$ and therefore
Algorithm 3 recurses on $U\setminus A$ only (see line (6) in Algorithm 3). The
idea is that in this case $U\setminus A$ corresponds to the union of nested
cuts that are trimmed off by Algorithm 4.

Part (2) will be useful to bound the number of iterations that Algorithm 4 can
take. In every iteration a cut is trimmed off, and from condition (12) we know
the volume of these cuts to be not too small in $U^{<i}$. From part (2) we
then know these volumes to be not too small in $U$ either, and hence the
number of such cuts cannot be too large, since they are disjoint.

The end goal of part (3) is to upper bound the number of edges crossing and
the remaining volume when Algorithm 4 returns $(R,\bot)$ and therefore
Algorithm 3 recurses on $R$ and $U\setminus R$ (see line (7) in Algorithm 3).
The idea is that in this case, every cut trimmed off by Algorithm 4 is sparse
and far from being balanced (because of condition (11) in Algorithm 4),
whereas the last one is both sparse and somewhat balanced (because of
condition (11) in Algorithm 4).

In the remainder of this section we prove the three parts of this lemma.

###### Proof of Lemma 6.5, part (1).

Intuitively, the union of a sequence of nested sparse and small cuts should be
sparse and small too. We prove this by induction on $i\in[t]$. Denote for
convenience $\psi~{}=~{}\delta~{}\phi$.

The base case for $i=1$ readily follows. Since $U^{1}=U$, we have
$\Phi_{U}^{\circ}(R_{1})<\psi$ and also
$\operatorname{vol}_{U}^{\circ}(R_{1})<\frac{1}{5}\operatorname{vol}_{U}^{\circ}(U)$
from precondition (2). Moreover, by precondition (1), there is no
$\psi$-sparse cut $X$ with
$\theta\leq\operatorname{vol}_{U}^{\circ}(X)<\frac{1}{2}\operatorname{vol}_{U}^{\circ}(U)$.
Hence, it must be the case that
$\operatorname{vol}_{U}^{\circ}(R_{1})<\theta$.

For the inductive step, take $i\in[t-1]$ and assume that
$\Phi_{U}^{\circ}(\cup_{z=1}^{i}R_{z})<\psi$ and
$\operatorname{vol}_{U}^{\circ}(\cup_{z=1}^{i}R_{z})<\theta$. We now apply
Lemma 6.4 with $S=U^{<i+1}$ and $T=R_{i+1}$. We can do so because
$\Phi_{U}^{\circ}(S)=\Phi_{U}^{\circ}(\cup_{z=1}^{i}R_{z})<\psi$, so the lemma
gives

$\displaystyle\operatorname{vol}_{U}^{\circ}(R_{i+1})\leq\operatorname{vol}_{U^{<i+1}}^{\circ}(R_{i+1})\leq\frac{1}{5}\operatorname{vol}_{U}^{\circ}(U)<\frac{1}{4}\operatorname{vol}_{U}^{\circ}(U)\,.$

Combining this bound with the inductive hypothesis that
$\operatorname{vol}_{U}^{\circ}(\cup_{z=1}^{i}R_{z})<\theta$, one has

$\operatorname{vol}_{U}^{\circ}(\cup_{z=1}^{i+1}R_{z})=\operatorname{vol}_{U}^{\circ}(\cup_{z=1}^{i}R_{z})+\operatorname{vol}_{U}^{\circ}(R_{i+1})<\theta+\operatorname{vol}_{U}^{\circ}(R_{i+1})<\frac{1}{5}\operatorname{vol}_{U}^{\circ}(U)+\frac{1}{4}\operatorname{vol}_{U}^{\circ}(U)<\frac{1}{2}\operatorname{vol}_{U}^{\circ}(U)\,,$

which rewrites as $\operatorname{vol}_{U}^{\circ}(T\cup(U\setminus
S))<\frac{1}{2}\operatorname{vol}_{U}^{\circ}(U)$ with $S=U^{<i+1}$ and
$T=R_{i+1}$. Also, from precondition (2), we have
$\Phi_{U^{<i+1}}^{\circ}(R_{i+1})<\psi$, or in other words
$\Phi_{S}^{\circ}(T)<\psi$ with $S=U^{<i+1}$ and $T=R_{i+1}$. Then, the second
part of Lemma 6.4 gives $\Phi_{U}^{\circ}(\cup_{z=1}^{i+1}R_{z})<\psi$, so one
part of the induction is proved. For the other part, we combine
$\Phi_{U}^{\circ}(\cup_{z=1}^{i+1}R_{z})<\psi$ and
$\operatorname{vol}_{U}^{\circ}(\cup_{z=1}^{i+1}R_{z})<\frac{1}{2}\operatorname{vol}_{U}^{\circ}(U)$
with precondition (1): since we assume there is no $\psi$-sparse cut in
$G[U]^{\circ}$ with volume sandwiched between $\theta$ and
$\frac{1}{2}\operatorname{vol}_{U}^{\circ}(U)$, it must be the case that
$\operatorname{vol}_{U}^{\circ}(\cup_{z=1}^{i+1}R_{z})<\theta$. ∎

###### Proof of Lemma 6.5, part (2).

We prove this using part (1) and Lemma 6.4. The case of $i=1$ follows from the
preconditions, since $U^{1}=U$. Let then $i=2,\dots,t$, and denote for
convenience $\psi~{}=~{}\delta~{}\phi$. Then, part (1) gives that
$\Phi_{U}^{\circ}(\cup_{z=1}^{i-1}R_{z})<\psi$. If we set $S=U^{<i}$ and
$T=R_{i}$ we have
$\Phi_{U}^{\circ}(S)=\Phi_{U}^{\circ}(\cup_{z=1}^{i-1}R_{z})<\psi$, and can
then apply Lemma 6.4 to get the lower bound

$\displaystyle\operatorname{vol}_{U}^{\circ}(R_{i})$
$\displaystyle>\operatorname{vol}_{U^{<i}}^{\circ}(R_{i})-\delta
b\cdot\operatorname{vol}_{U}^{\circ}(\cup_{z=1}^{i-1}R_{z})$ since $\delta\leq
1$
$\displaystyle\geq\operatorname{vol}_{U^{<i}}^{\circ}(R_{i})-b\cdot\operatorname{vol}_{U}^{\circ}(\cup_{z=1}^{i-1}R_{z})\,.$

Part (1) also gives
$\operatorname{vol}_{U}^{\circ}(\cup_{z=1}^{i-1}R_{z})<\theta$, and since we
assume that
$\operatorname{vol}_{U^{<i}}^{\circ}(R_{i})\geq\theta^{\operatorname*{low}}$,
one concludes

$\operatorname{vol}_{U}^{\circ}(R_{i})>\operatorname{vol}_{U^{<i}}^{\circ}(R_{i})-b\cdot\operatorname{vol}_{U}^{\circ}(\cup_{z=1}^{i-1}R_{z})\geq\theta^{\operatorname*{low}}-b\cdot\theta\,.$

∎

###### Proof of Lemma 6.5, part (3).

We begin by analysing the volume $\operatorname{vol}_{U}^{\circ}(R)$. Again,
from part (1) we have

$\Phi_{U}^{\circ}(\cup_{i=1}^{t}R_{i})<\delta\phi\,,\quad\operatorname{vol}_{U}^{\circ}(\cup_{i=1}^{t}R_{i})<\theta\,.$

Setting $\psi=\delta\phi$, $S=U^{<t+1}$ and $T=R$, we have
$\Phi_{U}^{\circ}(S)=\Phi_{U}^{\circ}(\cup_{z=1}^{t}R_{z})<\psi$, so we can
apply Lemma 6.4 to yield

$\operatorname{vol}_{U}^{\circ}(R)>\operatorname{vol}_{U^{<t+1}}^{\circ}(R)-b\cdot\operatorname{vol}_{U}^{\circ}(\cup_{i=1}^{t}R_{i})>\theta^{\operatorname*{low}}-b\cdot\theta\,,$
(6.4)

and

$\operatorname{vol}_{U}^{\circ}(R)\leq\operatorname{vol}_{U^{<t+1}}^{\circ}(R_{t})\leq\frac{5}{9}\operatorname{vol}_{U^{<t+1}}^{\circ}(U^{<t+1})\,.$
(6.5)

We can once more apply Lemma 6.4 with $S=T=U^{<t+1}$ (since again
$\Phi_{U}^{\circ}(S)=\Phi_{U}^{\circ}(\cup_{z=1}^{t}R_{z})<\psi$), so

$\operatorname{vol}_{U^{<t+1}}^{\circ}(U^{<t+1})\leq\operatorname{vol}_{U}^{\circ}(U)\,.$
(6.6)

We then have from (6.4), (6.5), (6.6)

$\theta^{\operatorname*{low}}-b\cdot\theta\leq\operatorname{vol}_{U}^{\circ}(R)\leq\frac{5}{9}\operatorname{vol}_{U^{<t+1}}^{\circ}(U^{<t+1})\leq\frac{5}{9}\operatorname{vol}_{U}^{\circ}(U)\,.$
(6.7)

Next we analyse the sparsity of $R$ by first upper-bounding the quantity
${\partial}_{U}R$:

$\displaystyle{\partial}_{U}R$
$\displaystyle\leq{{\partial}_{U^{<t+1}}R+{\partial}_{U}(\cup_{i=1}^{t}R_{i})}$
(6.8) since $\Phi_{U^{<t+1}}^{\circ}(R)<\psi$ by assumption
$\displaystyle<{\psi\cdot\operatorname{vol}_{U^{<t+1}}^{\circ}(R)+{\partial}_{U}(\cup_{i=1}^{t}R_{i})}$
(6.9) since $\Phi_{U}^{\circ}(\cup_{i=1}^{t}R_{i})<\psi$ from part (1)
$\displaystyle<{\psi\cdot\operatorname{vol}_{U^{<t+1}}^{\circ}(R)+\psi\cdot\operatorname{vol}_{U}^{\circ}(\cup_{i=1}^{t}R_{i})}$
(6.10) since
$\operatorname{vol}_{U}^{\circ}(R)<\frac{5}{9}\operatorname{vol}_{U}^{\circ}(U)$
from (6.7)
$\displaystyle<{\psi\cdot\frac{5}{9}\cdot\operatorname{vol}_{U}^{\circ}(U)+\psi\cdot\operatorname{vol}_{U}^{\circ}(\cup_{i=1}^{t}R_{i})}$
(6.11) since $\operatorname{vol}_{U}^{\circ}(\cup_{i=1}^{t}R_{i})<\theta$ from
part (1)
$\displaystyle<\psi\cdot\frac{5}{9}\cdot\operatorname{vol}_{U}^{\circ}(U)+\psi\cdot\theta$
(6.12) by assumption on $\theta$
$\displaystyle<\psi\cdot{\operatorname{vol}_{U}^{\circ}(U)}\,.$ (6.13)

On the other hand, the bounds in (6.7) yield

$\displaystyle\min\\{\operatorname{vol}_{U}^{\circ}(R),\operatorname{vol}_{U}^{\circ}(U\setminus
R)\\}$
$\displaystyle\geq\min\left\\{\theta^{\operatorname*{low}}-b\cdot\theta,\frac{4}{9}\operatorname{vol}_{U}^{\circ}(U)\right\\}$
(6.14) since
$\theta^{\operatorname*{low}}\leq\frac{4}{9}\operatorname{vol}_{U}^{\circ}(U)$
by assumption $\displaystyle=\theta^{\operatorname*{low}}-b\cdot\theta\,.$
(6.15)

From the bound (6.13) and (6.15) we finally conclude

$\Phi_{U}^{\circ}(R)=\frac{{\partial}_{U}R}{\min\\{\operatorname{vol}_{U}^{\circ}(R),\operatorname{vol}_{U}^{\circ}(U\setminus
R)\\}}<\frac{\psi\cdot{\operatorname{vol}_{U}^{\circ}(U)}}{\theta^{\operatorname*{low}}-b\cdot\theta}\,.$

∎

####  6.1.2 Relations between volume estimates

In this section we show how relations between volume estimates (such as the
comparisons performed by Algorithm 3 in line (7) and by Algorithm 4 in lines
(11) and (12)) translate to relations between the actual volumes of the
corresponding cuts.

######  Lemma 6.6 (Relations between volume estimates).

Let $b,\phi,c\in(0,1)$ be such that $c\leq 1/4$ is a constant and $\phi\leq
b$. Fix a cluster $U\subseteq V$, and also let $H=(V,E^{\prime},w)$ such that
$H[U]^{\circ}\approx_{c}G[U]^{\circ}$, and let $\omega$ be a
$(\psi,\alpha^{\prime},\lambda^{\prime},c)$-BSCW of $G[U]^{\circ}$ for some
$\psi\in(0,\phi]$ and $\alpha^{\prime},\lambda^{\prime}\geq 1$. If
$\omega=(R,\nu)$ for some $\emptyset\neq R\subsetneq U$ and
$\nu\in\mathbb{R}_{>0}$, then for any $\rho,\tau\in[0,1]$ and $X\subseteq V$
we have

  1. 1.

if $\nu\geq\rho\cdot\left(\operatorname{vol}_{X}^{\circ\,w}(X)\right)^{\tau}$,
then
$\operatorname{vol}_{U}^{\circ}(R)\geq\rho/2\cdot\left(\operatorname{vol}_{X}^{\circ}(X)\right)^{\tau}$.

  2. 2.

if $\nu<\rho\cdot\left(\operatorname{vol}_{X}^{\circ\,w}(X)\right)^{\tau}$,
then
$\operatorname{vol}_{U}^{\circ}(R)<2\rho\cdot\left(\operatorname{vol}_{X}^{\circ}(X)\right)^{\tau}$
and for every cut $\emptyset\neq S\subsetneq U$ with
$\Phi_{U}^{\circ}(S)<\psi$ and
$\operatorname{vol}_{U}^{\circ}(S)\leq\operatorname{vol}_{U}^{\circ}(U\setminus
S)$ one has
$\operatorname{vol}_{U}^{\circ}(S)<2\lambda^{\prime}\rho\cdot\left(\operatorname{vol}_{X}^{\circ}(X)\right)^{\tau}$.

###### Proof.

From property (2d) of the definition of BSCW (see Definition 5.1), we know
$(1-c)\operatorname{vol}_{U}^{\circ}(R)\leq\nu\leq(1+c)\operatorname{vol}_{U}^{\circ}(R)$,
and from property (2b) we know that for every cut $\emptyset\neq S\subsetneq
U$ with $\Phi_{U}^{\circ}(S)<\psi$ and
$\operatorname{vol}_{U}^{\circ}(S)\leq\operatorname{vol}_{U}^{\circ}(U\setminus
S)$ one has
$\operatorname{vol}_{U}^{\circ}(S)<\lambda^{\prime}\cdot\operatorname{vol}_{U}^{\circ}(R)$.

On the other hand,
$(1-c)\operatorname{vol}_{X}^{\circ}(X)\leq\operatorname{vol}_{X}^{\circ\,w}(X)\leq(1+c)\operatorname{vol}_{X}^{\circ}(X)$
for any $X\subseteq V$. To see why, first note that
$\operatorname{vol}_{X}^{\circ\,w}(X)=\operatorname{vol}^{w}(X)+\frac{b-\phi}{\phi}\operatorname{bnd}_{X}^{w}(X)=\operatorname{vol}^{w}(X)+\frac{b-\phi}{\phi}\partial^{w}X$,
and analogously
$\operatorname{vol}_{X}^{\circ}(X)=\operatorname{vol}(X)+\frac{b-\phi}{\phi}{\partial}X$.
Then, since $H[U]^{\circ}\approx_{c}G[U]^{\circ}$, we have the approximation
guarantee for global cuts (see Definition 4.1): applying it to all singleton
cuts in $X$ we can approximate $\operatorname{vol}(X)$, and applying it to $X$
we can approximate ${\partial}X$.

From the above discussion it follows that for all $\rho,\tau\in[0,1]$ and
$X\subseteq V$,
$\nu\geq\rho\cdot\left(\operatorname{vol}_{X}^{\circ\,w}(X)\right)^{\tau}$
implies
$\operatorname{vol}_{U}^{\circ}(R)\geq\rho\frac{1-c}{1+c}\cdot\left(\operatorname{vol}_{X}^{\circ}(X)\right)^{\tau}\geq\rho/2\cdot\left(\operatorname{vol}_{X}^{\circ}(X)\right)^{\tau}$,
since $c\leq 1/4$. If instead
$\nu<\rho\cdot\left(\operatorname{vol}_{X}^{\circ\,w}(X)\right)^{\tau}$, we
have
$\operatorname{vol}_{U}^{\circ}(R)<\rho\frac{1+c}{1-c}\cdot\left(\operatorname{vol}_{X}^{\circ}(X)\right)^{\tau}\leq
2\rho\cdot\left(\operatorname{vol}_{X}^{\circ}(X)\right)^{\tau}$. Moreover,
since by definition of $\omega$ one has
$\operatorname{vol}_{U}^{\circ}(S)<\lambda^{\prime}\cdot\operatorname{vol}_{U}^{\circ}(R)$
for every cut $\emptyset\neq S\subsetneq U$ with $\Phi_{U}^{\circ}(S)<\psi$
and
$\operatorname{vol}_{U}^{\circ}(S)\leq\operatorname{vol}_{U}^{\circ}(U\setminus
S)$, we get
$\operatorname{vol}_{U}^{\circ}(S)<\lambda^{\prime}\cdot\operatorname{vol}_{U}^{\circ}(R)\leq\lambda^{\prime}2\rho\cdot\left(\operatorname{vol}_{X}^{\circ}(X)\right)^{\tau}$
for any such $S$. ∎

####  6.1.3 Bounding the number of iterations

Combining the structural properties of nested cuts together with Lemma 6.6, we
can show the correctness of the algorithms. We begin by observing that
whenever Algorithm 4 breaks the inner loop in line (14) we have $j\leq k$.
This ensures that restraining the outer loop to indices $j=1,\dots,k+1$ (see
line (5)) does not lead to undefined behaviour.

######  Lemma 6.7 (Algorithm 4 does few outer loop iterations).

Let $b,\phi,c\in(0,1)$ such that $c\leq 1/30$ is a constant, $\phi<b$ and
$b\leq c$. Also let $C\geq 3$ be a constant, and let
$\textsc{BalSparseCut}_{\alpha,\lambda}$ be an $(\alpha,\lambda)$-BSCA where
$\alpha\leq\frac{1}{2b}$. If 2 holds, then if Algorithm 4 breaks in line (14)
it is in some outer loop iteration $j$ with $j\leq k$.

###### Proof.

We prove this by contradiction, so suppose the algorithm enters line (14) with
$j=k+1$ for some inner loop iteration $h\geq 1$. Let $A$ be the value of the
corresponding variable in Algorithm 4 at the beginning of inner loop iteration
$h$ within outer loop iteration $k+1$. Also let $H=(V,E^{\prime},w)$ be the
graph gotten from line (8) in the same iteration. From the description of the
algorithm, since it entered line (14), the call
$\textsc{BalSparseCut}_{\alpha,\lambda}(H[A]^{\circ},(1+{1}/{(2\log
n)})\cdot\phi_{k+1})$ from line (9) has returned a BSCW of the form $(R,\nu)$
such that
$\nu<\frac{1}{C\lambda}(\operatorname{vol}_{U}^{\circ\,w}(U))^{1-(k+1-1)/k}=\frac{1}{C\lambda}(\operatorname{vol}_{U}^{\circ\,w}(U))^{0}$.
Moreover, since we have $c\leq 1/30$, $\phi<b$, $b\leq c$,
$\alpha\leq\frac{1}{2b}$, and $H[A]\approx_{\delta_{k+1}}G[A]$ (from 2), Lemma
5.3 ensures that $(R,\nu)$ is a $(\phi_{j},(1+\frac{1}{\log
n})\alpha,(1+c)\lambda,c)$-BSCW of $G[A]^{\circ}$ (see 6.3).

We now want to use Lemma 6.6 with $\psi=\phi_{k+1}$,
$\alpha^{\prime}=(1+\frac{1}{\log n})\alpha$, $\lambda^{\prime}=(1+c)\lambda$,
$\rho=\frac{1}{C\lambda}$, $\tau=0$, and $X=U$. These parameters verify the
conditions for applying Lemma 6.6 to $(R,\nu)$ on $G[A]^{\circ}$: $c\leq
1/30\leq 1/4$, $\psi=\phi_{k+1}\leq\phi$ (by definition of $\phi_{k+1}$ in the
algorithm), $\alpha^{\prime},\lambda^{\prime}\geq 1$, $\rho\leq 1$,
$\tau\in[0,1]$, $H[A]\approx_{c}G[A]$ (since $H[A]\approx_{\delta_{k+1}}G[A]$
and $\delta_{k+1}\leq c$), and hence $(R,\nu)$ is a
$(\phi_{j},(1+\frac{1}{\log n})\alpha,(1+c)\lambda,c)$-BSCW of $G[A]^{\circ}$.
Then Lemma 6.6 gives

$\operatorname{vol}_{A}^{\circ}(R)<2\rho(\operatorname{vol}_{U}^{\circ}(U))^{\tau}=\frac{2}{C\lambda}<1\,,$

which in particular implies $R=\emptyset$. However, this contradicts the fact
that $(R,\nu)$ is a BSCW of $G[A]^{\circ}$ (see Definition 5.1). ∎

Next, we show that Algorithm 4 verifies the preconditions (1) and (2) of Lemma
6.5. Specifically, if Algorithm 3 calls Algorithm 4, there cannot be sparse
and balanced cuts in $U$, and also every cut trimmed by Algorithm 4 is sparse
and small in volume. This will later allow us to apply Lemma 6.5 for bounding
the number of inner loop iterations (and also for bounding the recursion
depth, in the next section).

######  Lemma 6.8 (Algorithm 4 makes a sequence of nested sparse small cuts).

Let $b,\phi,c\in(0,1)$ such that $c\leq 1/30$ is a constant, $\phi<b$ and
$b\leq c$. Also let $C\geq 11$ be a constant, and let
$\textsc{BalSparseCut}_{\alpha,\lambda}$ be an $(\alpha,\lambda)$-BSCA where
$\alpha\leq\frac{1}{2b}$. Consider an execution of Algorithm 4 called from
Algorithm 3 on input cluster $U\subseteq V$. Also let
$R_{1},\dots,R_{q}\subseteq U$ be the sequence of $q$ cuts trimmed in line
(13) by Algorithm 4, and let $U^{<i}=U\setminus(\cup_{z-1}^{i-1}R_{z})$. If 1
and 2 hold, then

  1. 1.

for all $\emptyset\neq S\subsetneq U$ with $\Phi_{U}^{\circ}(S)<\phi$,
$\operatorname{vol}_{U}^{\circ}(S)\leq\operatorname{vol}_{U}^{\circ}(U\setminus
S)$, one has
$\operatorname{vol}_{U}^{\circ}(S)<\frac{3}{C}\operatorname{vol}_{U}^{\circ}(U)$,

  2. 2.

for all $i\in[q]$ one has $\Phi_{U^{<i}}^{\circ}(R_{i})<\phi$ and
$\operatorname{vol}_{U^{<i}}^{\circ}(R_{i})<\frac{1}{5}\operatorname{vol}_{U}^{\circ}(U)$.

###### Proof.

From the description of Algorithms 3 and 4, we see that Algorithm 4 starts
only if line (5) of Algorithm 3 returns a BSCW $\omega=(R,\nu)$ such that
$\nu<\frac{1}{C\lambda}\operatorname{vol}_{U}^{\circ\,w}(U)$, as per line (9)
(otherwise, Algorithm 3 would not call Algorithm 4). Now we want to apply
Lemma 5.3 to $\omega$. Because we have $c\leq 1/30$, $\phi<b$, $b\leq c$,
$\delta=c^{2}b/\log n$, $\alpha\leq\frac{1}{2b}$ and
$H[U]\approx_{\delta}G[U]$ from 1, all the preconditions of Lemma 5.3 are met
for us to apply it to the call
$\textsc{BalSparseCut}_{\alpha,\lambda}(H[U]^{\circ},(1+\frac{1}{2\log
n})\cdot\phi)$ from line (5) of Algorithm 3: hence, $\omega$ is a
$(\phi,(1+\frac{1}{\log n})\alpha,(1+c)\lambda,c)$-BSCW of $G[U]^{\circ}$.
Since we observed just above that $\omega$ is of the form $(R,\nu)$ and
$\nu<\frac{1}{C\lambda}\operatorname{vol}_{U}^{\circ\,w}(U)$, we now use Lemma
6.6 with parameters $\psi=\phi$, $\alpha^{\prime}=(1+\frac{1}{\log n})\alpha$,
$\lambda^{\prime}=(1+c)\lambda$, $\rho=\frac{1}{C\lambda}$, $\tau=1$, and
$X=U$. These parameters verify the requirement of Lemma 6.6 since we have
$c\leq 1/30\leq 1/4$, $H[U]\approx_{c}G[U]$ (from 1, since $\delta\leq c$),
$\psi\leq\phi$, $\alpha^{\prime},\lambda^{\prime}\geq 1$, $\rho,\tau\leq 1$,
and $(R,\nu)$ is a $(\phi,(1+\frac{1}{\log n})\alpha,(1+c)\lambda,c)$-BSCW of
$G[U]^{\circ}$. Then we get that for every cut $\emptyset\neq S\subsetneq U$
with $\Phi_{U}^{\circ}(S)<\phi$ and
$\operatorname{vol}_{U}^{\circ}(S)\leq\operatorname{vol}_{U}^{\circ}(U\setminus
S)$ one has

$\operatorname{vol}_{U}^{\circ}(S)<2\lambda^{\prime}\rho\cdot\operatorname{vol}_{U}^{\circ}(U)=\frac{2(1+c)\lambda}{C\lambda}\operatorname{vol}_{U}^{\circ}(U)\leq\frac{3}{C}\cdot\operatorname{vol}_{U}^{\circ}(U)\,.$

This gives part (1).

For all $i\in[q]$, denote by $j(i)\in[k+1]$ the outer loop iteration of
Algorithm 4 where $R_{i}$ was trimmed, and also let
$U^{<i}=U\setminus(\cup_{z=1}^{i-1}R_{z})$ (i.e., at the beginning of the
iteration where $R_{i}$ has been trimmed we had $A=U^{<i}$). Then, from the
description of the algorithm we know that $R_{i}$ was paired with a value
$\nu_{R_{i}}$ such that $(R_{i},\nu_{R_{i}})$ was the result of
$\textsc{BalSparseCut}_{\alpha,\lambda}(H[U^{<i}]^{\circ},(1+\frac{1}{2\log
n})\cdot\phi_{j(i)-1})$, where $H=(V,E^{\prime},w)$ verifies
$H[U^{<i}]\approx_{\delta_{j(i)}}G[U^{<i}]$ because of 2. As we have $c\leq
1/30$, $\phi<b$, $b\leq c$, $\alpha\leq\frac{1}{2b}$, Lemma 5.3 ensures that
the pair $(R_{i},\nu_{R_{i}})$ is a $(\phi_{j(i)},(1+\frac{1}{\log
n})\alpha,(1+c)\lambda,c)$-BSCW of $G[U^{<i}]^{\circ}$ for all $i\in[q]$ (see
6.3). From the description of the algorithm we also know that $\nu_{R_{i}}$
must also not satisfy condition (11), as otherwise Algorithm 4 would have
returned, so
$\nu_{R_{i}}<\frac{1}{C\lambda}\operatorname{vol}_{U}^{\circ\,w}(U)$ for all
$i\in[q]$. For each $i\in[q]$, we now use Lemma 6.6 with parameters
$\psi=\phi_{j(i)}$, $\alpha^{\prime}=(1+\frac{1}{\log n})\alpha$,
$\lambda^{\prime}=(1+c)\lambda$, $\rho=\frac{1}{C\lambda}$, $\tau=1$, and
$X=U$. These parameters verify the requirement for applying Lemma 6.6 to
$(R_{i},\nu_{R_{i}})$ in $G[U^{<i}]$: $c\leq 1/30\leq 1/4$,
$H[U^{<i}]\approx_{c}G[U^{<i}]$ (from 2 and $\delta_{j(i)}\leq c$),
$\psi=\phi_{j(i)}\leq\phi$, $\alpha^{\prime},\lambda^{\prime}\geq 1$,
$\rho,\tau\leq 1$, and $(R_{i},\nu_{R_{i}})$ is a
$(\phi_{j(i)},(1+\frac{1}{\log n})\alpha,(1+c)\lambda,c)$-BSCW of
$G[U^{<i}]^{\circ}$. Then, for all $i\in[q]$ Lemma 6.6 gives

$\operatorname{vol}_{U^{<i}}^{\circ}(R_{i})<\frac{2}{C\lambda}\operatorname{vol}_{U}^{\circ}(U)<\frac{1}{5}\operatorname{vol}_{U}^{\circ}(U)\,,$
(6.16)

since $C\geq 11$. Furthermore, because every $(R_{i},\nu_{R_{i}})$ is a
$(\phi_{j(i)},(1+\frac{1}{\log n})\alpha,(1+c)\lambda,c)$-BSCW of
$G[U^{<i}]^{\circ}$, we have by Definition 5.1

$\Phi_{U^{<i}}^{\circ}(R_{i})<\left(1+\frac{1}{\log
n}\right)\alpha\phi_{j(i)}=\left(1+\frac{1}{\log
n}\right)\alpha\frac{\phi}{\left(\left(1+\frac{1}{\log
n}\right)\alpha\right)^{j(i)}}\leq\phi\,,$ (6.17)

since $j(i)\geq 1$. The bounds in (6.16) and (6.17) give part (2). ∎

Finally, we argue that Algorithm 4 goes through few inner loop iterations
within each outer loop iteration. The idea for this is that we can upper bound
the total volume trimmed in line (13), but we can also lower bound the volume
of each individual cut.

######  Lemma 6.9 (Algorithm 4 does few inner loop iterations).

Let $b,\phi,c\in(0,1)$ such that $c\leq 1/30$ is a constant, $\phi<b$ and
$b\leq c$. Also let $C\geq 31$ be a constant, let
$\textsc{BalSparseCut}_{\alpha,\lambda}$ be an $(\alpha,\lambda)$-BSCA where
$\alpha\leq\frac{1}{2b}$ and $\lambda\leq\frac{c}{2b}$, and let $k$ be an
integer such that $k\geq\log\frac{n^{2}}{\phi}/\log\frac{c}{\lambda\cdot b}$.
If 1 and 2 hold, then Algorithm 4 goes through at most $1/{b}$ inner loop
iterations within each outer loop iteration.

###### Proof.

Let $U$ be the input cluster of Algorithm 4. Fix hereafter an outer loop
iteration $j=1,\dots,k+1$, and let $A$ be the value of the corresponding
variable of the algorithm at the beginning of the $j$-th outer loop iteration.
Because line (13) of Algorithm 4 removes a non-empty cut from $A$ at every
inner loop iteration, there are finitely many iterations. Denote then by $t$
the number of inner loop iterations for outer loop iteration $j$. Then, for
every inner loop iteration $h\in[t]$ define $A^{<h}$ to be the value of
variable $A$ at the beginning of inner loop iteration $h$.

Since 2 holds, we also know that to every inner loop iteration $h\in[t]$
corresponds a graph $H=(V,E^{\prime},w)$ from line (8) which satisfies
$H[A^{<h}]\approx_{\delta_{j}}G[A^{<h}]$. As we have $c\leq 1/30$, $\phi<b$,
$b\leq c$, $\alpha\leq\frac{1}{2b}$, and
$H[A^{<h}]\approx_{\delta_{j}}G[A^{<h}]$, Lemma 5.3 ensures that calling
$\textsc{BalSparseCut}_{\alpha,\lambda}(H[A^{<h}]^{\circ},(1+\frac{1}{2\log
n})\cdot\phi_{j})$ gives a $(\phi_{j},(1+\frac{1}{\log
n})\alpha,(1+c)\lambda,c)$-BSCW of $G[A^{<h}]^{\circ}$ in line (9) of
Algorithm 4 (see 6.3). Moreover, from the description of the algorithm, it
must be the case that the BSCW obtained is of the form $(R_{h},\nu_{h})$ for
all $h\in[t-1]$, where $\emptyset\neq R_{h}\subsetneq A^{<h}$ and
$\nu_{h}\in\mathbb{R}_{>0}$. One can then see that for every $h\in[t]$ we have
$A^{<h}=A\setminus(\cup_{z=1}^{h-1}R_{z})$, and because of conditions (11) and
(12) we have that for every $h\in[t-1]$ the following holds:

$\frac{1}{C\lambda}\left(\operatorname{vol}_{U}^{\circ\,w}(U)\right)^{1-(j-1)/k}\leq\nu_{h}<\frac{1}{C\lambda}\operatorname{vol}_{U}^{\circ\,w}(U)\,.$

We now want to translate the above bounds to
$\operatorname{vol}_{A^{<h}}^{\circ}(R_{h})$ using Lemma 6.6. To do so, note
that $H[A^{<h}]\approx_{\delta_{j}}G[A^{<h}]$ in particular implies
$H[A^{<h}]\approx_{c}G[A^{<h}]$ (since we have defined
$\delta_{j}=c^{2}b_{j}/\log n\leq c$), and as discussed before we know that

$(R_{h},\nu_{h})$ is a $\left(\phi_{j},\left(1+\frac{1}{\log
n}\right)\alpha,(1+c)\lambda,c\right)$-BSCW of $G[A^{<h}]^{\circ}$ (6.18)

Let us then set $\psi=\phi_{j}$, $\alpha^{\prime}=(1+\frac{1}{\log n})\alpha$,
$\lambda^{\prime}=(1+c)\lambda$, $\rho=\frac{1}{C\lambda}$, $\tau$ being
either $1-(j-1)/k$ (for the lower bound) or $1$ (for the upper bound), and
$X=U$. These parameters verify the conditions for applying Lemma 6.6 to
$(R_{h},\nu_{h})$ on $G[A^{<h}]^{\circ}$: $c\leq 1/30\leq 1/4$,
$\psi=\phi_{j}\leq\phi$, $\alpha^{\prime},\lambda^{\prime}\geq 1$, $\rho\leq
1$, both values of $\tau$ are bounded by $1$ (this is because $j\leq k+1$),
$H[A^{<h}]\approx_{c}G[A^{<h}]$ (since from 2 we have
$H[A^{<h}]\approx_{\delta_{j}}G[A^{<h}]$), and $(R_{h},\nu_{h})$ is a
$(\phi_{j},(1+\frac{1}{\log n})\alpha,(1+c)\lambda,c)$-BSCW of
$G[A^{<h}]^{\circ}$ (see (6.18)). Then Lemma 6.6 gives

$\frac{1}{2C\lambda}\left(\operatorname{vol}_{U}^{\circ}(U)\right)^{1-(j-1)/k}\leq\operatorname{vol}_{A^{<h}}^{\circ}(R_{h})<\frac{2}{C\lambda}\operatorname{vol}_{U}^{\circ}(U)\,,$
(6.19)

where the lower bound is obtained with $\tau=1-(j-1)/k$ and the upper bound
with $\tau=1$. The application of Lemma 6.6 with $\tau=1$ also gives that for
every cut $\emptyset\neq S\subsetneq A^{<h}$ with
$\Phi_{A^{<h}}^{\circ}(S)<\phi_{j}$ and
$\operatorname{vol}_{A^{<h}}^{\circ}(S)\leq\operatorname{vol}_{A^{<h}}^{\circ}(A^{<h}\setminus
S)$ one has

$\operatorname{vol}_{A^{<h}}^{\circ}(S)<2\lambda^{\prime}\rho\cdot\operatorname{vol}_{U}^{\circ}(U)=\frac{2(1+c)\lambda}{C\lambda}\operatorname{vol}_{U}^{\circ}(U)\leq\frac{3}{C}\cdot\operatorname{vol}_{U}^{\circ}(U)\,.$
(6.20)

We consider now the case of $j=1$ and $2\leq j\leq k+1$ separately.

##### Case $j=1$.

In this case $A$ is identical to the input cluster $U$. We then want to apply
Lemma 6.5 with $\delta=1$ and
$\theta=\frac{3}{C}\operatorname{vol}_{U}^{\circ}(U)$ to the sequence of cuts
$R_{1},R_{2},\dots,R_{t-1}$ in the cluster $U$. Let for convenience
$U^{i}=U\setminus(\cup_{z=1}^{i-1}R_{z})$ for all $i\in[t]$.

First note that this value of $\theta$ meets the requirement of Lemma 6.5 that
$\theta<\frac{1}{5}\operatorname{vol}_{U}^{\circ}(U)$, since $C\geq 16$.
Secondly, our set of assumptions matches that of Lemma 6.8, so we get that for
all $\emptyset\neq S\subsetneq U$ with $\Phi_{U}^{\circ}(S)<\phi$,
$\operatorname{vol}_{U}^{\circ}(S)\leq\operatorname{vol}_{U}^{\circ}(U\setminus
S)$, one has
$\operatorname{vol}_{U}^{\circ}(S)<\frac{3}{C}\operatorname{vol}_{U}^{\circ}(U)$,
and for all $i\in[q]$ one has $\Phi_{U^{<i}}^{\circ}(R_{i})<\phi$ and
$\operatorname{vol}_{U^{<i}}^{\circ}(R_{i})<\frac{1}{5}\operatorname{vol}_{U}^{\circ}(U)$.
These facts match preconditions (1) and (2) of Lemma 6.5 for $\delta$ and
$\theta$ as we set them above.

Part (1) of Lemma 6.5 then upper-bounds the total volume of the sequence as

$\operatorname{vol}_{U}^{\circ}(\cup_{h=1}^{t-1}R_{h})<\frac{3}{C}\operatorname{vol}_{U}^{\circ}(U)\,.$
(6.21)

Since the lower bound of (6.18) with $j=1$ means that
$\operatorname{vol}_{U^{<h}}^{\circ}(R_{h})\geq\frac{1}{2C\lambda}\operatorname{vol}_{U}^{\circ}(U)$
for all $h\in[t-1]$, using part (2) of Lemma 6.5 with
$\theta^{\operatorname*{low}}=\frac{1}{2C\lambda}\operatorname{vol}_{U}^{\circ}(U)$
we further get

$\operatorname{vol}_{U}^{\circ}(R_{h})\geq\frac{1}{2C\lambda}\operatorname{vol}_{U}^{\circ}(U)-b\cdot\frac{3}{C}\operatorname{vol}_{U}^{\circ}(U)\geq\frac{1}{3C\lambda}\operatorname{vol}_{U}^{\circ}(U)\quad\text{
for all $h\in[t-1]$}\,,$ (6.22)

since $\lambda\leq\frac{1}{18b}$. Therefore, taking the ratio of the
cumulative upper bound in (6.21) and the individual lower bounds from (6.22),
we conclude that $t-1$ cannot exceed

$\frac{\operatorname{vol}_{U}^{\circ}(\cup_{h=1}^{t-1}R_{h})}{\min_{h\in[t-1]}\operatorname{vol}_{U}^{\circ}(R_{h})}\leq\frac{\frac{3}{C}\operatorname{vol}_{U}^{\circ}(U)}{\frac{1}{3C\lambda}\operatorname{vol}_{U}^{\circ}(U)}\leq
9\lambda\,.$

Thus, the number of inner loop iterations for $j=1$ is at most
$9\lambda+1\leq\frac{1}{2b}+1\leq 1/b$.

##### Case $2\leq j\leq k+1$.

The approach is analogous to the first iteration, except that we use the
bounds from Lemma 6.5 on the sequence $R_{1},\dots,R_{t-1}$ in the cluster $A$
(for $j=1$ we applied the lemma to the cluster $U$). We remark that, in this
case, $A$ can also be seen as the value of the corresponding variable of
Algorithm 4 at the very end of outer loop iteration $j-1$.

Consider the call
$\textsc{BalSparseCut}_{\alpha,\lambda}(H[A]^{\circ},(1+\frac{1}{2\log
n})\cdot\phi_{j-1})$ to $\textsc{BalSparseCut}_{\alpha,\lambda}$ in the last
inner loop iteration within outer loop iteration $j-1$, where
$H=(V,E^{\prime},w)$ is accordingly the graph obtained from line (8) at the
last inner loop iteration within outer loop iteration ${j-1}$. Since 2 holds,
we know that the graph $H$ satisfies $H[A]\approx_{\delta_{j-1}}G[A]$. As we
have $c\leq 1/30$, $\phi<b$, $b\leq c$, $\alpha\leq\frac{1}{2b}$, and
$H[A]\approx_{\delta_{j-1}}G[A]$, Lemma 5.3 ensures that the call
$\textsc{BalSparseCut}_{\alpha,\lambda}(H[A]^{\circ},(1+\frac{1}{2\log
n})\cdot\phi_{j-1})$ gives a $(\phi_{j-1},(1+\frac{1}{\log
n})\alpha,(1+c)\lambda,c)$-BSCW $\omega$ of $G[A]^{\circ}$ (see 6.3). On the
other hand, from the description of the algorithm we know that iteration $j$
starts only if this $\omega$ is of the form $(R,\nu)$ with
$\nu<\frac{1}{C\lambda}(\operatorname{vol}_{U}^{\circ\,w}(U))^{1-(j-2)/k}$
(due to condition (12)). We now use Lemma 6.6 with parameters
$\psi=\phi_{j-1}$, $\alpha^{\prime}=(1+\frac{1}{\log n})\alpha$,
$\lambda^{\prime}=(1+c)\lambda$, $\rho=\frac{1}{C\lambda}$, $\tau=1-(j-2)/k$,
and $X=U$. These parameters verify the requirement of Lemma 6.6 since we have
$c\leq 1/30\leq 1/4$, $H[A]\approx_{c}G[A]$ (from 2 and $\delta_{j-1}\leq c$),
$\psi=\phi_{j-1}\leq\phi$, $\alpha^{\prime},\lambda^{\prime}\geq 1$,
$\rho,\tau\leq 1$, and $(R,\nu)$ is a $(\phi_{j-1},(1+\frac{1}{\log
n})\alpha,(1+c),c\lambda)$-BSCW of $G[A]^{\circ}$. Then we get that for every
cut $\emptyset\neq S\subsetneq A$ with $\Phi_{A}^{\circ}(S)<\phi_{j-1}$ and
$\operatorname{vol}_{A}^{\circ}(S)\leq\operatorname{vol}_{A}^{\circ}(A\setminus
S)$ one has

$\operatorname{vol}_{A}^{\circ}(S)<2\lambda^{\prime}\rho\left(\operatorname{vol}_{U}^{\circ}(U)\right)^{\tau}=\frac{2(1+c)\lambda}{C\lambda}\left(\operatorname{vol}_{U}^{\circ}(U)\right)^{1-(j-2)/k}\leq\frac{3}{C}\cdot\left(\operatorname{vol}_{U}^{\circ}(U)\right)^{1-(j-2)/k}\,.$
(6.23)

This is still not enough to apply Lemma 6.5 to cluster $A$: the bound in
(6.19) bounds the volumes of nested cuts $R_{h}$ in $A^{<h}$ by
$\frac{2}{C\lambda}\operatorname{vol}_{U}^{\circ}(U)$, but applying Lemma 6.5
demands an upper bound of $\frac{1}{5}\operatorname{vol}_{A}^{\circ}(A)$ on
the volumes of cuts $R_{h}$ in $A^{<h}$. Hence, we first show the volume of
$U$ to be not much larger than that of $A$.

######  Claim 6.10.

We have $\operatorname{vol}_{U}^{\circ}(U)\leq
2\operatorname{vol}_{A}^{\circ}(A)$.

###### Proof.

If $A=U$ the statement is trivial. Otherwise, we know there must have been a
sequence of nested cuts $S_{1},\dots,S_{r}\subseteq U$ that Algorithm 4
trimmed off from $U$ in line (13) so that $A=U\setminus(\cup_{i\in[r]}S_{i})$.
We then want to apply Lemma 6.5 to the sequence of cuts
$S_{1},S_{2},\dots,S_{r}$ in the cluster $U$ with $\delta=1$ and
$\theta=\frac{3}{C}\operatorname{vol}_{U}^{\circ}(U)$. Let for convenience
$U^{<i}=U\setminus(\cup_{z=1}^{i-1}S_{z})$ for all $i\in[r+1]$.

First note that this value of $\theta$ meets the requirement of Lemma 6.5 that
$\theta<\frac{1}{5}\operatorname{vol}_{U}^{\circ}(U)$, since $C\geq 16$.
Secondly, our set of assumptions matches that of Lemma 6.8, so we get that for
all $\emptyset\neq S\subsetneq U$ with $\Phi_{U}^{\circ}(S)<\phi$,
$\operatorname{vol}_{U}^{\circ}(S)\leq\operatorname{vol}_{U}^{\circ}(U\setminus
S)$, one has
$\operatorname{vol}_{U}^{\circ}(S)<\frac{3}{C}\operatorname{vol}_{U}^{\circ}(U)$,
and for all $i\in[r]$ one has $\Phi_{U^{<i}}^{\circ}(S_{i})<\phi$ and
$\operatorname{vol}_{U^{<i}}^{\circ}(S_{i})<\frac{1}{5}\operatorname{vol}_{U}^{\circ}(U)$
(the latter follows because part (2) of Lemma 6.8 bounds the sparsity and
volume of every cut in the entire sequence of cuts trimmed by the algorithm,
and $S_{1},\dots,S_{r}$ is a prefix of the entire sequence). These facts match
preconditions (1) and (2) of Lemma 6.5 for $\delta$ and $\theta$ as set above.
Part (1) of Lemma 6.5 then upper-bounds the total volume of the sequence as

$\operatorname{vol}_{U}^{\circ}(\cup_{i=1}^{r}S_{i})<\frac{3}{C}\operatorname{vol}_{U}^{\circ}(U)\,.$
(6.24)

To conclude it is sufficient to notice

$\displaystyle\operatorname{vol}_{U}^{\circ}(U)$
$\displaystyle=\operatorname{vol}_{U}^{\circ}(A)+\operatorname{vol}_{U}^{\circ}(U\setminus
A)$
$\displaystyle=\operatorname{vol}_{U}^{\circ}(A)+\operatorname{vol}_{U}^{\circ}(\cup_{i=1}^{r}S_{i})$
$\operatorname{vol}_{A}^{\circ}(A)$ cannot have less self-loops than
$\operatorname{vol}_{U}^{\circ}(A)$
$\displaystyle\leq\operatorname{vol}_{A}^{\circ}(A)+\operatorname{vol}_{U}^{\circ}(\cup_{i=1}^{r}S_{i})$
by (6.24)
$\displaystyle<\operatorname{vol}_{A}^{\circ}(A)+\frac{3}{C}\operatorname{vol}_{U}^{\circ}(U)\,,$

and the claim follows since $C\geq 6$. ∎

By 6.10 and (6.19), we have that for every $h\in[t-1]$

$\operatorname{vol}_{A^{<h}}^{\circ}(R_{h})<\frac{2}{C\lambda}\operatorname{vol}_{U}^{\circ}(U)\leq\frac{4}{C\lambda}\operatorname{vol}_{A}^{\circ}(A)<\frac{1}{5}\operatorname{vol}_{A}^{\circ}(A)\,,$
(6.25)

since $C\geq 21$. Furthermore, because every $(R_{h},\nu_{h})$ is a
$(\phi_{j},(1+\frac{1}{\log n})\alpha,(1+c)\lambda,c)$-BSCW of
$G[A^{<h}]^{\circ}$, we have

$\Phi_{A^{<h}}^{\circ}(R_{h})<\left(1+\frac{1}{\log
n}\right)\alpha\phi_{j}=\left(1+\frac{1}{\log
n}\right)\alpha\frac{\phi}{\left(\left(1+\frac{1}{\log
n}\right)\alpha\right)^{j}}\leq\phi_{j-1}\,.$ (6.26)

We are now in shape to apply Lemma 6.5 to the sequence of cuts
$R_{1},R_{2},\dots,R_{t+1}$ in the cluster $A$. Specifically, we do this with
$\delta=\phi_{j-1}/\phi$ and
$\theta=\frac{3}{C}(\operatorname{vol}_{U}^{\circ}(U))^{1-(j-2)/k}$. First
observe that $\delta\leq 1$ (by definition of $\phi_{j-1}$) and
$\theta\leq\frac{3}{C}\operatorname{vol}_{U}^{\circ}(U)\leq\frac{1}{5}\operatorname{vol}_{A}^{\circ}(A)$
(again by 6.10 and $C\geq 31$), as demanded by Lemma 6.5. For these
parameters, one can see that precondition (2) is given by (6.25) and (6.26).
Precondition (1) is instead given by (6.23). Part (1) of Lemma 6.5 then upper-
bounds the total volume of the sequence as

$\operatorname{vol}_{A}^{\circ}(\cup_{h=1}^{t-1}R_{h})<\theta=\frac{3}{C}\left(\operatorname{vol}_{U}^{\circ}(U)\right)^{1-(j-2)/k}\,.$
(6.27)

We are left with lower bounding the volume of each individual cut. We do this
with part (2) of Lemma 6.5 with
$\theta^{\operatorname*{low}}=\frac{1}{2C\lambda}(\operatorname{vol}_{U}^{\circ}(U))^{1-(j-1)/k}$,
which meets the requirement that
$\operatorname{vol}_{A}^{\circ}(R_{h})\geq\theta^{\operatorname*{low}}$ thanks
to the bound in (6.19). Part (2) of Lemma 6.5 then gives that for all
$h\in[t-1]$

$\displaystyle\operatorname{vol}_{A}^{\circ}(R_{h})\geq\theta^{\operatorname*{low}}-b\cdot\theta=\frac{1}{2C\lambda}\left(\operatorname{vol}_{U}^{\circ}(U)\right)^{1-(j-1)/k}-b\cdot\frac{3}{C}\left(\operatorname{vol}_{U}^{\circ}(U)\right)^{1-(j-2)/k}\,.$
(6.28)

Therefore, taking the ratio of the upper bound on the total volume from (6.27)
and the lower bound on the volume of each individual cut from (6.28), we
conclude that $t-1$ is at most

$\displaystyle\frac{\operatorname{vol}_{A}^{\circ}(\cup_{h=1}^{t-1}R_{h})}{\min_{h\in[t-1]}\operatorname{vol}_{A}^{\circ}(R_{h})}$
$\displaystyle\leq\frac{\frac{3}{C}\left(\operatorname{vol}_{U}^{\circ}(U)\right)^{1-(j-2)/k}}{\frac{1}{2C\lambda}\left(\operatorname{vol}_{U}^{\circ}(U)\right)^{1-(j-1)/k}-b\cdot\frac{3}{C}\left(\operatorname{vol}_{U}^{\circ}(U)\right)^{1-(j-2)/k}}$
$\displaystyle=\frac{\frac{3}{C}\left(\operatorname{vol}_{U}^{\circ}(U)\right)^{1/k}}{\frac{1}{2C\lambda}-b\cdot\frac{3}{C}\left(\operatorname{vol}_{U}^{\circ}(U)\right)^{1/k}}\,.$

Next, we observe that
$\operatorname{vol}_{U}^{\circ}(U)\leq\operatorname{vol}(V)\cdot
b/\phi\leq\operatorname{vol}(V)/{\phi}\leq n^{2}/\phi$ (since in the worst
case we over-count every edge in $G$ as a self-loop in $G[U]^{\circ}$ and at
most $b/\phi$ times). Then, using that
$k\geq\log(\frac{n^{2}}{\phi})/\log(\frac{c}{\lambda\cdot b})$, it holds that
$\left(\operatorname{vol}_{U}^{\circ}(U)\right)^{1/k}\leq\frac{c}{\lambda\cdot
b}$. Now we can upper-bound the above as

$\displaystyle\frac{\frac{3}{C}\left(\operatorname{vol}_{U}^{\circ}(U)\right)^{1/k}}{\frac{1}{2C\lambda}-b\cdot\frac{3}{C}\left(\operatorname{vol}_{U}^{\circ}(U)\right)^{1/k}}\leq\frac{\frac{3}{C}\left(\operatorname{vol}_{U}^{\circ}(U)\right)^{1/k}}{\frac{1}{2C\lambda}-b\cdot\frac{3}{C}\frac{c}{\lambda\cdot
b}}\leq\frac{\frac{3}{C}\cdot\left(\frac{n^{2}}{\phi}\right)^{1/k}}{\frac{1}{5C\lambda}}\leq\frac{\frac{3}{C}\cdot\frac{c}{\lambda\cdot
b}}{\frac{1}{5C\lambda}}=15\frac{c}{b}\,,$

since $c\leq\frac{1}{30}$. Hence, the number of inner loop iterations for
$2\leq j\leq k+1$ is at most $\frac{15c}{b}+1\leq\frac{1}{b}$. ∎

####  6.1.4 Bounding the recursion depth

From the description of the algorithms one can see that we recurse on both
sides of a cut (in line (11) of Algorithm 3) only when the conditions (7) in
Algorithm 3 and (11) in Algorithm 4 suggest that the cut is balanced, so as to
maintain the recursion depth small. When instead Algorithm 3 recurses on one
side only, in line (10), we can use the properties of nested cuts to upper
bound the volume of the recursed side. To control the number of self-loops
that we add after each recursion, we also want to ensure that we recurse on
sparse cuts only.

######  Lemma 6.11 (Algorithm 3 recurses on balanced sparse cuts).

Let $b,\phi,c\in(0,1)$ such that $c\leq 1/30$ is a constant, $\phi<b$, $b\leq
c$. Also let $C\geq 16$ be a constant, and let
$\textsc{BalSparseCut}_{\alpha,\lambda}$ be an $(\alpha,\lambda)$-BSCA where
$\alpha\leq\frac{1}{2b}$ and $\lambda\leq\frac{1}{18b}$. If 1 and 2 hold,
whenever Algorithm 3 with input cluster $U\subseteq V$ makes a recursive call,
the recursion is on a cluster $\emptyset\neq X\subsetneq U$ such that

$\Phi_{U}^{\circ}(X)<(3C\lambda+2\alpha)\cdot\phi\quad\text{ and
}\quad\operatorname{vol}_{U}^{\circ}(X)\leq\left(1-\frac{1}{3C\lambda}\right)\operatorname{vol}_{U}^{\circ}(U)\,.$

###### Proof.

There are three lines where a recursive call can happen: (7), (10), (11). We
analyse them separately.

##### Recursion in line (7).

Let $H=(V,E^{\prime},w)$ be the graph returned in line (4) of Algorithm 3.
Since the algorithm recurses in line (7), the call
$\textsc{BalSparseCut}_{\alpha,\lambda}(H[U]^{\circ},(1+\frac{1}{2\log
n})\cdot\phi)$ of line (5) must have returned a BSCW of the form $(R,\nu)$
such that

$\nu\geq\frac{1}{C\lambda}\operatorname{vol}_{U}^{\circ\,w}(U)\,.$ (6.29)

As we have $c\leq 1/30$, $\phi<b$, $b\leq c$, $\alpha\leq\frac{1}{2b}$, and
$H[U]\approx_{\delta}G[U]$ (because of 1), Lemma 5.3 gives that $(R,\nu)$ is a
$(\phi,(1+\frac{1}{\log n})\alpha,(1+c)\lambda,c)$-BSCW of $G[U]^{\circ}$. By
Definition 5.1, this means

$\Phi_{U}^{\circ}(R)<\left(1+\frac{1}{\log n}\right)\alpha\cdot\phi\leq
2\alpha\cdot\phi\,.$

We now want to use Lemma 6.6 with $\psi=\phi$,
$\alpha^{\prime}=(1+\frac{1}{\log n})\alpha$, $\lambda^{\prime}=(1+c)\lambda$,
$\rho=\frac{1}{C\lambda}$, $\tau~{}=~{}1$, and $X=U$. These parameters verify
the conditions for applying Lemma 6.6 to $(R,\nu)$ on $G[U]^{\circ}$: $c\leq
1/30\leq 1/4$, $\psi\leq\phi$, $\alpha^{\prime},\lambda^{\prime}\geq 1$,
$\rho\leq 1$, $\tau\leq 1$, $H[U]\approx_{c}G[U]$ (since
$H[U]\approx_{\delta}G[U]$ and $\delta\leq c$), and $(R,\nu)$ is a
$(\phi,(1+\frac{1}{\log n},c)\alpha,(1+c)\lambda)$-BSCW of $G[U]^{\circ}$.
Then Lemma 6.6 with (6.29) gives

$\operatorname{vol}_{U}^{\circ}(R)\geq\frac{\rho}{2}(\operatorname{vol}_{U}^{\circ}(U))^{\tau}=\frac{1}{2C\lambda}\operatorname{vol}_{U}^{\circ}(U)\,,$

which we can use to upper bound the volume of $U\setminus R$:

$\operatorname{vol}_{U}^{\circ}(U\setminus
R)=\operatorname{vol}_{U}^{\circ}(U)-\operatorname{vol}_{U}^{\circ}(R)\leq\left(1-\frac{1}{2C\lambda}\right)\operatorname{vol}_{U}^{\circ}(U).$

Finally, by property (2c) of BSCW applied to $R$,
$\operatorname{vol}_{U}^{\circ}(R)\leq(1+c)\operatorname{vol}_{U}^{\circ}(U\setminus
R)$. Because $c\leq 1/30\leq 1/2$ and $C\geq 2$,

$\operatorname{vol}_{U}^{\circ}(R)\leq\frac{1+c}{2}\operatorname{vol}_{U}^{\circ}(U)\leq\left(1-\frac{1}{2C\lambda}\right)\operatorname{vol}_{U}^{\circ}(U).$

Since in this case the algorithm recurses on $R$ and $U\setminus R$, we have
the claim.

##### Recursion in lines (10) and (11).

These cases can only happen if Algorithm 3 resorts to Algorithm 4. Let then
$R_{1},\dots,R_{q}\subseteq U$ be the sequence of cuts trimmed off by
Algorithm 4 in line (9). We then want to apply Lemma 6.5 to the sequence of
cuts $R_{1},R_{2},\dots,R_{q}$ in the cluster $U$ with $\delta=1$ and
$\theta=\frac{3}{C}\operatorname{vol}_{U}^{\circ}(U)$. Let for convenience
$U^{<i}=U\setminus(\cup_{z=1}^{i-1}R_{z})$ for all $i\in[q+1]$.

First note that this value of $\theta$ meets the requirement of Lemma 6.5 that
$\theta<\frac{1}{5}\operatorname{vol}_{U}^{\circ}(U)$, since $C\geq 16$.
Secondly, our set of assumptions matches that of Lemma 6.8, so we get that for
all $\emptyset\neq S\subsetneq U$ with $\Phi_{U}^{\circ}(S)<\phi$,
$\operatorname{vol}_{U}^{\circ}(S)\leq\operatorname{vol}_{U}^{\circ}(U\setminus
S)$, one has
$\operatorname{vol}_{U}^{\circ}(S)<\frac{3}{C}\operatorname{vol}_{U}^{\circ}(U)$,
and for all $i\in[q]$ one has $\Phi_{U^{<i}}^{\circ}(R_{i})<\phi$ and
$\operatorname{vol}_{U^{<i}}^{\circ}(R_{i})<\frac{1}{5}\operatorname{vol}_{U}^{\circ}(U)$.
These facts match preconditions (1) and (2) of Lemma 6.5 for $\delta$ and
$\theta$ as we set them above.

  * •

_Line ( 10)_. Part (1) of Lemma 6.5 then upper-bounds the total sparsity and
volume of the sequence as

$\Phi_{U}^{\circ}(\cup_{z=1}^{q}R_{z})<\phi\quad\text{and}\quad\operatorname{vol}_{U}^{\circ}(\cup_{z=1}^{q}R_{z})<\frac{3}{C}\operatorname{vol}_{U}^{\circ}(U)\,.$
(6.30)

For Algorithm 3 to recurse in line (10), it must be the case that Algorithm 4
returned a pair $(S,\top)$ in line (9) (see condition (9)). Looking into
Algorithm 4, one can then see that if it returns a pair of the form
$(S,\top)$, it must be the case that $S$ is the value of variable $A$ at the
end of the algorithm, i.e. $S=A=U\setminus(\cup_{z\in[q]}R_{z})$. In line
(10), the recursive call is $\textsc{Decompose}(U\setminus S,\ell+1)$, so we
recurse on $U\setminus S=\cup_{z\in[q]}R_{z}$. From (6.30) we then have the
claim since $C\geq 6$.

  * •

_Line ( 11)_. The difference from the previous case is that for Algorithm 3 to
recurse in line (11), it must be the case that Algorithm 4 returned a pair
$(S,\bot)$ in line (9) (see condition (9)), and in particular this implies
that Algorithm 4 returned in line (11).

Let $p$ be the outer loop iteration where Algorithm 4 returns, and let
$H=(V,E^{\prime},w)$ be the graph from line (8) in the last inner loop
iteration of outer loop iteration $p$ (i.e. the inner loop iteration where it
returns). Since in such iteration we must have that variable $A$ actually
equals $U^{<q+1}$, let $\omega$ be the result of
$\textsc{BalSparseCut}_{\alpha,\lambda}(H[U^{q+1}]^{\circ},(1+\frac{1}{2\log
n})\phi_{p})$ in that same iteration. As we have $c\leq 1/30$, $\phi<b$,
$b\leq c$, $\alpha\leq\frac{1}{2b}$, and
$H[U^{<q+1}]\approx_{\delta_{p}}G[U^{<q+1}]$ (from 2), Lemma 5.3 ensures that
$\omega$ is a $(\phi_{p},(1+\frac{1}{\log n})\alpha,(1+c)\lambda,c)$-BSCW of
$G[U^{<q+1}]^{\circ}$ (see 6.3). Moreover, since Algorithm 4 returned in line
(11), it must be the case that $\omega$ is of the form $(S,\nu)$, where $S$ is
the cut returned from Algorithm 4 to Algorithm 3 in the pair $(S,\bot)$. From
the description of the algorithm it must also be the case that

$\nu\geq\frac{1}{C\lambda}\operatorname{vol}_{U}^{\circ\,w}(U)\,.$ (6.31)

As we have $c\leq 1/30\leq 1/4$, $\phi<b$, $b\leq c$,
$\alpha\leq\frac{1}{2b}$, and $H[U^{<q+1}]\approx_{c}G[U^{<q+1}]$ (from 2 and
$\delta_{p}\leq c$), the fact that $(S,\nu)$ is a $(\phi_{p},(1+\frac{1}{\log
n})\alpha,(1+c)\lambda,c)$-BSCW of $G[U^{<q+1}]^{\circ}$, and the bound
(6.31), Lemma 6.6 gives

$\operatorname{vol}_{U^{<q+1}}^{\circ}(S)\geq\frac{1}{2C\lambda}\operatorname{vol}_{U}^{\circ}(U)\,.$
(6.32)

Since $(S,\nu)$ is a $(\phi_{p},(1+\frac{1}{\log
n})\alpha,(1+c)\lambda,c)$-BSCW of $G[U^{<q+1}]^{\circ}$, by Definition 5.1 we
also know

$\operatorname{vol}_{U^{<q+1}}^{\circ}(S)\leq(1+c)\operatorname{vol}_{U^{<q+1}}^{\circ}(U\setminus
S)\,,$

so

$\operatorname{vol}_{U^{<q+1}}^{\circ}(S)\leq\frac{5}{9}\operatorname{vol}_{U^{<q+1}}^{\circ}(U)\,,$
(6.33)

since $c\leq 1/30\leq 1/10$. Now, setting $R=S$ and
$\theta^{\operatorname*{low}}=\frac{1}{2C\lambda}\operatorname{vol}_{U}^{\circ}(U)$,
the bounds in (6.32) and (6.33), together with the fact that
$\theta^{\operatorname*{low}}\leq\frac{4}{9}\operatorname{vol}_{U}^{\circ}(U)$
(since $C\geq 2$), allow us to apply part (3) of Lemma 6.5. This gives

$\displaystyle\Phi_{U}^{\circ}(S)$
$\displaystyle<\phi\frac{\operatorname{vol}_{U}^{\circ}(U)}{\theta^{\operatorname*{low}}-b\cdot\theta}$
(6.34)
$\displaystyle=\phi\cdot\frac{\operatorname{vol}_{U}^{\circ}(U)}{\frac{1}{2C\lambda}\operatorname{vol}_{U}^{\circ}(U)-b\cdot\frac{3}{C}\operatorname{vol}_{U}^{\circ}(U)}$
(6.35) since $b\leq\frac{1}{18\lambda}$ $\displaystyle\leq
3C\lambda\cdot\phi\,,$ (6.36)

and

$\frac{1}{3C\lambda}\operatorname{vol}_{U}^{\circ}(U)\leq\theta^{\operatorname*{low}}-b\cdot\theta\leq\operatorname{vol}_{U}^{\circ}(S)\leq\frac{5}{9}\operatorname{vol}_{U}^{\circ}(U)\,.$
(6.37)

We can now conclude: since the result of Algorithm 4 is $(S,\bot)$, Algorithm
3 recurses on both $S$ and $U\setminus S$ in line (11). Let
$X\in\\{S,U\setminus S\\}$. Then from (6.36) we have that
$\Phi_{U}^{\circ}(X)<3C\lambda\cdot\phi$, and from (6.37) we have that
$\operatorname{vol}_{U}^{\circ}(X)\leq(1-\frac{1}{3C\lambda})\operatorname{vol}_{U}^{\circ}(U)$
since $C\geq 2$.

∎

We now upper-bound the recursion depth of the algorithm, using the above
lemma.

######  Lemma 6.12 (Algorithm 3 has small recursion depth).

Let $b,\phi,c\in(0,1)$ such that $c\leq 1/30$ is a constant, $\phi<b$, $b\leq
c$. Also let $C\geq 16$ be a constant, and let
$\textsc{BalSparseCut}_{\alpha,\lambda}$ be an $(\alpha,\lambda)$-BSCA where
$\alpha\leq\frac{1}{144C\lambda b}$,
$\lambda\leq\min\\{\frac{1}{18b},\,\frac{1}{15C\sqrt{b}}\\}$. If 1 and 2 hold,
then the recursion depth of $\textsc{Decompose}(V,0)$ (i.e. Algorithm 3) is at
most $9C\lambda\cdot\log n$.

###### Proof.

The crux is that recursion only happens on one of the sides of a not too large
cut. As our set of assumptions matches that of Lemma 6.11 (note that the
preconditions are the same except $\alpha\leq\frac{1}{144C\lambda
b}\leq\frac{1}{2b}$ and
$\lambda\leq\min\\{\frac{1}{18b},\,\frac{1}{15C\sqrt{b}}\\}\leq\frac{1}{18b}$),
we get the following: for any recursion from $U$ to $X$

$\Phi_{U}^{\circ}(X)<(2\alpha+3C\lambda)\phi\quad\text{ and
}\quad\operatorname{vol}_{U}^{\circ}(X)\leq\left(1-\frac{1}{3C\lambda}\right)\operatorname{vol}_{U}^{\circ}(U)$
(6.38)

To get a bound on the recursion depth, we translate these bounds to a bound on
$\operatorname{vol}_{X}^{\circ}(X)$.

We use Lemma 6.4 with $\delta=3C\lambda+2\alpha$, $S=X$, and $T=X$. These
setting verifies the requirements of Lemma 6.4: $\delta\leq 1/b$ (since
$\alpha\leq\frac{1}{4b}$, and $\lambda\leq\frac{1}{6Cb}$),
$\Phi_{U}^{\circ}(S)<\delta\phi$ from (6.38), and $T\subseteq S$. Hence,
inequality (2) from Lemma 6.4 gives

$\displaystyle\operatorname{vol}_{X}^{\circ}(X)$
$\displaystyle=\operatorname{vol}_{S}^{\circ}(T)$ inequality (2) of Lemma 6.4
$\displaystyle<\operatorname{vol}_{U}^{\circ}(T)+\delta
b\cdot\min\\{\operatorname{vol}_{U}^{\circ}(S),\operatorname{vol}_{U}^{\circ}(U\setminus
S)\\}$ $\displaystyle\leq(1+\delta b)\cdot\operatorname{vol}_{U}^{\circ}(X)$
from (6.38) $\displaystyle\leq\left(1+\delta
b\right)\left(1-\frac{1}{3C\lambda}\right)\operatorname{vol}_{U}^{\circ}(U)$
since $\alpha\leq\frac{1}{144C\lambda b}$ and
$\lambda\leq\frac{1}{15C\sqrt{b}}$
$\displaystyle\leq\left(1+\frac{1}{36C\lambda}\right)\left(1-\frac{1}{3C\lambda}\right)\operatorname{vol}_{U}^{\circ}(U)$
$\displaystyle\leq\left(1-\frac{1}{4C\lambda}\right)\operatorname{vol}_{U}^{\circ}(U)\,.$

From this we conclude that if we do a recursion on $X$ at level $\ell$, then

$\operatorname{vol}_{X}^{\circ}(X)\leq\left(1-\frac{1}{4C\lambda}\right)^{\ell}\operatorname{vol}_{V}^{\circ}(V)=\left(1-\frac{1}{4C\lambda}\right)^{\ell}\operatorname{vol}(V)<\left(1-\frac{1}{4C\lambda}\right)^{\ell}n^{2}\,.$

The bound follows. ∎

####  6.1.5 Correctness

Finally, one can see from the algorithms that they recurse only on the sides
of cuts resulting from $\textsc{BalSparseCut}_{\alpha,\lambda}$. We know such
cuts to be sparse, so intuitively there should be few inter-cluster edges in
the resulting partition of $V$. We also know that when the algorithm returns a
cluster $\\{U\\}$, it is because the corresponding BSCW declares it to be an
expander. One can then prove that the result of this process is a BLD.

######  Lemma 6.13 (Algorithm 3 outputs a BLD).

Let $b,\phi,c\in(0,1)$ such that $c\leq 1/30$ is a constant, $\phi<b$, $b\leq
c$. Also let $C\geq 31$ be a constant, let
$\textsc{BalSparseCut}_{\alpha,\lambda}$ be an $(\alpha,\lambda)$-BSCA where
$\alpha\leq\frac{1}{144C\lambda b}$,
$\lambda\leq\min\\{\frac{1}{18b},\,\frac{1}{15C\sqrt{b}}\\}$, and let $k$ be
an integer such that $k\leq\log n$. If 1 and 2 hold, then the result of
$\textsc{Decompose}(V,0)$ (i.e. Algorithm 3) is a
$(b,\epsilon,\phi,\gamma)$-BLD of $G$ where

$\epsilon=4(3C\lambda+2\alpha)\cdot\phi\cdot 9C\lambda\cdot\log
n\cdot\mathrm{e}^{2b(3C\lambda+2\alpha)9C\lambda\cdot\log n}\quad\text{ and
}\quad\gamma=6\alpha^{k+1}\,.$

###### Proof.

First note that our assumptions subsume the preconditions of Lemma 6.7. Hence,
if Algorithm 4 breaks in line (14) it is in some outer loop iteration $j$ with
$j\leq k$, so the behaviour of the algorithm is well defined (see the outer
loop for $j=1,\dots,k+1$ in line (5) of Algorithm 4).

From the description we then see that $\textsc{Decompose}(V,0)$ always outputs
a valid partition $\mathcal{U}$ of $V$. We show that $\mathcal{U}$ verifies
the two properties of Definition 3.1.

##### Property (2).

Let $X\in\mathcal{U}$, which can either be the result of the return statement
in line (6) or in line (10) of Algorithm 3.

  * •

_Return statement in line ( 6)_. Let $U\subseteq V$ be the input cluster to
the instance of Algorithm 4 that returned $X$. Also let $H=(V,E^{\prime},w)$
be the graph from line (4) and $\omega$ be the result of
$\textsc{BalSparseCut}_{\alpha,\lambda}(H[U]^{\circ},(1+\frac{1}{2\log
n})\cdot\phi)$ in line (5) of that same instance. From the description of the
algorithm, we know that the return statement in line (6) only occurs if
$\omega=\bot$, and in particular $X$ is the input cluster $U$.

As our parameter regime implies $c\leq 1/30$, $\phi<b$, $b\leq c$,
$\alpha\leq\frac{1}{2b}$, and also we have $H[U]\approx_{\delta}G[U]$ from 1,
we can use Lemma 5.3. This ensures that $\omega$ is a $(\phi,(1+\frac{1}{\log
n})\alpha,(1+c)\lambda,c)$-BSCW of $G[U]^{\circ}$. From Definition 5.1,
$\omega=\bot$ implies that $G[U]^{\circ}$ is a $\phi$-expander.

  * •

_Return statement in line ( 10)_. In this case, Algorithm 3 must have called
Algorithm 4, which in turn returned a pair $(S,\top)$. Then, Algorithm 4 must
have returned in line (10). Denoting by $A$ the value of the corresponding
variable in Algorithm 4 when it returns, we must have $A=X$. Also let
$p\in[k+1]$ be the outer loop iteration where Algorithm 4 returns, let
$H=(V,E^{\prime},w)$ be the graph from line (8), and let $\omega$ be the
result of
$\textsc{BalSparseCut}_{\alpha,\lambda}(H[A]^{\circ},(1+\frac{1}{2\log
n})\cdot\phi_{p})$ in line (5) of the inner loop iteration where the algorithm
returns.

As our parameter regime implies $c\leq 1/30$, $\phi<b$, $b\leq c$,
$\alpha\leq\frac{1}{2b}$, and also we have $H[A]\approx_{\delta_{p}}G[A]$ from
2, we can use Lemma 5.3. This ensures that $\omega$ is a
$(\phi_{p},(1+\frac{1}{\log n})\alpha,(1+c)\lambda,c)$-BSCW of $G[U]^{\circ}$
(see 6.3). From Definition 5.1, $\omega=\bot$ implies that
$G[A]^{\circ}=G[X]^{\circ}$ is a $\phi_{p}$-expander. Since $p\leq k+1$,
$k\leq\log n$, and $\phi_{p}$ is defined as

$\phi_{p}=\frac{\phi}{\left(\left(1+\frac{1}{\log
n}\right)\alpha\right)^{p}}\,,$

we conclude that $G[X]^{\circ}$ is in fact a $\psi$-expander with

$\psi=\frac{\phi}{\left(\left(1+\frac{1}{\log
n}\right)\alpha\right)^{p}}\geq\frac{\phi}{\left(\left(1+\frac{1}{\log
n}\right)\alpha\right)^{k+1}}\geq\frac{\phi}{6\alpha^{k+1}}\,.$

From the above case analysis we conclude that for every $X\in\mathcal{U}$,
$G[U]^{\circ}$ is a $\phi/\gamma$-expander with $\gamma=6\alpha^{k+1}$.

##### Property (1).

We will bound the number of inter-cluster edges by counting the number of
edges cut at every recursion level, and then sum over levels. For convenience,
let then $D=9C\lambda\cdot\log n$. We can then employ Lemma 6.12 (since our
set of assumptions matches that of the lemma), which bounds the recursion
depth by $D$.

Next, for $\ell=0,1,\dots,D$, let $\mathcal{I}^{\ell}$ be the set of instances
of Algorithm 3 at the $\ell$-th level of the recursion triggered from
$\textsc{Decompose}(V,0)$. Each instance $\mathcal{I}\in\mathcal{I}^{\ell}$ is
a pair $\mathcal{I}=(U,X)$, where $U\subseteq V$ is the input cluster to the
instance, and:

  1. 1.

if the instance returns $\\{U\\}$ in line (6), then $X=\emptyset$;

  2. 2.

if the instance makes a recursive call, then $\emptyset\neq X\subsetneq U$ is
a set on which the instance invokes Algorithm 3.

Then, since our set of assumptions matches that of Lemma 6.11, we get that
$\Phi_{U}^{\circ}(X)<(2\alpha+3C\lambda)\phi$ for every $\ell=0,\dots,D$ and
every $(U,X)\in\mathcal{I}^{\ell}$ such that $X\neq\emptyset$. Hence,

$\text{for all $\ell=0,\dots,D$, and all $(U,X)\in\mathcal{I}^{\ell}$, we have
}\quad{\partial}_{U}X<(2\alpha+3C\lambda)\phi\operatorname{vol}_{U}^{\circ}(X)\,.$
(6.39)

With this notation, define the set of edges cut at level $\ell$ to be

$C_{\ell}=\bigcup_{(U,X)\in\mathcal{I}^{\ell}}E(X,U\setminus X)\,.$

Now let $\mu=(3C\lambda+2\alpha)$, and for $\ell=0,\dots,D$ also define

$T(\ell)=\mu\phi\operatorname{vol}(V)+2\mu\cdot
b\sum_{\ell^{\prime}=0}^{\ell-1}T(\ell^{\prime})\,.$

To bound the number of inter cluster edges, we first show that $|C_{\ell}|\leq
T(\ell)$, then we resolve the recurrence $T(\ell)$, and finally we sum over
$\ell=0,\dots,D$ to conclude.

######  Claim 6.14.

For every $\ell=0,1,\dots,D$ one has $|C_{\ell}|\leq T(\ell)$.

###### Proof.

We prove the statement by induction. At level $0$ there can be only one
instance $(V,X)\in\mathcal{I}^{0}$, so the number of edges cut is
$|C_{0}|={\partial}_{V}X$. By (6.39)

$|C_{0}|<\mu\phi\operatorname{vol}_{V}^{\circ}(X)=\mu\phi\operatorname{vol}(X)\leq\mu\phi\operatorname{vol}(V)=T(0)\,,$

thus proving the base case.

Next take any $1\leq\ell\leq D$, and assume that $|C_{\ell^{\prime}}|\leq
T(\ell^{\prime})$ for all $\ell^{\prime}=0,\dots,\ell-1$. By (6.39) we know
${\partial}_{U}X<\mu\phi\cdot\operatorname{vol}_{U}^{\circ}(X)$ for all
$(U,X)\in\mathcal{I}^{\ell}$. Using the definition of
$\operatorname{vol}_{U}^{\circ}(X)$, we get

$\displaystyle{\partial}_{U}X<\mu\phi\cdot\operatorname{vol}_{U}^{\circ}(X)$
$\displaystyle=\mu\phi\cdot\left(\operatorname{vol}(X)+\frac{b-\phi}{\phi}\operatorname{bnd}_{U}(X)\right)$
(6.40) since $\operatorname{bnd}_{U}(X)\leq{\partial}U$
$\displaystyle\leq\mu\phi\cdot\operatorname{vol}(X)+\mu b\cdot{\partial}U\,.$
(6.41)

Observe that the union of all $E(U,V\setminus U)$ on level $\ell$ is a subset
of all edges cut on previous recursion levels. This means that

$\sum_{(U,X)\in\mathcal{I}^{\ell}}{\partial}U\leq
2\sum_{\ell^{\prime}=0}^{\ell-1}|C_{\ell^{\prime}}|\,,$ (6.42)

since every $e\in C_{\ell^{\prime}}$ is counted at most twice by the sum over
$\mathcal{I}^{\ell}$.

Using the induction hypothesis and observing that the cuts
$\\{X:(U,X)\in\mathcal{I}^{\ell}\\}$ must be disjoint, we can upper-bound
$|C_{\ell}|$ as

$\displaystyle|C_{\ell}|$
$\displaystyle=\sum_{(U,X)\in\mathcal{I}^{\ell}}{\partial}_{U}X$ by (6.41) and
disjointness of the $X$’s $\displaystyle<\mu\phi\operatorname{vol}(V)+\mu
b\sum_{(U,X)\in\mathcal{I}^{\ell}}{\partial}U$ by (6.42)
$\displaystyle\leq\mu\phi\operatorname{vol}(V)+2\mu
b\sum_{\ell^{\prime}=0}^{\ell-1}|C_{\ell^{\prime}}|$ by the induction
hypothesis $\displaystyle\leq\mu\phi\operatorname{vol}(V)+2\mu
b\sum_{\ell^{\prime}=0}^{\ell-1}T(\ell^{\prime})$ $\displaystyle=T(\ell)\,.$

thus showing the inductive statement. ∎

Now we solve the recurrence.

######  Claim 6.15.

$T(\ell)\leq\mu\phi\operatorname{vol}(V)(1+2\mu b)^{\ell}$ for all $\ell\geq
0$.

###### Proof.

Let $\ell\geq 1$ and assume the statement holds true for all
$0\leq\ell^{\prime}\leq\ell-1$. Then,

$\displaystyle T(\ell)$ $\displaystyle=\mu\phi\operatorname{vol}(V)+2\mu
b\sum_{\ell^{\prime}=0}^{\ell-1}T(\ell^{\prime})$
$\displaystyle\leq\mu\phi\operatorname{vol}(V)+2\mu
b\sum_{\ell^{\prime}=0}^{\ell-1}\mu\phi\operatorname{vol}(V)(1+2\mu
b)^{\ell^{\prime}}$ $\displaystyle=\mu\phi\operatorname{vol}(V)\left(1+2\mu
b\sum_{\ell^{\prime}=0}^{\ell-1}(1+2\mu b)^{\ell^{\prime}}\right)$
$\displaystyle=\mu\phi\operatorname{vol}(V)\left(1+2\mu b\frac{(1+2\mu
b)^{\ell}-1}{1+2\mu b-1}\right)$
$\displaystyle=\mu\phi\operatorname{vol}(V)(1+2\mu b)^{\ell}\,.$

∎

Now combing 6.14 and 6.15, one has that the number of inter-cluster edges in
$\mathcal{U}$ is

$\displaystyle\sum_{U\in\mathcal{U}}{\partial}U\leq
2\sum_{\ell=0}^{D}|C_{\ell}|\leq 2\sum_{\ell=0}^{D}T(\ell)\leq
2\mu\phi\operatorname{vol}(V)\cdot(D+1)\cdot(1+2\mu b)^{D}\leq
4\mu\cdot\phi\cdot\operatorname{vol}(V)\cdot D\cdot e^{2b\mu D}\,.$

∎

###  6.2 Dynamic stream implementation

In the previous sections we analysed Algorithm 3 and Algorithm 4 in an ideal,
offline setting with “free” access to sparsifiers. To get Lemma 6.1, we only
need to lift this assumption, and combine lemmas from the previous section.

See 6.1

###### Proof.

Let $C=40,c=1/40$, and define the quantities $D=9C\lambda\cdot\log n$,
$\delta=c^{2}b/\log n$, and $\delta_{j}=\delta\cdot(\alpha(1+1/\log n))^{-j}$
for $j\in[k+1]$. We process the stream as follows.

  1. 1.

We maintain $D+1$ independent samples from the distribution
$\mathcal{D}_{\delta}$ using the algorithm of Lemma 4.2, resulting in a
collection of sparsifiers $H_{\ell}$ for $0\leq\ell\leq D$.

  2. 2.

For every $j\in[k+1]$, we maintain $(D+1)\cdot 1/b$ samples from the
distribution $\mathcal{D}_{\delta_{j}}$ using the algorithm of Lemma 4.2,
resulting in a collection of sparsifiers $H_{\ell,j,h}$ for $0\leq\ell\leq D$,
$j~{}\in~{}[k+1]$, $h\in[1/b]$.

After having processed the stream as described above, we want to use Algorithm
3 and Algorithm 4 to decode these samples into a BLD. In Algorithm 3 and
Algorithm 4 we have hardwired parameters $k,\alpha,\lambda,C,c$: the
parameters $k,\alpha,\lambda$ are as in the lemma statement, and $C,c$ are set
as defined above (i.e. $C=40,c=1/40$). Algorithm 3 and Algorithm 4 also use
BLD parameters $b,\phi$: $b$ is just the value in the lemma statement, and we
set

$\phi=\frac{\epsilon}{4(3C\lambda+2\alpha)\cdot
D\cdot\mathrm{e}^{2b(3C\lambda+2\alpha)D}}\,.$

The only thing left to specify about the algorithms is the sparsifier-access.
Since we process the stream by essentially computing a number of sparsifiers,
there is a natural way to do this: for $0\leq\ell\leq D$, we define the
procedure $\textsc{Sparsifier}^{c}_{\ell}(U,\cdot)$ from line (4) in Algorithm
3 to return $H_{\ell}$ for every $U\subseteq V$; similarly, for $0\leq\ell\leq
D$, $j~{}\in~{}[k+1]$, $h\in[1/b]$, we define the procedure
$\textsc{Sparsifier}^{c}_{\ell,j,h}(A,\cdot)$ from line (8) in Algorithm 4 to
return $H_{\ell,j,h}$ for every $A\subseteq V$.

##### Correctness.

Since $C,\lambda=O(1)$, $\alpha b\leq 1/\log n$, $D=O(\log n)$, one can see
that $\phi=\Omega(\frac{\epsilon}{\alpha\log n})$. From this value of $\phi$
we also get $\phi<b$, since $C,\lambda,\alpha\geq 1$, $\epsilon\leq b\log n$,
the exponential is at least $1$, and $D>\log n$ . Then, our parameter regime
has all the conditions for using Lemma 6.12, Lemma 6.9, Lemma 6.13: we have an
$(\alpha,\lambda)$-BSCA $\textsc{BalSparseCut}_{\alpha,\lambda}$, $\phi<b$,
$b\leq 1/\log n\leq c\leq 1/30$, $C\geq 31$, $\alpha\leq\frac{1}{b\log
n}\leq\frac{1}{144C\lambda b}\leq\frac{1}{2b}$, $\lambda=O(1)$ so
$\lambda\leq\min\\{\frac{1}{18b},\,\frac{1}{15C\sqrt{b}},\frac{c}{2b}\\}$,
$k\geq\frac{\log{n^{5}\alpha}}{\log{b^{-1/2}}/{\lambda}}$ implies
$k\geq\log\frac{n^{2}}{\phi}/\log\frac{c}{\lambda\cdot b}$ (since
$\phi=\Omega(\frac{\epsilon}{\alpha\log n})$, $\epsilon\geq 1/n^{2}$, and $c$
is a constant), and $k\leq\log n$. We now just want to lift 1 and 2, so as to
apply these lemmas. From our definition of
$\textsc{Sparsifier}_{\ell}(U,\cdot)$ and
$\textsc{Sparsifier}_{\ell,j,h}(A,\cdot)$ above, we have the following claim.

######  Claim 6.16.

Assumptions 1 and 2 hold with high probability as long as $\ell\leq D$ and
$h\leq 1/b$.

###### Proof.

The claim follows from the way we process the stream, described above, and
from our definition of $\textsc{Sparsifier}^{c}_{\ell}(U,\cdot)$ and
$\textsc{Sparsifier}^{c}_{\ell,j,h}(A,\cdot)$.

  * •

For every $0\leq\ell\leq D$ and any $U\subseteq V$,
$\textsc{Sparsifier}^{c}_{\ell}(U,\cdot)$ outputs the graph $H_{\ell}$,
independently sampled from $\mathcal{D}_{\delta}$. Algorithm 3 only calls
$\textsc{Sparsifier}^{c}_{\ell}(U,b)$ for a cluster $U$ that was found using
randomness from levels before $\ell$ (simply by the description of the
algorithm, see recursive calls in lines (7), (10), (11) of Algorithm 3). Thus,
by Lemma 4.2 we know that $H_{\ell}[U]\approx_{\delta}G[U]$ with high
probability. Since there can be at most $n$ calls to
$\textsc{Sparsifier}^{c}_{\ell}(U,b)$ for any $\ell$, we can conclude that
$H_{\ell}$ works for each of them with high probability.

  * •

For every $0\leq\ell\leq D,\,j\in[k+1],\,h\in[1/b]$ and any $A\subseteq V$,
$\textsc{Sparsifier}^{c}_{\ell,j,h}(A,\cdot)$ outputs the graph
$H_{\ell,j,h}$, independently sampled from $\mathcal{D}_{\delta_{j}}$.
Similarly as before, we can see from the description of Algorithm 4 that
$\textsc{Sparsifier}^{c}_{\ell,j,h}(A,b_{j})$ can only be called on a cluster
$A$ that depends on the randomness of a previous level (in case $A$ equals the
input cluster $U$ to Algorithm 4) or a previous iteration (in case $A$ was
updated in line (13)). Thus, $A$ is independent from $H_{\ell,j,h}$. Thus, by
Lemma 4.2 we know that $H_{\ell,j,h}[A]\approx_{\delta_{j}}G[A]$ with high
probability. Also in this case there can be at most $n$ calls to
$\textsc{Sparsifier}^{c}_{\ell,j,h}(A,b_{j})$ for any triple $\ell,j,h$, so
$H_{\ell,j,h}$ works for each of them with high probability.

∎

Provided 1 and 2 hold, Lemma 6.12 and Lemma 6.9 are guaranteeing that there is
no point in the execution of the algorithm with recursion level $\ell$ larger
than $D$ or with inner loop index $h$ (see line (7)) larger than $1/b$. On the
other hand, 6.16 ensures that 1 and 2 hold with high probability as long as
$\ell\leq D$ and $h\leq 1/b$. Hence, we have that the results from Lemma 6.12,
Lemma 6.9, Lemma 6.13 hold simultaneously with high probability. In
particular, the output $\mathcal{U}$ of $\textsc{Decompose}(V,0)$ is a
$(b,\epsilon,\phi,\gamma)$-BLD of $G$ with high probability for
$\gamma=O(\alpha^{k+1})$ (note that we set $\phi$ exactly by rearranging the
value of $\epsilon$ given by Lemma 6.13).

##### Space complexity.

The space requirement for processing the stream is dominated by the
sparsifiers that we maintain, plus the space used by any call to
$\textsc{BalSparseCut}_{\alpha,\lambda}$ for the decoding phase. From Lemma
4.2 we know that sampling from $\mathcal{D}_{\delta}$ can be done by
maintaining a linear sketch of $\widetilde{O}(n/\delta^{2})$ bits, and
sampling from $\mathcal{D}_{\delta_{j}}$ can be done maintaining a linear
sketch of $\widetilde{O}(n/\delta_{j}^{2})$ bits. Since we maintain $D+1$
samples from $\mathcal{D}_{\delta}$, and $(D+1)\cdot 1/b$ samples from
$\mathcal{D}_{\delta_{j}}$ for every $j\in[k+1]$, the space complexity for
processing the stream is

$(D+1)\cdot\widetilde{O}\left(\frac{n}{\delta^{2}}\right)+(D+1)\cdot\frac{1}{b}\cdot\sum_{j=1}^{k+1}\widetilde{O}\left(\frac{n}{\delta_{j}^{2}}\right)\,.$

Because we defined $D=9C\lambda\cdot\log n$, $\delta=c^{2}b/\log n$,
$\delta_{j}=\delta\cdot(\alpha(1+1/\log n))^{-j}$, and we have
$C,\lambda=O(1),\,k=O(\log n),c=\Omega(1)$, we use at most

$O(\log n)\widetilde{O}\left(\frac{n}{b^{2}}\right)+O(\log
n)O\left(\frac{1}{b}\right)O(k)\cdot\widetilde{O}\left(\frac{n}{b^{2}}\right)\cdot\alpha^{O(k)}=\widetilde{O}\left(\frac{n}{b^{3}}\right)\cdot\alpha^{O(k)}$

bits of space for the sparsifiers. Finally, note that Algorithms 3 and 4 run
$\textsc{BalSparseCut}_{\alpha,\lambda}$ on sparsifiers with at most $n$
vertices and at most

$\max\left\\{\widetilde{O}(n/\delta^{2}),\max_{j\in[k+1]}\left\\{\widetilde{O}(n/\delta_{j}^{2})\right\\}\right\\}=\widetilde{O}\left(\frac{n}{b^{2}}\right)\cdot\alpha^{O(k)}$

edges, by Lemma 4.2. As we can reuse the space for each call, this takes an
extra $S(n,\widetilde{O}(n/b^{2})\alpha^{O(k)})$ bits of space, leading to the
claimed space complexity for the decoding.

##### Time complexity.

Throughout the recursion of $\textsc{Decompose}(V,0)$, Algorithms 3 and 4 make
at most $\operatorname*{poly}(n)$ calls to
$\textsc{BalSparseCut}_{\alpha,\lambda}$. As noted above, each of these calls
is on a graph with at most $n$ vertices and
$\widetilde{O}(n/b^{2})\alpha^{O(k)}$ edges. Lemma 4.2 also guarantees that
decoding the linear sketch to get a sample from $\mathcal{D}_{\delta}$ and
$\mathcal{D}_{\delta_{j}}$ takes $\operatorname*{poly}(n)$ time. Hence the
running time of the decoding is $\operatorname*{poly}(n)\cdot
T(n,\widetilde{O}(n/b^{2})\alpha^{O(k)})$.

##### Sparsity parameter in BSCA calls.

By the way we set $\phi$ and by definition of the algorithm, we have that
every call to $\textsc{BalSparseCut}_{\alpha,\lambda}(\cdot,\psi)$ is made
with a sparsity parameter $\psi\in(0,1)$ that is
$\psi\leq\phi\leq\frac{1}{10\alpha}$.

∎

##  7 Lower bound for two-level expander decomposition

The goal of this section is to show that repeatedly computing EDs on the
inter-cluster edges necessarily incurs a dependence on the sparsity parameter.
Formally, the result is the following.

See 3 By Yao’s minimax principle, it is sufficient to give a distribution
$\mathcal{G}$ over graphs with vertex set $V$ such that any deterministic
streaming algorithm that computes, with probability at least $0.9$, an
$(\epsilon,\phi,\ell)$-RED of $G\sim\mathcal{G}$ takes $\Omega(n/\epsilon)$
bits of space. We are not going to use the fact that the stream can be dynamic
to show the lower bound, so any stream that reveals the edges of
$G\sim\mathcal{G}$ in an arbitrary order serves our purposes.

We then proceed as follows. In Section 7.1 we describe our hard distribution
over graphs, and show a structural property of its two-level
$(\epsilon,\phi)$-RED. In Section 7.2 we introduce a communication problem,
$\operatorname*{\textsc{recover}}$, and show a reduction to RED. Finally, in
Section 7.3 we give a communication lower bound for
$\operatorname*{\textsc{recover}}$. We combine these results into proving 3 in
Section 7.4.

###  7.1 Hard distribution

The randomness of our hard distribution $\mathcal{G}$ arises from sampling
Erdős-Rényi graphs. We recall the definition for convenience of the reader.

######  Definition 7.1.

Let $N$ be an integer and let $p\in[0,1]$. The distribution of Erdős-Rényi
graphs $\operatorname*{ER}(N,p)$ is the distribution over $N$-vertex graphs
$H=(U,F)$ where each pair $e\in\binom{U}{2}$ is in $F$ with probability $p$
independently of other pairs.

Let $d,m$ be integers such that $3\leq d<m<n$. We now define our hard
distribution $\mathcal{G}$ over $n$-vertex graphs $G=(V,E)$, and we illustrate
it in Figure 4.

######  Definition 7.2 (Distributions $\mathcal{G}$ and
$\mathcal{G}^{\prime}$).

We partition $V=[n]$ arbitrarily into two sets $S$ and $T$ with $n/2$ vertices
each, and further partition $S$ into $n/m$ sets $S_{1},\dots,S_{n/m}$ with
$m/2$ vertices each. The distribution $\mathcal{G}_{n,d,m}$ is supported over
graphs $G=(V,E)$ where $E$ is defined as follows.

  1. 1.

For each $i~{}\in~{}[n/m]$, the induced subgraph $G[S_{i}]$ is sampled
independently from the Erdős-Rényi distribution
$\operatorname*{ER}({m}/{2},4d/m)$ (see Definition 7.1 above). We denote by
$\mathcal{G}^{\prime}_{n,d,m}$ the distribution of the subgraph $G[S]$, i.e.
$\mathcal{G}^{\prime}_{n,d,m}=\operatorname*{ER}({m}/{2},4d/m)^{\otimes n/m}$.

  2. 2.

The induced subgraph $G[T]$ is a fixed $d$-regular $\psi$-expander, for
$\psi=\Omega(1)$ independent of $d,m,n$.

  3. 3.

We fix for convenience an arbitrary labelling $s_{i,1},\dots,s_{i,m/2}$ of the
vertices in each $S_{i},\,i\in[n/m]$, and we sample
$K\sim\operatorname{UNIF}([m/2])$. Then, for every $i\in[n/m]$, we add $dm/2$
edges from $s_{i,K}$ to $T$ so that each $t\in T$ has $d$ incident edges in
$E(S,T)$ (one way to do so is by partitioning $T$ into $n/(dm)$ subsets
$T_{1},\dots,T_{n/(dm)}$ with $dm/2$ vertices each and connecting $s_{i,K}$ to
each vertex of $T_{\lceil i/d\rceil}$ for every $i\in[n/m]$).

Since the parameters $n,d,m$ are fixed hereafter, we may drop the subscript
from $\mathcal{G}_{n,d,m}$ and $\mathcal{G}^{\prime}_{n,d,m}$ and simply
denote them by $\mathcal{G}$ and $\mathcal{G}^{\prime}$ respectively.

Figure 4: Illustration of the graph we use for proving the lower bound. Thick
bullets represent important vertices, thick lines represent important edges,
dotted lines represent edges connecting the important vertices to $T$.

Roughly speaking, our hard instances should be composed of $n/m$ regular
expanders that are densely connected to $T$, which is also an expander,
through a selection of “special” vertices. We will show that the hardness
arises from recovering information about certain important vertices and edges,
defined below and also illustrated in Figure 4.

######  Definition 7.3 (Important vertices and edges).

Let $G=(V,E)\in\mathrm{supp}(\mathcal{G})$. Denote by $k\in[m/2]$ the unique
index such that $\\{s_{i,k}:i\in[n/m]\\}=\\{s\in S:\\{t\in T:\\{s,t\\}\in
E\\}\neq\emptyset\\}$. Then, we define the set of important vertices
$V^{*}=\\{s_{i,k}:i\in[n/m]\\}$ to be the set of vertices of $S$ that are
adjacent to $T$, and define the set of important edges
$E^{*}=\\{\\{u,v^{*}\\}:u\in S\,,v^{*}\in V^{*}\\}$ to be the set of edges in
the induced subgraph $G[S]$ that are incident on $V^{*}$.

######  Remark 1.

Note that any sample $G\sim\mathcal{G}$ can be defined by $(G^{\prime},K)$,
where $G^{\prime}=(S,E^{\prime})$ is the graph consisting of the disjoint
union of the subgraphs $(G[S_{i}])_{i\in[n/m]}$, and $K\in[m/2]$ is the random
index determining the important vertices and edges. This is because the edges
within $G[T]$ are the same for all $G\sim\mathcal{G}$, and the edges $E(S,T)$
are determined by $K$. By virtue of this observation we abuse notation and
write $G=(G^{\prime},K)\sim\mathcal{G}$. Moreover, for any
$(G^{\prime},K)\sim\mathcal{G}$ one has $G^{\prime}\sim\mathcal{G}^{\prime}$,
and conversely, for any $G^{\prime}\sim\mathcal{G}^{\prime}$ and
$K\sim\operatorname{UNIF}([m/2])$ one also has
$(G^{\prime},K)\sim\mathcal{G}$.

In the remainder of the section, we call a graph $(1\pm\delta)\Delta$-regular
for an integer $\Delta>0$ and $\delta\in[0,1]$, if each of its vertices has
degree in the range $[(1-\delta)\Delta,(1+\delta)\Delta]$. With this
terminology, we show that in any valid $(\epsilon,\phi)$-ED of $G$, most of
the important edges are crossing edges, as depicted in Figure 5. This works
under the assumption that each $G[S_{i}]$ is a near-regular expander.

Figure 5: Illustration of the ideal expander decomposition of the graph. Thick
bullets represent important vertices, smaller bullets represent ordinary
vertices, thick lines represent important edges, dotted lines represent the
rest of the edges. Grey areas represent the clusters in the decomposition.

######  Lemma 7.4.

Let $G=(V,E)\in\mathrm{supp}(\mathcal{G})$, and let $\epsilon,\phi\in(0,1)$
such that $\epsilon\leq 10^{-5}\cdot\psi\cdot\frac{d}{m}$ and $\phi\geq 11/m$.
If $n\geq 100m$, $m\geq 500$, and every subgraph $(G[S_{i}])_{i\in[n/m]}$ is a
$(1\pm 1/10)2d$-regular $\frac{1}{3}$-expander, then any $(\epsilon,\phi)$-ED
$\mathcal{U}$ of $G$ satisfies

$\left|E^{*}\setminus\mathcal{U}\right|\geq\frac{4}{5}\cdot\left|E^{*}\right|\,.$

###### Proof.

Let $G=(V,E)\in\mathrm{supp}(\mathcal{G})$ and let $k\in[m/2]$ such that the
important vertices are $s_{i,k}$ for $i\in[n/m]$ (note that such value of $k$
can be uniquely inferred from seeing $G$ since the ordering of the vertices is
fixed). Note that by Definition 7.2 together with our assumption, the graph
$G$ has at most $11/10\cdot dn/2+3/4\cdot dn\leq 1.3dn$ edges.

Hereafter, let $\mathcal{U}$ be any $(\epsilon,\phi)$-ED of $G$. We begin by
arguing that there is a giant cluster in $\mathcal{U}$ that covers most of $T$
and most of the important vertices.

######  Claim 7.5.

There is a component $U^{*}\in\mathcal{U}$ such that

$|T\cap
U^{*}|\geq\left(1-12\frac{\epsilon}{\psi}\right)|T|\quad\text{and}\quad|V^{*}\cap
U^{*}|\geq\left(1-12\frac{\epsilon}{\psi}\right)|V^{*}|\,.$

###### Proof.

For any valid $(\epsilon,\phi)$-ED $\mathcal{U}$, we must have
$|E\setminus\mathcal{U}|\leq\epsilon\cdot 1.3dn$. Since $G[T]$ is a
$d$-regular $\psi$-expander, there is a component $U^{*}\in\mathcal{U}$ that
contains at least $(1-3\epsilon/\psi)\cdot n/2$ vertices from $T$, i.e.

$|T\cap
U^{*}|\geq\left(1-3\frac{\epsilon}{\psi}\right)\cdot\frac{n}{2}=\left(1-3\frac{\epsilon}{\psi}\right)|T|\,.$

To see why, note that if this was not the case then we could construct a cut
$S=\cup_{U\in\mathcal{U}^{\prime}}U\cap T$ for some
$\mathcal{U}^{\prime}\subseteq\mathcal{U}$ such that
$3\epsilon/\psi\cdot|T|<|S|\leq|T|/2$ and conclude that there would be at
least $\psi\operatorname{vol}_{G[T]}(S)>\epsilon\cdot 1.5dn$ edges crossing
$\mathcal{U}$.

Since each vertex in $T$ has an edge to $d$ important vertices (see Definition
7.2), there are at least $(1-6\epsilon/\psi)\cdot n/m$ important vertices with
at least $dm/4$ neighbours in $U^{*}\cap T$, i.e.

$\Big{|}\Big{\\{}s\in V^{*}:\,\left|\\{t\in U^{*}\cap T:\\{s,t\\}\in
E\\}\right|\geq\frac{1}{4}dm\Big{\\}}\Big{|}\geq\left(1-6\frac{\epsilon}{\psi}\right)\cdot\frac{n}{m}=\left(1-6\frac{\epsilon}{\psi}\right)\cdot|V^{*}|\,.$

To see why, note that if this was not the case, we would have $|\\{s,t\\}\in
E:\,s\in V^{*}\,,t\in T\setminus U^{*}\\}|$ to be larger than
$(6\epsilon/\psi\cdot n/m)\cdot dm/4$, which is impossible since every $t\in
T$ has $d$ incident edges in $E(S,T)$ and $|T\setminus U^{*}|\leq
3\epsilon/\psi\cdot n/2$.

Now, because most of the important vertices have many edges to $T\cap U^{*}$,
most of these should also be in $U^{*}$, otherwise too many edges would cross:
since $|E\setminus\mathcal{U}|\leq\epsilon\cdot 1.3dn$, there must be at most
$6\epsilon/\psi\cdot n/m+\frac{\epsilon\cdot 1.3dn}{dm/4}\leq
12\epsilon/\psi\cdot n/m$ important vertices that are not in $U^{*}$, i.e.

$|V^{*}\cap
U^{*}|\geq\left(1-12\frac{\epsilon}{\psi}\right)\cdot\frac{n}{m}=\left(1-12\frac{\epsilon}{\psi}\right)\cdot|V^{*}|\,.$

∎

We want to confine our attention to important vertices whose corresponding
subgraph $G[S_{i}]$ locally preserves property (1) of Definition 1.1, i.e. has
few inter-cluster edges as compared to its own volume. Formally, we consider
the set of good vertices, defined as

$V^{*}_{\text{g}}=\left\\{s_{i,k}\in V^{*}:s_{i,k}\in
U^{*}\,,\left|(E\setminus\mathcal{U})\cap\binom{S_{i}}{2}\right|\leq{200\epsilon}dm\right\\}\,.$
(7.1)

We next show that the subgraph $G[S_{i}]$ corresponding to a good vertex is
covered almost entirely by a single cluster, except the good vertex itself
which is assigned to $U^{*}$.

######  Claim 7.6.

Let $s_{i,k}\in V^{*}_{{\operatorname*{g}}}$. Then, there is a cluster
$U\in\mathcal{U}$ such that

$s_{i,k}\notin U\quad\text{and}\quad|U\cap
S_{i}|\geq\left(1-700{\epsilon}\right)|S_{i}|\,.$

###### Proof.

Since $G[S_{i}]$ is a $(1\pm 1/10)2d$-regular $\frac{1}{3}$-expander by
assumption, there is at least one component $U\in\mathcal{U}$ containing at
least $(1-700\epsilon)m/2$ vertices in $S_{i}$, i.e.

$|U\cap
S_{i}|\geq\left(1-700{\epsilon}\right)\frac{m}{2}=\left(1-700{\epsilon}\right)|S_{i}|\,,$
(7.2)

To see why, note that if this was not the case we could construct a cut
$R=\cup_{W\in\mathcal{U}^{\prime}}W\cap S_{i}$ for some
$\mathcal{U}^{\prime}\subseteq\mathcal{U}$ such that $10/9\cdot
700\epsilon\cdot|S_{i}|<|R|\leq 9/11\cdot|S_{i}|/2$ and conclude that there
would be at least $1/3\cdot\operatorname{vol}_{G[S_{i}]}(R)>230\epsilon dm$
edges crossing $\mathcal{U}$ inside $S_{i}$, contradicting the fact that
$s_{i,k}\in V^{*}_{{\operatorname*{g}}}$ (see the definition in (7.1)).

Hereafter, let $U\in\mathcal{U}$ be the cluster that satisfies (7.2) (which is
unique, since $\epsilon\leq 10^{-5}$). We know from 7.5 that there is a
cluster $U^{*}\in\mathcal{U}$ that contains all good vertices (by definition
of good vertex, see (7.1)) and that covers most of $T$. To show that
$s_{i,k}\notin U$, we leverage the fact that $s_{i,k}\in U^{*}$ and that
$G[U^{*}]$ must be a $\phi$-expander by property (2) of Definition 1.1.
Suppose towards a contradiction that $U^{*}=U$, and let $Q=(U^{*}\cap
S_{i})\setminus\\{s_{i,k}\\}$. Because $G[S_{i}]$ is $(1\pm 1/10)2d$-regular,
the volume of this set in $G[U^{*}]$ is at least

$\displaystyle\operatorname{vol}_{G[U^{*}]}(Q)$
$\displaystyle\geq-\deg_{G[S_{i}]}(s_{i,k})+\sum_{u\in U^{*}\cap
S_{i}}\deg_{G[U^{*}\cap S_{i}]}(u)$
$\displaystyle\geq-\frac{11}{10}2d+\sum_{u\in U^{*}\cap
S_{i}:\,\deg_{G[U^{*}\cap
S_{i}]}(u)\geq(1-600{\epsilon})\deg_{G[S_{i}]}(u)}\deg_{G[U^{*}\cap
S_{i}]}(u)\,.$

We next observe that the sum above has at least $|U^{*}\cap S_{i}|/2$ many
terms, for if this was not the case we would have at least
$300\epsilon|U^{*}\cap S_{i}|\cdot 9/10\cdot 2d\geq 200\epsilon dm$ edges from
$U^{*}\cap S_{i}$ to $S_{i}\setminus U^{*}$, which would contradict
$s_{i,k}\in V^{*}_{{\operatorname*{g}}}$ (see the definition in (7.1)). We
then continue from above and hence get

$\displaystyle\operatorname{vol}_{G[U^{*}]}(Q)$
$\displaystyle\geq-\frac{11}{10}2d+\frac{1}{2}|U^{*}\cap
S_{i}|\cdot\left(1-600{\epsilon}\right)\deg_{G[S_{i}]}(u)$
$\displaystyle\geq-\frac{11}{10}2d+\frac{1}{2}|U^{*}\cap
S_{i}|\cdot\left(1-600{\epsilon}\right)\frac{9}{10}2d$ since $|S_{i}\cap
U^{*}|\geq(1-700\epsilon)|S_{i}|$
$\displaystyle\geq-\frac{11}{10}2d+\frac{9}{10}2d\frac{1}{2}\left(1-1400{\epsilon}\right)\frac{m}{2}\,.$

Moreover, we know that $|U^{*}\cap
T|\geq(1-3\epsilon/\psi)n/2\geq(1-1/8000)n/2$ by our assumption on $\epsilon$,
so the fact that $G[T]$ is $d$-regular implies
$\operatorname{vol}_{G[U^{*}]}(U^{*})\geq\operatorname{vol}_{G[U^{*}\cap
T]}(U^{*}\cap T)\geq dn/10$. Also, by near-regularity of $G$ and because
$m\leq n/100$, we have $\operatorname{vol}_{G[U^{*}]}(Q)\leq 3d\cdot
m/2<dn/20\leq\frac{1}{2}\operatorname{vol}_{G[U^{*}]}(U^{*})$. This means that
$Q$ is the smaller side of the cut. On the other hand, the number of edges
crossing the cut $Q$ in $G[U^{*}]$ is too small, since vertices in $Q$ can
only connect to the rest of $U^{*}$ through edges incident on $s_{i,k}$, i.e.

${\partial}_{U^{*}}Q=\deg_{G[S_{i}]}(s_{i,k})\leq\frac{11}{10}2d\,.$

Therefore, $U_{i}=U^{*}$ implies

$\Phi_{G[U^{*}]}\leq\Phi_{G[U^{*}]}(Q)=\frac{{\partial}_{U^{*}}Q}{\operatorname{vol}_{G[U^{*}]}(Q)}\leq\frac{\frac{11}{10}2d}{\frac{9}{10}d\left(1-1400{\epsilon}\right)\frac{m}{2}-\frac{11}{10}2d}\leq\frac{10}{m}<\phi\,,$

a contradiction. Here we used that $m\geq 500$, $\phi\geq 11/m$, and
$\epsilon\leq 10^{-5}$. ∎

By virtue of 7.6, we have the following setting: for every good vertex
$s_{i,k}\in V^{*}_{\text{g}}$, there is one component $U$ covering a
$(1-700\epsilon)$ fraction of $S_{i}$ except $s_{i,k}$ itself. Therefore, many
important edges incident on each good vertex are crossing edges, i.e.

$\\{\\{s,s^{\prime}\\}\in E^{*}:\,s=s_{i,k},s^{\prime}\notin U^{*}\\}\subseteq
E(U^{*}\cap S_{i},S_{i}\setminus U^{*})\subseteq
E\setminus\mathcal{U}\quad\text{for all $s_{i,k}\in V^{*}_{\text{g}}$,}$

and

$|U^{*}\cap S_{i}|\leq|U\setminus S_{i}|\leq
700{\epsilon}|S_{i}|=700{\epsilon}\frac{m}{2}\quad\text{for all $s_{i,k}\in
V^{*}_{\text{g}}$.}$

In particular, the above conditions implies that, among the important edges
incident on each good vertex, at most $700\epsilon\cdot m/2$ of them can land
in the same cluster $U^{*}$ as the good vertex itself, i.e.

$|\\{\\{s,s^{\prime}\\}\in E^{*}:\,s=s_{i,k},s^{\prime}\notin
U^{*}\\}|\geq\frac{9}{10}2d-700{\epsilon}\frac{m}{2}\quad\text{for all
$s_{i,k}\in V^{*}_{\text{g}}$.}$ (7.3)

If there are many good vertices, we can conclude that a lot of the important
edges are crossing.

######  Claim 7.7.

One has $|V^{*}_{\operatorname*{g}}|\geq\frac{49}{50}|V^{*}|$.

###### Proof.

Since the number of crossing edges is
$|E\setminus\mathcal{U}|\leq\epsilon\cdot 1.3dn$, one has

$\left|\left\\{s_{i,k}\in
V^{*}:\,\left|(E\setminus\mathcal{U})\cap\binom{S_{i}}{2}\right|\leq{200\epsilon}dm\right\\}\right|\geq\left(1-\frac{1}{100}\right)\frac{n}{m}=\left(1-\frac{1}{100}\right)|V^{*}|\,.$
(7.4)

Combining 7.5 and the above bound, we know $V^{*}_{\operatorname*{g}}$ to be
large:

$|V^{*}_{\text{g}}|\geq\left(1-12\frac{\epsilon}{\psi}-\frac{1}{100}\right)\cdot|V^{*}|\geq\left(1-\frac{1}{50}\right)\cdot|V^{*}|\,,$

where we use the assumption that $\epsilon\leq
10^{-5}\cdot\psi\cdot\frac{d}{m}$. ∎

By 7.7 and the bound in (7.3), we can conclude the proof:

$\displaystyle|E^{*}\setminus\mathcal{U}|\geq\sum_{s_{i,k}\in
V^{*}_{\text{g}}}|\\{\\{s,t\\}\in
E^{*}:\,s=s_{i,k}\\}|\geq\left(\frac{9}{10}-700{\epsilon}\frac{m}{2}\frac{1}{2d}\right)2d\cdot|V^{*}_{\text{g}}|\,,$

and by 7.7 we get

$\displaystyle|E^{*}\setminus\mathcal{U}|\geq\left(\frac{9}{10}-700{\epsilon}\frac{m}{2}\frac{1}{2d}\right)2d\cdot\frac{49}{50}\cdot\frac{n}{m}\geq\frac{4}{5}\cdot|E^{*}|\,,$

where we used $\epsilon\leq 10^{-5}\psi\frac{d}{m}$ in the last inequality. ∎

###  7.2 Reduction to a communication problem

We introduce the two-party one-way communication problem
$\operatorname*{\textsc{recover}}$, defined as follows.

######  Definition 7.8 (Communication problem
$\operatorname*{\textsc{recover}}$).

Let $\xi>0$ be a real parameter. In the communication problem
$\operatorname*{\textsc{recover}}_{\xi}$, Alice’s input is a graph
$G^{\prime}=(S,E^{\prime})$, and Bob’s output is a set of pairs of vertices
$F~{}\subseteq~{}\binom{S}{2}$ such that

  1. 1.

$|F|\leq 6\xi\cdot|E^{\prime}|$, and

  2. 2.

at least a $1/10$ fraction of the pairs in $F$ are edges of $G^{\prime}$, i.e.
$|F\cap E^{\prime}|\geq 1/10\cdot|E^{\prime}|$.

We give a reduction from $\operatorname*{\textsc{recover}}_{\epsilon m}$ to
$(\epsilon,\phi,2)$-RED, in the setting where Alice’s input $G^{\prime}$ is an
$n/2$-vertex graph drawn from $\mathcal{G}^{\prime}$. We recall that
$\mathcal{G}^{\prime}=\mathcal{G}^{\prime}_{n,d,m}=\operatorname*{ER}({m}/{2},4d/m)^{\otimes
n/m}$ is the distribution over $n/2$-vertex graphs $G^{\prime}=(S,E^{\prime})$
consisting of the disjoint union of $n/m$ disjoint Erdős-Rényi graphs on $m/2$
vertices (see Definition 7.2). We then begin by verifying that, with high
probability, an input $G^{\prime}\sim\mathcal{G}^{\prime}$ is a collection of
$n/m$ nearly regular expanders.

######  Lemma 7.9.

Let $G^{\prime}\sim\mathcal{G}^{\prime}$. If $m\geq 500$ and $d\geq 600\log n$
then, with probability at least $1-1/n$, for every $i\in[n/m]$ one has that
the subgraph $G^{\prime}[S_{i}]$ is a $(1\pm 1/10)2d$-regular $1/3$-expander

###### Proof.

The statement follows from the following fact about Erdős-Rényi graphs, whose
proof is deferred to Section A.2.

######  Fact 7.10.

Let $N\geq 10$ be an integer and $p\in[0,1]$. Then, letting $\bar{d}=p(N-1)$
one has

$\Pr_{H=(U,F)\sim\operatorname*{ER}(N,p)}\left[\left(\Phi_{H}<\frac{1}{3}\right)\text{
or }\left(\exists u\in U\text{ s.t.
}\left|\deg_{H}(u)-\bar{d}\right|>\frac{1}{11}\bar{d}\right)\right]\leq
4N\cdot\exp\left(-\frac{pN}{600}\right)\,.$

In our case, each subgraph $G^{\prime}[S_{i}]$ is drawn from
$\operatorname*{ER}({m}/{2},4d/m)$, and note that $m/2\geq 250\geq 10$, thus
meeting the precondition of 7.10. Hence, for any $i\in[n/m]$ 7.10 gives

$\Pr\left[\left(\Phi_{G^{\prime}[S_{i}]}<\frac{1}{3}\right)\text{ or
}\left(\exists u\in S_{i}\text{ s.t.
}\left|\deg_{G^{\prime}[S_{i}]}(u)-2d\right|>\frac{1}{10}2d\right)\right]\leq
2m\cdot\exp\left(-\frac{d}{300}\right)\,,$

where we used $m\geq 500$ to express the degree bounds in terms of $2d$
instead of $\bar{d}$. Therefore, taking a union bound gives

$\Pr\left[\forall\,i\in[n/m]\,,\left(\Phi_{G^{\prime}[S_{i}]}\geq\frac{1}{3}\text{
and }\forall u\in
S_{i}\,,\left|\deg_{G^{\prime}[S_{i}]}(u)-2d\right|\leq\frac{1}{10}2d\right)\right]\geq
1-\frac{1}{n}\,,$

where we used $d\geq 600\log n\geq 600\ln n$. ∎

By virtue of the above, most of Alice’s inputs can be embedded into a sample
from $\mathcal{G}$ where a large fraction of important edges are inter-cluster
edges of any ED, as per Lemma 7.4. This will allow Alice and Bob to solve
$\operatorname*{\textsc{recover}}_{\epsilon m}$.

######  Reduction 7.11.

Let $\mathcal{A}$ be a deterministic streaming algorithm for computing a
$2$-level $(\epsilon,\phi)$-RED of a graph given in a stream of edges. For a
graph $G^{\prime}=(S,E^{\prime})\sim\mathcal{G}^{\prime}$, we reduce
$\operatorname*{\textsc{recover}}_{\epsilon m}$ to computing a $2$-level
$(\epsilon,\phi)$-RED as follows. Alice instantiates $\mathcal{A}$ for the
vertex set $V$, and feeds her edges $E^{\prime}$ and the fixed edges of $G[T]$
to $\mathcal{A}$. Then, she sends the memory state $\Pi$ of $\mathcal{A}$ to
Bob. Then, Bob instantiates $m/2$ copies of $\mathcal{A}$, call them
$\mathcal{A}_{1},\dots,\mathcal{A}_{m/2}$, and sets the memory state of them
to $\Pi$. Next, for each $k\in[m/2]$ let $G_{k}=(V,E_{k})$ be the graph
defined by $(G^{\prime},k)$, and note that Bob knows the edges between $S$ and
$T$ (see Definition 7.2). Then, Bob feeds the edges $E_{k}(S,T)$ to
$\mathcal{A}_{k}$. For each $k\in[m/2]$, let
$\mathcal{U}^{k}_{1},\mathcal{U}^{k}_{2}$ be the output of $\mathcal{A}_{k}$.
Bob finally constructs his output set $F$ as follows: for each $k\in[m/2]$, if
the number of non-isolated vertices in $\mathcal{U}^{k}_{2}$ is at most
$3\epsilon dn$, add the pair $\\{s,s_{i,k}\\}$ to $F$ for every $i\in[n/m]$
and every $s\in S_{i}$ that is not an isolated vertex in
$\mathcal{U}^{k}_{2}$. More formally, for a partition $\mathcal{U}$ of $V$,
let $V\setminus\mathcal{U}=\\{u\in V:\,\\{u\\}\notin\mathcal{U}\\}$ be the set
of non-isolated vertices in $\mathcal{U}$. With this notation, Bob outputs

$F=\bigcup_{k\in[m/2]:|V\setminus\mathcal{U}_{2}^{k}|\leq 3\epsilon
dn}F_{k}\,,\quad\quad\text{with
}F_{k}=\left\\{\\{s,s_{i,k}\\}:i\in[n/m],\,s\in
S_{i}\cap(V\setminus\mathcal{U}_{2}^{k})\right\\}\,.$ (7.5)

We remark that if Bob learns the important edges $E^{*}_{k}$ for all
$k\in[m/2]$, then he learns all of $E^{\prime}$.

######  Remark 2.

In the setting of 7.11, we have $E^{\prime}=\bigcup_{k\in[m/2]}E^{*}_{k}$ and
$|E^{\prime}|=\frac{1}{2}\sum_{k\in[m/2]}|E^{*}_{k}|$.

As suggested by Remark 2, it is enough to ensure that each instance
$\mathcal{A}_{k}$ recovers the important edges of $G_{k}$ in order for Bob to
learn the edges of $G^{\prime}$. We in particular restrict ourselves to
indices $k$ for which the algorithm $\mathcal{A}_{k}$, the graph $G_{k}$, and
the RED $\mathcal{U}_{1}^{k},\mathcal{U}_{2}^{k}$ are well behaved, as defined
below.

######  Definition 7.12.

In the setting of 7.11, for every $k\in[m/2]$ let $\mathcal{P}_{k}$ be the
property that

$\text{$\mathcal{U}_{1}^{k},\mathcal{U}_{2}^{k}$ is an $(\epsilon,\phi,2)$-RED
of
$G_{k}$}\,,\quad\left|E^{*}_{k}\setminus\mathcal{U}^{k}_{1}\right|\geq\frac{4}{5}\cdot\left|E^{*}_{k}\right|\,,\quad|E_{k}^{*}|\geq\frac{9}{5}\frac{dn}{m}\,,\quad|E_{k}|\leq
1.3dn\,.$ (7.6)

We first show a preliminary result: if there are many $k\in[m/2]$ that satisfy
$\mathcal{P}_{k}$, then Bob’s output set contains many edges of $G^{\prime}$.

######  Lemma 7.13.

In the setting of 7.11, if $\epsilon\in(0,1)$ satisfies
$\epsilon\leq\frac{1}{30\sqrt{m}}$, then

$|E^{\prime}\cap
F|\geq\frac{49}{100}\frac{dn}{m}|\\{k\in[m/2]:\mathcal{P}_{k}\\}|\,.$

###### Proof.

Recall from 7.11 that $F$ is made by the union of $F_{k}$ over $k\in[m/2]$. We
then first give a guarantee on the $F_{k}$’s individually.

######  Claim 7.14.

Let $k\in[m/2]$ such that $\mathcal{P}_{k}$ holds. Then

  1. 1.

$|V\setminus\mathcal{U}_{2}^{k}|\leq 3\epsilon dn$, and

  2. 2.

$|F_{k}\cap(E^{*}_{k}\setminus\mathcal{U}^{k}_{1})|\geq\frac{dn}{m}-\epsilon^{2}\cdot
1.3dn$.

###### Proof of (1).

Since $\mathcal{P}_{k}$ is verified, $\mathcal{U}_{1}^{k},\mathcal{U}_{2}^{k}$
is an $(\epsilon,\phi,2)$-RED of $G_{k}$ (see Definition 7.12). By definition
of RED (see Definition 3.2), we know
$|E_{k}\setminus\mathcal{U}^{k}_{1}|\leq\epsilon|E_{k}|$. Moreover, one can
note that the number of non-isolated vertices in $\mathcal{U}_{2}^{k}$ is at
most twice the number of edges in $E_{k}\setminus\mathcal{U}_{1}^{k}$. This is
because every non isolated vertex must have at least one edge incident on it
in $E_{k}\setminus\mathcal{U}_{1}^{k}$ (which is the input to the second level
ED), as otherwise property (2) of Definition 1.1 would be violated for any
$\phi>0$. Thus,

$|V\setminus\mathcal{U}_{2}^{k}|\leq 2|E_{k}\setminus\mathcal{U}^{k}_{1}|\leq
2\epsilon|E_{k}|\leq 3\epsilon dn\,,$

where the last inequality follows because $|E_{k}|\leq 1.3dn$ (see Definition
7.12). ∎

###### Proof of (2).

From part (1), together with the assumptions that
$\mathcal{U}_{1}^{k},\mathcal{U}_{2}^{k}$ is an $(\epsilon,\phi,2)$-RED of
$G_{k}$ and $|E_{k}|\leq 1.3dn$ (see Definition 7.12), we have

$\left|V\setminus\mathcal{U}^{k}_{2}\right|\leq 3\epsilon
dn\quad\text{and}\quad\left|E_{k}\setminus\mathcal{U}_{2}^{k}\right|=\left|\left(E_{k}\setminus\mathcal{U}_{1}^{k}\right)\setminus\mathcal{U}_{2}^{k}\right|\leq\epsilon\left|E_{k}\setminus\mathcal{U}_{1}^{k}\right|\leq\epsilon^{2}\cdot|E_{k}|\leq\epsilon^{2}1.3dn\,.$

We want to argue that many of the important edges $E^{*}_{k}$ of $G_{k}$ are
present in the set of pairs $F_{k}$ (see 7.11). To do this, we make the
following observation for any edge $\\{s,s^{\prime}\\}\in
E^{*}_{k}\setminus\mathcal{U}^{k}_{1}$: if none of $s,s^{\prime}$ is an
isolated vertex in $\mathcal{U}_{2}^{k}$, i.e.
$\\{s\\}\notin\mathcal{U}_{2}^{k}$ and
$\\{s^{\prime}\\}\notin\mathcal{U}_{2}^{k}$, then $\\{s,s^{\prime}\\}\in
F_{k}$; otherwise, if $\\{s\\}\in\mathcal{U}_{2}^{k}$ or
$\\{s^{\prime}\\}\in\mathcal{U}_{2}^{k}$, then
$\\{s,s^{\prime}\\}\in(E_{k}\setminus\mathcal{U}_{1}^{k})\setminus\mathcal{U}_{2}^{k}$
(and this is because $\mathcal{U}_{2}^{k}$ is an ED of the graph
$(V,E_{k}\setminus\mathcal{U}_{1}^{k})$ and $\\{s,s^{\prime}\\}\in
E_{k}\setminus\mathcal{U}_{1}^{k}$ by assumption). Therefore,

$\displaystyle|F_{k}\cap(E^{*}_{k}\setminus\mathcal{U}^{k}_{1})|\geq|E^{*}_{k}\setminus\mathcal{U}^{k}_{1}|-|(E_{k}\setminus\mathcal{U}_{1}^{k})\setminus\mathcal{U}_{2}^{k}|\,.$
(7.7)

To conclude the claim, we use again the property $\mathcal{P}_{k}$: since
$\mathcal{U}_{1}^{k},\mathcal{U}_{2}^{k}$ is an $(\epsilon,\phi,2)$-RED of
$G_{k}$, we have

$\left|(E_{k}\setminus\mathcal{U}_{1}^{k})\setminus\mathcal{U}_{2}^{k}\right|\leq\epsilon|E_{k}\setminus\mathcal{U}_{1}^{k}|\leq\epsilon^{2}\cdot|E_{k}|\,.$

Using again $\mathcal{P}_{k}$, we know
$|E^{*}_{k}\setminus\mathcal{U}^{k}_{1}|\geq\frac{4}{5}\cdot|E^{*}_{k}|$,
$|E_{k}^{*}|\geq\frac{9}{5}{dn}/{m}$, and $|E_{k}|\leq 1.3dn$, so from (7.7)
we conclude

$|F_{k}\cap(E^{*}_{k}\setminus\mathcal{U}^{k}_{1})|\geq|E^{*}_{k}\setminus\mathcal{U}^{k}_{1}|-|(E_{k}\setminus\mathcal{U}_{1}^{k})\setminus\mathcal{U}_{2}^{k}|\geq\frac{4}{5}\cdot|E^{*}_{k}|-\epsilon^{2}1.3dn\geq\frac{dn}{m}-\epsilon^{2}1.3dn\,.$
(7.8)

∎

From the definition of Bob’s output $F$ (see 7.11) and by Remark 2, one has

$\displaystyle|E^{\prime}\cap
F|=\left|\left(\bigcup_{k\in[m/2]}E_{k}^{*}\right)\cap\left(\bigcup_{k\in[m/2]:|V\setminus\mathcal{U}_{2}^{k}|\leq
3\epsilon dn}F_{k}\right)\right|$
$\displaystyle\geq\left|\bigcup_{k\in[m/2]:|V\setminus\mathcal{U}_{2}^{k}|\leq
3\epsilon dn}\left(E_{k}^{*}\cap F_{k}\right)\right|$ by Remark 2
$\displaystyle\geq\frac{1}{2}\sum_{k\in[m/2]:|V\setminus\mathcal{U}_{2}^{k}|\leq
3\epsilon dn}\left|E_{k}^{*}\cap F_{k}\right|\,,$

and we finish using 7.14:

$\displaystyle|E^{\prime}\cap F|$
$\displaystyle\geq\frac{1}{2}\sum_{k\in[m/2]:|V\setminus\mathcal{U}_{2}^{k}|\leq
3\epsilon dn}\left|E_{k}^{*}\cap F_{k}\right|$ by part (1) of 7.14
$\displaystyle\geq\frac{1}{2}\sum_{k\in[m/2]:\mathcal{P}_{k}\text{
holds}}\left|E_{k}^{*}\cap F_{k}\right|\,,$

and then

$\displaystyle|E^{\prime}\cap
F|\geq\frac{1}{2}\sum_{k\in[m/2]:\mathcal{P}_{k}\text{
holds}}\left|E_{k}^{*}\cap
F_{k}\right|\geq\frac{1}{2}\sum_{k\in[m/2]:\mathcal{P}_{k}\text{
holds}}\left|(E^{*}_{k}\setminus\mathcal{U}^{k}_{1})\cap F_{k}\right|\,,$

so by part (2) of 7.14 we have

$\displaystyle|E^{\prime}\cap
F|\geq\frac{1}{2}\sum_{k\in[m/2]:\mathcal{P}_{k}\text{
holds}}\left(\frac{dn}{m}-\epsilon^{2}\cdot
1.3dn\right)\geq\frac{49}{100}\frac{dn}{m}|\\{k\in[m/2]:\mathcal{P}_{k}\\}|\,,$

where we used $\epsilon\leq\frac{1}{30\sqrt{m}}$ in the last inequality. ∎

Finally, we prove that an efficient RED algorithm gives an efficient
$\operatorname*{\textsc{recover}}$ protocol, using the lemma we just showed.

######  Lemma 7.15.

Let $\epsilon,\phi\in(0,1)$ such that
$\epsilon\leq\min\\{10^{-5}\psi\frac{d}{m},\frac{1}{30\sqrt{m}}\\}$ and
$\phi\geq 11/m$. If $n\geq 100m$, $m\geq 500$, $d\geq 600\log n$, and there is
a deterministic $L$-bit space streaming algorithm $\mathcal{A}$ that computes
an $(\epsilon,\phi,2)$-RED with probability at least $9/10$ over inputs
$G\sim\mathcal{G}$, then there is a deterministic protocol that solves
$\operatorname*{\textsc{recover}}_{\epsilon m}$ with probability at least
$3/5$ over inputs $G^{\prime}\sim\mathcal{G}^{\prime}$ with communication
complexity at most $L$.

###### Proof.

The protocol is given by 7.11. We observe that the communication complexity
bound immediately follows, since $\mathcal{A}$ has space complexity $L$ by
assumption, and Alice only sends to Bob the state of the algorithm.

We now focus on proving correctness of the protocol with constant probability.
We do this by first proving that $F$ satisfies each of the two properties of
Definition 7.8 provided that some conditions hold, and then verify that such
conditions occur with constant probability.

######  Claim 7.16 (Property (1) of Definition 7.8).

If $\left|\left\\{k\in[m/2]:\,\mathcal{P}_{k}\right\\}\right|\geq\frac{m}{3}$,
then $|F|\leq 6\cdot\epsilon m|E^{\prime}|$.

######  Claim 7.17 (Property (2) of Definition 7.8).

If $\left|\left\\{k\in[m/2]:\,\mathcal{P}_{k}\right\\}\right|\geq\frac{m}{3}$,
then $|F\cap E^{\prime}|\geq 1/10\cdot|E^{\prime}|$.

######  Claim 7.18.

One has
$\Pr_{G^{\prime}\sim\mathcal{G}^{\prime}}\left[\left|\left\\{k\in[m/2]:\,\mathcal{P}_{k}\right\\}\right|\geq{m}/{3}\right]\geq{3}/{5}$.

By 7.16 and 7.17, the protocol given by 7.11 succeeds provided that the input
$G^{\prime}$ satisfies
$\left|\left\\{k\in[m/2]:\,\mathcal{P}_{k}\right\\}\right|\geq\frac{m}{3}$. By
7.18, the latter condition is verified with probability at least $3/5$. The
lemma statement is then proven, modulo showing 7.16, 7.16, and 7.18, which we
do next.

###### Proof of 7.16.

As per 7.11, $F$ is the union of $F_{k}=\\{\\{s,s_{i,k}\\}:i\in[n/m],\,s\in
S_{i}\cap(V\setminus\mathcal{U}_{2}^{k})\\}$ over $k$ such that
$|V\setminus\mathcal{U}_{2}^{k}|\leq 3\epsilon dn$. Note that
$|\\{\\{s,s_{i,k}\\}:i\in[n/m],\,s\in
S_{i}\cap(V\setminus\mathcal{U}_{2}^{k})\\}|$ is in fact upper-bounded by
$|V\setminus\mathcal{U}_{2}^{k}|$. One then gets that $|F|\leq 3\epsilon
dn\frac{m}{2}$. In order to relate this bound to $|E^{\prime}|$, we use our
assumption: for at least $m/3$ values of $k\in[m/2]$, $|E^{*}_{k}|\geq
9/5\cdot dn/m$. By Remark 2, this means $|E^{\prime}|\geq 1/2\cdot
m/3\cdot(9/5\cdot dn/m)=3/10\cdot dn$, so one concludes $|F|\leq
6\epsilon|E^{\prime}|m$. ∎

###### Proof of 7.17.

We can use Lemma 7.13, since our bound on $\epsilon$ ensures the precondition
of the lemma. We then have $|E^{\prime}\cap
F|\geq\frac{49}{100}\frac{dn}{m}|\\{k\in[m/2]:\mathcal{P}_{k}\\}|$. Now, we
conclude the claim by virtue of our assumption:

$|E^{\prime}\cap
F|\geq\frac{49}{100}\frac{dn}{m}|\\{k\in[m/2]:\mathcal{P}_{k}\\}|\geq\frac{m}{3}\frac{49}{100}\frac{dn}{m}\geq\frac{1}{10}|E^{\prime}|\,,$

where in the last inequality we used that our assumption further implies
$|E^{\prime}|\leq|E_{k}|\leq 1.3dn$ for some $k\in[m/2]$. ∎

###### Proof of 7.18.

We recall that for $G^{\prime}\sim\mathcal{G}^{\prime}$ and
$K\sim\operatorname{UNIF}([m/2])$ one has $(G^{\prime},K)\sim\mathcal{G}$ (see
Remark 1). For $k\in[m/2]$, we then interchangeably write $\mathcal{A}(G)$ and
$\mathcal{A}(G^{\prime},k)$ to refer to an execution of $\mathcal{A}$ on the
graph $G$ associated with $(G^{\prime},k)$. Our assumption on $\mathcal{A}$
rewrites as

$\Pr_{G^{\prime}\sim\mathcal{G}^{\prime},\,K\sim\operatorname{UNIF}([m/2])}\left[\text{$\mathcal{A}(G^{\prime},K)$
fails}\right]=\Pr_{(G^{\prime},K)\sim\mathcal{G}}\left[\text{$\mathcal{A}(G^{\prime},K)$
fails}\right]\leq\frac{1}{10}\,.$

Now recall 7.11: for each $k\in[m/2]$, the result of $\mathcal{A}_{k}$
computed by Bob is exactly $\mathcal{A}(G^{\prime},k)$, where $G^{\prime}$
denotes Alice’s input. Therefore, using that $G^{\prime}$ and $K$ are
independent and that $K$ is drawn uniformly, we get

$\operatorname{\mathbb{E}}_{G^{\prime}\sim\mathcal{G}^{\prime}}\left[\left|\left\\{k\in[m/2]:\text{
$\mathcal{A}_{k}$ fails
}\right\\}\right|\right]=\operatorname{\mathbb{E}}_{G^{\prime}\sim\mathcal{G}^{\prime}}\left[\left|\left\\{k\in[m/2]:\text{
$\mathcal{A}(G^{\prime},k)$ fails
}\right\\}\right|\right]\leq\frac{1}{10}\cdot\frac{m}{2}\,.$

Hence, if we sample $G^{\prime}\sim\mathcal{G}^{\prime}$, only a small
fraction of the values of $k$ will make $(G^{\prime},k)$ a failing instance.
Specifically, for any $\alpha\in[1/10,1]$, Markov’s inequality gives

$\Pr_{G^{\prime}\sim\mathcal{G}^{\prime}}\left[\left|\left\\{k\in[m/2]:\text{
$\mathcal{A}(G^{\prime},k)$ fails
}\right\\}\right|>\frac{1}{\alpha}\frac{1}{10}\cdot\frac{m}{2}\right]\leq\alpha\,.$

In other words, at least a $1-\alpha$ fraction of the probability measure of
$\mathcal{G}^{\prime}$ yields a graph $G^{\prime}$ such that $(G^{\prime},k)$
is a succeeding instance for $\mathcal{A}$ with at least a $1-0.1/\alpha$
fraction of the possible values for $k\in[m/2]$. By Lemma 7.9 (which applies
since we assume $m\geq 500$, $d\geq 600\log n$), we also have that a $1-1/n$
fraction of the measure of $\mathcal{G}^{\prime}$ yields a graph $G^{\prime}$
where each component is a $(1\pm 1/10)2d$-regular $\frac{1}{3}$-expander. This
in particular implies that at least a $1-\alpha-1/n$ fraction of the
probability measure of $\mathcal{G}^{\prime}$ yields a graph $G^{\prime}$ such
that:

  * •

for every $k\in[m/2]$, the graph $G_{k}=(V,E_{k})$ given by $(G^{\prime},k)$
has $|E_{k}|\leq 1.3dn$, by near-regularity and Definition 7.2;

  * •

for every $k\in[m/2]$, the graph $G_{k}=(V,E_{k})$ given by $(G^{\prime},k)$
has $|E^{*}_{k}|\geq\frac{9}{5}\frac{dn}{m}$, by near regularity and
Definition 7.2;

  * •

with at least a $1-0.1/\alpha$ fraction of the possible values for $k\in[m/2]$
we have the following: $\mathcal{A}_{k}$ outputs an $(\epsilon,\phi,2)$-RED
$\mathcal{U}^{k}_{1},\mathcal{U}^{k}_{2}$ of the graph $G=(V,E_{k})$ given by
$(G^{\prime},k)$. Moreover, by Lemma 7.4 (which applies, since our assumptions
on $n$, $m$, $\epsilon$, $\phi$ meet its preconditions) one has that
$\mathcal{U}_{1}^{k}$ verifies the property

$\left|E^{*}_{k}\setminus\mathcal{U}^{k}_{1}\right|\geq\frac{4}{5}\cdot\left|E^{*}_{k}\right|\,.$

We have then obtained that at least a $1-\alpha-1/n$ fraction of the
probability measure of $\mathcal{G}^{\prime}$ yields a graph $G^{\prime}$ such
that $\mathcal{P}_{k}$ holds for at least a $1-0.1/\alpha$ fraction of the
possible values for $k\in[m/2]$. Setting $\alpha=3/10$ gives the claim. ∎

∎

###  7.3 Hardness of the communication problem

We show that $\operatorname*{\textsc{recover}}_{\xi}$ requires linear
communication in the number of edges when $G^{\prime}\sim\mathcal{G}^{\prime}$
and $\xi=\epsilon m$. Intuitively, this is because Bob is only allowed to
output an $\approx\epsilon m$ factor more pairs than $|E^{\prime}|$, and for
an appropriate parameter regime $\epsilon
m|E^{\prime}|<\frac{1}{1000}\binom{m/2}{2}\frac{n}{m}$ (where
$\binom{m/2}{2}\frac{n}{m}$ is the total number of vertex pairs in a graph
consisting of $n/m$ disjoint subgraphs on $m/2$ vertices).

######  Lemma 7.19.

Let $\epsilon\in(0,1)$ such that $\epsilon\leq{10^{-33}}/{d}$. If $m\geq 500$
and $d\geq 600\log n$, then any deterministic protocol that solves
$\operatorname*{\textsc{recover}}_{\epsilon m}$ with probability at least
$3/5$ over inputs $G^{\prime}\sim\mathcal{G}^{\prime}$ requires $\Omega(dn)$
bits of communication.

###### Proof.

Let us fix hereafter $\mathcal{Q}$ to be a deterministic protocol that solves
$\operatorname*{\textsc{recover}}_{\epsilon m}$ with probability at least
$3/5$ over inputs $G^{\prime}\sim\mathcal{G}^{\prime}$. We define
$\mathcal{I}^{(1)}\subseteq\mathrm{supp}(\mathcal{G}^{\prime})$ to be the
subset of input graphs $G^{\prime}=(S,E^{\prime})$ in the support of
$\mathcal{G}^{\prime}$ such that $\mathcal{Q}$ outputs correctly on input
$G^{\prime}$. We also partition $\mathrm{supp}(\mathcal{G}^{\prime})$ based on
the number of edges, so for every integer $t$ we define
$\mathcal{I}_{t}\subseteq\mathrm{supp}(\mathcal{G}^{\prime})$ to be the subset
of graphs $G^{\prime}=(S,E^{\prime})\in\mathrm{supp}(\mathcal{G}^{\prime})$
with $|E^{\prime}|=t$. We also let for convenience
$\mathcal{I}^{(1)}_{t}=\mathcal{I}^{(1)}\cap\mathcal{I}_{t}$ be the subset of
correct graphs with $t$ edges. For any
$G^{\prime}=(S,E^{\prime})\in\mathrm{supp}(\mathcal{G}^{\prime})$, we denote
by $M_{G^{\prime}}\in\\{0,1\\}^{*}$ the message sent by Alice on input
$G^{\prime}$ using the protocol $\mathcal{Q}$.

######  Claim 7.20.

If $t$ is an integer such that $t\in[9/10\cdot dn/2,\,11/10\cdot dn/2]$ and
$|\mathcal{I}^{(1)}_{t}|\geq{1}/{2}\cdot|\mathcal{I}_{t}|$, then

$\textup{{H}}\left(M_{G^{\prime}}\,\middle|\,G^{\prime}\in\mathcal{I}_{t}^{(1)}\right)\geq\frac{dn}{3}\,.$

###### Proof.

For any $G^{\prime}\in\mathcal{I}^{(1)}_{t}$, following the reception of
$M_{G^{\prime}}$, Bob deterministically outputs at most $6\cdot(\epsilon
m)\cdot|E^{\prime}|=6\cdot\epsilon mt$ pairs of vertices
$F~{}\subseteq~{}\binom{S}{2}$, such that at least
$1/10\cdot|E^{\prime}|=t/10$ of them are actually edges of $G^{\prime}$. Thus,
for any $t$ and any message $M\in\\{0,1\\}^{\leq nm}$ (where we restrained
messages to be at most $nm$-bit long without loss of generality), the number
of $G^{\prime}\in\mathcal{I}^{(1)}_{t}$ such that $M_{G^{\prime}}=M$ is at
most

$\displaystyle\left|\left\\{G^{\prime}\in\mathcal{I}^{(1)}_{t}:\,M_{G^{\prime}}=M\right\\}\right|$
$\displaystyle\leq\sum_{j=0.1t}^{t}\binom{6\cdot\epsilon
mt}{j}\cdot\binom{\frac{n}{m}\binom{m/2}{2}}{t-j}$
$\displaystyle\leq\sum_{j=0.1t}^{t}\left(\frac{\mathrm{e}\cdot 6\cdot\epsilon
mt}{j}\right)^{j}\cdot\left(\frac{\mathrm{e}\cdot nm/8}{t-j}\right)^{t-j}$
$\displaystyle=\mathrm{e}^{t}\sum_{j=0.1t}^{t}\left(\frac{60\cdot\epsilon
mt}{t}\right)^{j}\cdot\left(\frac{nm/8}{t}\right)^{t-j}\cdot\left(\frac{t}{t-j}\right)^{t-j}\,.$

We employ the following fact to bound the above, whose proof is deferred to
Section A.3.

######  Fact 7.21.

For any $0<x\leq y$, $(y/x)^{x}\leq\mathrm{e}^{y/\mathrm{e}}$.

We apply 7.21 to the factor $(t/t-j)^{(t-j)}$ with $x=t-j$ and $y=t$, and
hence we get

$\displaystyle\left|\left\\{G^{\prime}\in\mathcal{I}^{(1)}_{t}:\,M_{G^{\prime}}=M\right\\}\right|$
$\displaystyle\leq\mathrm{e}^{(1+1/\mathrm{e})t}\sum_{j=0.1t}^{t}\left(60\epsilon
m\right)^{j}\cdot\left(\frac{nm/8}{t}\right)^{t-j}$ (7.9)
$\displaystyle=\mathrm{e}^{(1+1/\mathrm{e})t}\left(\frac{nm}{8t}\right)^{t}\sum_{j=0.1t}^{t}\left(60\cdot\frac{\epsilon
8t}{n}\right)^{j}$ (7.10)
$\displaystyle\leq\mathrm{e}^{(1+1/\mathrm{e})t}\left(\frac{nm}{8t}\right)^{t}\left({500}\cdot\frac{\epsilon
t}{n}\right)^{t/10}t\,,$ (7.11)

where in the last inequality we used the upper bounds on $\epsilon$ and $t$.
On the other hand, by virtue of our assumption that
$|\mathcal{I}_{t}^{(1)}|\geq{1}/{2}\cdot|\mathcal{I}_{t}|$, one has

$\displaystyle\left|\mathcal{I}^{(1)}_{t}\right|$
$\displaystyle\geq\frac{1}{2}\left|\left\\{G^{\prime}=(S,E^{\prime})\in\mathrm{supp}(\mathcal{G}^{\prime}):\,|E^{\prime}|=t\right\\}\right|$
(7.12)
$\displaystyle\geq\frac{1}{2}\left|\left\\{G^{\prime}=(S,E^{\prime})\in\mathrm{supp}(\mathcal{G}^{\prime}):\,\forall\,i\in[n/m],\,\left|E^{\prime}\cap\binom{S_{i}}{2}\right|=\frac{t}{n/m}\right\\}\right|$
(7.13)