On the Streaming Complexity of Expander Decomposition
Yu Chen Michael Kapralov Mikhail Makarov Davide Mazzali




























[1] ▹ #1





equationsection

countitems
nextitemizecount




AutoMultiColItemize
	>32
		
		
		>3


		@mpargs@captypexxx
		xxx 
		xxx 
		
	ifnextchar[@lab@nolab
	@lab[#1]#2 [#2 —#1]
	@nolab#1 [#1]













































































maincoractualCorollary
maincorsimpleCorollary
mainthsimpleTheorem
mainthactualTheorem
theoremTheorem[section]
definition[theorem]Definition
lemma[theorem]Lemma
*lemma*Lemma
*definition*Definition
corol[theorem]Corollary
claim[theorem]Claim
remarkRemark
fact[theorem]Fact
prop[theorem]Proposition
obs[theorem]Observation
assumpAssumption
reduct[theorem]Reduction
*reduct*Reduction








On the Streaming Complexity of Expander Decomposition
    
	Yu Chen

	EPFL

	Michael Kapralov

	EPFL

	Mikhail Makarov

	EPFL

	Davide Mazzali

	EPFL

    
================================================================================================

empty

In this paper we study the problem of finding (ϵ, ϕ)-expander decompositions of a graph in the streaming model, in particular for dynamic streams of edge insertions and deletions. The goal is to partition the vertex set so that every component induces a ϕ-expander, while the number of inter-cluster edges is only an ϵ fraction of the total volume. It was recently shown that there exists a simple algorithm to construct a (O(ϕlog n), ϕ)-expander decomposition of an n-vertex graph using O(n/ϕ^2) bits of space [Filtser, Kapralov, Makarov, ITCS'23]. This result calls for understanding the extent to which a dependence in space on the sparsity parameter ϕ is inherent. We move towards answering this question on two fronts.

We prove that a (O(ϕlog n), ϕ)-expander decomposition can be found using O(n) space, for every ϕ.  At the core of our result is the first streaming algorithm for computing boundary-linked expander decompositions, a recently introduced strengthening of the classical notion [Goranci et al., SODA'21]. The key advantage is that a classical sparsifier [Fung et al., STOC'11], with size independent of ϕ, preserves the cuts inside the clusters of a boundary-linked expander decomposition within a multiplicative error.

Notable algorithmic applications use sequences of expander decompositions, in particular one often repeatedly computes a decomposition of the subgraph induced by the inter-cluster edges (e.g., the seminal work of Spielman and Teng on spectral sparsifiers [Spielman, Teng, SIAM Journal of Computing 40(4)], or the recent maximum flow breakthrough [Chen et al., FOCS'22], among others). We prove that any streaming algorithm that computes a sequence of (O(ϕlog n), ϕ)-expander decompositions requires Ω(n/ϕ) bits of space, even in insertion only streams.


empty



plain



§ INTRODUCTION

Expander graphs are known to represent a class of easier instances for many problems. Therefore, breaking down the input into disjoint expanders can allow to conveniently solve the task on each of them separately, before combining the partial results into a global solution. This approach is enabled by (ϵ, ϕ)-expander decompositions (for short, (ϵ, ϕ)-ED). For an undirected graph G=(V,E), this is a partition 𝒰 of the vertex set V, such that there are at most ϵ |E| inter-cluster edges, while every cluster U ∈𝒰 induces a ϕ-expander. The list of successful applications of this framework is long, including Laplacian system solvers <cit.>, deterministic algorithms for minimum cut <cit.>, graph and hyper-graph sparsification <cit.>, dynamic algorithms for cut and connectivity problems <cit.>, fast max flow algorithms <cit.>, distributed triangle enumeration <cit.>, polynomial time algorithms for semirandom planted CSPs <cit.>, and many more.

We refer to ϵ and ϕ as the sparsity parameters: the former controls how sparsely connected the clusters need to be, and the latter determines how expanding (i.e. non-sparse) the cuts within clusters are. The reason for using the same term for both is that they are in fact very closely related. One can show that any n-vertex graph has an (ϵ,ϕ)-ED with ϵ = O(ϕlog n). To see this, consider the following constructive argument: if the graph has no ϕ-sparse cut then {V} is a valid ED of G, otherwise recurse on the two sides (S,V ∖ S) of a ϕ-sparse cut and union the results to get an ED for G. Every cluster in this decomposition is then an expander, and a charging argument allows to bound the number of inter-cluster edges by O(ϕ |E| log n) <cit.>. One can also observe that no better asymptotic trade-off between ϵ and ϕ is possible in general <cit.>. Therefore, this sets the benchmark for algorithmic constructions of EDs.

At a high level, many ED algorithms follow the approach suggested by the existential argument. As a naive implementation would take exponential time, the crux often lies in efficient algorithms that either certify that a large portion of the input is an expander, or find a balanced sparse cut. This would result in a small depth recursion, thanks to balancedness, where each level requires little computational resources. There are several successful examples of this approach. In the sequential setting, a recent algorithm constructs a (O(ϕlog^3 n), ϕ)-ED in (|E|) time <cit.>, based on the previous best algorithm which runs in (|E|/ϕ) time <cit.>. There is also a deterministic counterpart, which outputs a (ϕ· n^o(1), ϕ)-ED in almost linear time <cit.>. For the CONGEST model of distributed computing, it is possible to obtain, for instance, a (ϕ^1/√(log n)· n^o(1), ϕ)-ED in n^o(1) / ϕ rounds <cit.>. It is also possible to maintain a (ϕ· n^o(1),ϕ)-ED for a graph undergoing edge updates in n^o(1)/ϕ^2 amortized update time <cit.>.



 §.§ Previous work

In the streaming setting, the problem of finding EDs was open until the recent work of <cit.>. They obtain a dynamic stream algorithm which outputs a (O(ϕlog n),ϕ)-ED and takes (n/ϕ^2) space. While being optimal in the quality of the decomposition, decoding the sketch to actually output an ED takes exponential time. The authors also give a polynomial time version: one can produce a (ϕ· n^o(1), ϕ)-ED using space (n/ϕ^2)+n^1+o(1)/ϕ^1-o(1), with a post-processing that takes (n) time (where the o(1)'s can be tuned, allowing for a quality-space trade-off).

These streaming algorithms also adopt the recursive approach based on finding balanced ϕ-sparse cuts, but the streaming model poses a challenge that we now illustrate. Sparsification for graph streams has been extensively studied <cit.>, so a natural attempt would consist of maintaining a cut sparsifier as the stream comes and later run the recursive partitioning on it. However, it must be noted that these cuts are to be found in the subgraphs induced by the two sides of a previously made cut. This is not a problem in a classical computational setting, but it actually constitutes the main obstacle for the streaming model: at sketching time, the algorithm does not know which subgraphs it will need to access. Unfortunately, it is impossible to preserve cut sizes in arbitrary subgraphs with multiplicative precision. The natural work-around is to introduce an additive error term: in <cit.>, the authors introduce the concept of power-cut sparsifiers. For any given partition 𝒰 of V, these sparsifiers preserve the cuts |E(S,U∖ S)| of each cluster U ∈𝒰 in the partition up to an error of δ· |E(S,U∖ S)| + ψ·(S). They further show that maintaining (n / δψ) random linear measurements of the incidence matrix of the input graph is enough to obtain such sparsifiers. One can see that setting δ≪ 1 and ψ≈ϕ preserves the sparsity of cuts to within an additive error of roughly ϕ, using (n/ϕ) linear measurements. This is enough to find a balanced ϕ-sparse cut in every subgraph induced by a given partition of the vertex set. There is another caveat, though: power-cut sparsifiers give a high probability guarantee for any fixed partition, but we cannot expect them to work for all partitions simultaneously. Therefore, in order not to use the sparsifiers adaptively, we need one power-cut sparsifier for every recursion level. The authors show that the depth of the procedure cannot exceed (1/ϵ) = (1/ϕ), thus obtaining the space complexity stated before. A few more details are involved in the polynomial time algorithm, but the underlying framework is the same.



 §.§ Our contribution

The work of <cit.> initiated the study of expander decompositions in the streaming setting, and consequently raised the question of whether a dependence in space on the sparsity parameter ϕ is inherent. In this paper, we move towards settling the streaming complexity of expander decompositions by attacking the problem on two fronts: (1) we give a nearly optimal algorithm for “one-level” expander decomposition that avoids the sparsity dependence, and (2) we show that computing a “repeated” expander decomposition, commonly used in applications, cannot avoid such dependence.


  §.§.§ Upper bound

We give an (n) space algorithm for computing a (O(ϕlog n), ϕ)-ED in dynamic streams. Specifically, we show that a “universal” sketch consisting of (n) random linear measurements of the incidence matrix can be decoded into a (O(ϕlog n), ϕ)-ED for any ϕ: the sketch is independent of the sparsity ϕ.

[ED algorithm – exponential time decoding]
	
	Let G=(V,E) be a graph given in a dynamic stream. Then, there is an algorithm that maintains a linear sketch of G in (n) space. For any ϕ∈ (0,1), the algorithm decodes the sketch to compute a (O(ϕlog n), ϕ)-ED of G with high probability, in (n) space and 2^O(n) time.


We note that at least Ω(nlog n) space is needed for any small enough ϕ: for example, if the input graph is a matching of size n/10, say, its ED gives a 1-O(ϕlog n) fraction of the matching edges. 

The decoding time of our sketch can be made polynomial, at the expense of some loss in the quality of the expander decomposition (similarly to <cit.>), but keeping the space independent of the sparsity ϕ.

[ED algorithm – polynomial time decoding]
	
	Let G=(V,E) be a graph given in a dynamic stream. Then, there is an algorithm that maintains a linear sketch of G in n^1+o(1) space. For any ϕ∈ (0,1), the algorithm decodes the sketch to compute a (ϕ· n^o(1), ϕ)-ED of G with high probability, in n^1+o(1) space and (n) time.


In this case we are off by subpolynomial factors in both quality and space complexity as compared to the optimal ones. The actual theorem that we prove allows one to trade-off the loss in quality and increase in space.



  §.§.§ Lower bound

Most algorithmic applications of EDs, including the ones mentioned above, do not use just one ED of the input graph. Rather, they use an ED sequence obtained by repeatedly computing an ED of the inter-cluster edges from the previous level. This can be done in two natural ways: by contracting the clusters of an ED (we call this variant CED, for “contraction”), or by removing the intra-cluster edges without changing the vertex set (we call this variant RED, for “removal”). These approaches lead to different results and are used for different applications (e.g., <cit.> contract the clusters, and <cit.> recurse on inter-cluster edges). In the sequential setting, both CEDs and REDs can be obtained straightforwardly given an ED algorithm. However, this is not so obvious in the streaming model.

One the one hand, one should be able get a sparsity-independent algorithm for computing CEDs in dynamic streams via <ref> or <ref>: observe that contracting the vertices of a sparsifier of the input graph G  gives a sparsifier of the graph obtained by contracting vertices in G, so the idea would be to maintain an independent copy of our algorithm for each of the O(log n) levels and contracting vertices in the sparsifier based on the decomposition of the previous level. On the other hand, we show a space lower bound for computing REDs, even in insertion only streams, showing that a dependence on 1/ϕ is necessary.

[RED lower bound]
	
	Let ϵ,ϕ∈ (0,1) such that 1/n ≪ϕ≪ 1/ n and ϵ =( ϕ). Any streaming algorithm that with constant probability computes at least two levels of an (ϵ,ϕ)-RED requires Ω(n/ϕ) bits of space.


The result seems to challenge the intuition that EDs become weaker as ϕ and ϵ decrease (note that when ϕ is, say, 1/n^2, an ED can simply consist of connected components). The questions of (1) whether this bound can be improved, (2) how it scales with the number of levels of RED we compute, and (3) whether there are algorithms matching such bounds, remain open.



 §.§ Basic notation





  
Graph streaming. In this paper, we will be mostly working in the dynamic graph streaming model, where we know the vertex set V=[n], and we receive a stream of insertions and deletions for undirected edges over V. In insertion-only graph streams, the only difference is that previously inserted edges cannot be deleted. At the end of the stream, the graph G=(V,E) consists of the edges that have been inserted and not deleted, and we say that G is given in a (dynamic) stream. When we consider a graph given in a (dynamic) stream, we are implicitly assuming it to have n vertices, without introducing the parameter n explicitly. Also, when we refer to G and n without reintroducing them we are implicitly considering the graph resulting from the input stream and its number of vertices.

A powerful tool for dynamic graph streams is linear sketching, introduced in the seminal work of Ahn, Guha, and McGregor <cit.>. The idea is to left-multiply the n2× n incidence matrix of the graph by a random k ×n2 matrix for k ≪n2. Since the sketch consists of linear measurements, it automatically handles the case of dynamic streams. We will not be using sketching techniques directly, but rather employ existing algorithms that do. In this paper we restrain ourselves to unweighted edge streams. One may study the same problem in general turnstile graph streams <cit.>, but we do not do this here.



  
Cuts, volumes, expanders. Given an unweighted graph G=(V, E), possibly with multiple self-loops on the vertices, we will operate with weighted graphs that approximate G in an appropriate sense. We write G'=(V',E', w) to denote a weighted graph, possibly with multiple weighted self-loops on the vertices. We describe next some notation for such weighted graph G'. The same notation carries over to the unweighted graph G by implicitly setting w to assign a weight of 1 to all edges and self-loops.

For any A,B ⊆ V' we denote by E'(A,B) the edges in E' with one endpoint in A and one in B, and by w(A,B) the total weight of edges in E'(A,B). The volume of a cut S ⊆ V' is the sum of the (weighted) degrees, including self-loops, of its vertices. We denote it by _G'(S). The sparsity of a cut ∅≠ S ⊊ V' is defined as

    Φ_G'(S) = w(S,V' ∖ S)/min{_G'(S), _G'(V' ∖ S)}  .

For ψ∈ (0,1), we make a distinction between cuts having sparsity less than ψ, which we call ψ-sparse, and cuts having sparsity at least ψ, which we call ψ-expanding. The sparsity of G' is the defined as

    Φ_G' = min_∅≠ S ⊊ V'Φ_G'(S)   ,

and we call G' a ψ-expander if all its cuts are ψ-expanding, i.e. Φ_G'≥ψ.

For a pair of vertices e={u,v}∈V'2, we denote by λ_e(G') the edge connectivity of e in G', i.e.

    λ_e(G') = min_∅≠ S ⊊ V'  : u ∈ S, v ∈ V' ∖ S w(S,V'∖ S)   .




  
Expander decomposition. As we will treat expander decompositions for the input graph G only, we conveniently use the following additional notation. For a cluster U ⊆ V, i.e. a subset of the vertices, and a cut S ⊆ U, which is also a subset of the vertices, we denote the number of edges crossing S in U by SU, i.e. SU=|E(S,U ∖ S)|. This is the local cut of S in U. If U = V, we use a shorthand notation SSV. We call such a cut the global cut of S, since for S ⊆ U we will be interested in both SU and S. Moreover, we drop the subscript from the volume and simply write (·) instead of _G(·). Then, EDs can be defined as follow.


	
	Let G=(V,E) and let ϵ, ϕ∈ (0,1). A partition 𝒰 of V is an (ϵ, ϕ)-expander decomposition (for short, (ϵ, ϕ)-ED) of G if
	
		
  *  1/2∑_U ∈𝒰U≤ϵ |E|, and
		
  *  for every U ∈𝒰, one has that G[U] is a ϕ-expander.
	




§ TECHNICAL OVERVIEW

In this section, we outline our techniques, and give intuition for how to prove our results.


 §.§ Sparsity-independent one-level expander decomposition


Given a graph G=(V,E) in a  dynamic stream, and a parameter ϕ∈ (0,1), we consider the problem of computing an (ϵ, ϕ)-ED of G for ϵ = O(ϕlog n). We show that one can do this in (n) bits of space, without any dependence on ϕ.
In this section, we sketch our approach.

Let us begin by recalling the standard recursive framework for constructing expander decompositions <cit.>, concisely summarized in <ref>. For any parameter ϕ≤ 10^-1/log n, this algorithm produces a (O(ϕlog n), ϕ)-ED by recursively partitioning G along ϕ-sparse cuts until no more such cuts are found.



Many algorithmic constructions of EDs are essentially efficient implementations of <ref>. Adapting <ref> to dynamic streams comes with its own set of challenges.
When the input is given in a dynamic stream, one can only afford to store a limited amount of information about the input graph. Since <ref> only needs to measure the sparsity of cuts, it seems enough to have access to cut sizes and volumes. Both these quantities are preserved by cut sparsifiers. According to the classical definition <cit.>, a δ-cut sparsifier is a weighted subgraph H=(V,E',w) of the input G=(V,E), where for every cut S ⊆ V one has

    (1-δ)·S≤S≤ (1+δ) ·S  .

It is known that such a sparsifier can be constructed in dynamic streams using (n/δ^2) bits of space <cit.>. With the same space requirement we can also measure the sparsity of cuts up to a (1±δ) multiplicative error. Having this in mind, it is natural to consider the following algorithm: first, read the stream and construct a cut sparsifier, then run <ref> on it and output the resulting clustering as the expander decomposition. However, this approach does not work as is. As it turns out, more information is needed about the graph than what is captured by the regular notion of a cut sparsifier.

The problem with this approach becomes immediately apparent when one considers the second recursion level. As the process recurses on the two sides of a sparse cut S, it will repeat the procedure on the subgraphs G[S] and G[V ∖ S]. Unfortunately, the cut preservation property of the sparsifier does not carry over to those subgraphs, making it inadequate for estimating the sparsity of the cuts in those graphs. 
In fact, the notion of expander decomposition itself already operates on the subgraphs, as it is required that each cut in each cluster of the decomposition is expanding.



  §.§.§ Testing expansion of subgraphs

The reasoning from above gives rise to the following sketching problem: produce a sparsifier that can be used to check that any subgraph is a ϕ-expander. To solve it, the authors of <cit.> introduced the concept of a (δ,ψ)-power-cut sparsifier. Its property is that, for any cluster U ⊆ V, with high probability all cuts S ⊆ U are preserved within an additive-multiplicative error.
Recall that SU is equal to the size of the cut S inside the induced subgraph G[U].
When talking about sparsifiers in this section, we will slightly abuse notation by assuming that there is some instance H=(V,E',w) of it and denote by SU the size of the cut S in the subgraph H[U] of this sparsifier H. Then we can write the guarantee of a (δ, ψ)-power-cut sparsifier as follows[A similar sparsifier construction was proposed by <cit.>. Their construction has an additive error of ψ |S|, so the dependence is on the number of vertices instead of the volume]:

    ∀  S ⊆ U,     (1-δ)·SU-ψ·(S) ≤SU≤ (1+δ)·SU+ψ·(S)   .

The authors also give a dynamic stream construction, which uses (n/δψ) bits of space by sampling edges proportionally to the degrees of their endpoints.


To check the ϕ-expansion of subgraphs up to a small constant multiplicative error, it is enough to set δ to be a small constant. However, the multiplicative error parameter ψ must be ≲ϕ. 
This is a significant downside of this construction, as it was shown in <cit.> that a (δ, ϕ)-power-cut sparsifier must have at least Ω(n /ϕ) edges. In fact, their lower bound is more general, and holds for general subgraphs[The lower bound instance is a 1/ϕ-regular graph. There, each edge by itself forms a ϕ-expander, while any pair of vertices without an edge between them is not. Being able to test the ϕ-expansion of the majority of those small subgraphs would imply being able to recover the majority of edges in the graph.].
In other words, Ω(n/ϕ) space is necessary in order to test ϕ-expansion of general subgraphs. Consequently, new tools must be used to have any hope of getting an algorithm independent of 1 / ϕ.



  
*Our contribution: sparsification of boundary-linked subgraphs

As it turns out, solving the expansion testing problem, as it was stated, is not necessary. Recently, in the breakthrough work of <cit.>, it was shown that one could demand additional properties from the expander decomposition, and it will still exist at the price of increasing the number of inter-cluster edges by a small multiplicative factor.

More formally, for a set of vertices U ⊆ V and τ > 0, we denote by G[U]^τ an induced subgraph of G on U, where additionally for each edge e={u,v} that connects a vertex u inside U with a vertex v outside of U, τ self-loops are added to u. The graph G[U]^τ is called a τ-boundary-linked subgraph. Note that if G[U]^τ is a ϕ-expander, then so necessarily is G[U], but not the other way around.


Then it is possible, for a given ϕ, and = (ϕ),  τ≈ 1/ϕ, to construct an (, ϕ)-expander decomposition 𝒰 where for each cluster U ∈𝒰, G[U]^τ is a Ω(ϕ)-expander <cit.>. Such a decomposition is called a boundary-linked expander decomposition.

A key observation is that if in our algorithm we were aiming to construct a boundary-linked expander decomposition, the testing problem would only involve checking that any given boundary-linked subgraph is ϕ-expanding. Indeed, this problem is much easier than the original one and can be solved in space (n). We will show how to do it in two steps: first, we will discuss how to strengthen the power-cut sparsifier, and then prove that this strengthening is enough to resolve the problem.



  
*Achieving additive error in the global cut
As was noted in <cit.>, the idea behind constructing a power-cut sparsifier was to reanalyse the guarantee given by the construction of <cit.> for sparsifying expanders. In other words, a power-cut sparsifier results from a more rigorous analysis of an existing sparsifier. The problem with this approach is that the sparsifier of <cit.> is relatively weak to begin with: it only preserves cuts in expanders, while other constructions can preserve them in all graphs <cit.>.
To strengthen the guarantee, we give the same treatment to the construction of <cit.> in <ref>. For the sake of simplicity and to gain an intuition for why this kind of sparsification is at all possible, we discuss here how to do that with the classical construction of <cit.> by closely following the original proof.

We show that, given a graph G=(V, E) with a minimum cut of size k, it is possible to construct a sparsifier H of G such that every cut inside any given subgraph G[U] of G is preserved with high probability with the following guarantee:

    ∀  S ⊆ U,   SU - δ·S≤SU≤SU + δ·S .

In this paper, a sparsifier with property (<ref>) is called a cluster sparsifier (see <ref>).
To achieve (<ref>), consider using the same process as in <cit.>: sample each edge with the same probability p ≈δ^-2/ k.

To see why this works, fix a subgraph U ⊆ V, and consider any cut S in U. 
We wish to show that the size of the cut S inside U concentrates well after sampling. In the original proof, this is done by simply applying a Chernoff bound. In our case, this bound would look like this:

    [|SU - SU| ≥δ·SU] ≤exp(-1/3δ^2 p ·SU)   .

However, this is insufficient, as the probability depends on the cut size inside G[U]. As we have no lower bound on its size, unlike with the sizes of global cuts, the second part of the argument of <cit.> cannot be applied. Instead, we apply an additive-multiplicative version of the Chernoff bound (see for example <cit.>), that allows us to compare the approximation error with a bigger value than its expectation. This gives us

    [|SU - SU| ≥δ·S] ≤ 2exp(-1/100δ^2 p ·S)   .

Expressing the probability in terms of the global cut allows us to use the cut counting lemma <cit.>, which bounds the number of global cuts of size at most α k by n^2α,  for α≥ 1. The proof is concluded by associating each global cut with a local cut in G[U] and taking the union bound over them.

In order to get the guarantee of (<ref>) for all graphs, not only those with a minimum cut of size k, one can sample edges proportionally to the inverse of their connectivity (as in the work of <cit.>) as opposed to uniformly. Moreover, one can implement such sampling scheme in dynamic streams, using the approach of Ahn, Guha, and McGregor <cit.>. We defer the details of these reanalyses to <ref>, where we show how to construct cluster sparsifiers with property (<ref>) in dynamic streams.



  
*Benefits of boundary-linked graphs
To see why the cluster sparsifier is enough to solve the boundary-linked ϕ-expansion testing problem, consider the following reasoning. Set the self-loop parameter τ equal to b / ϕ, for some b ≫ϕ and b ≪ 1. Fix a cluster U, for which G[U]^b / ϕ is an Ω(ϕ)-expander. 
The crucial fact is that the size of any cut inside G[U]^b / ϕ is lower bounded by its size in the global graph up to a small polylogarithmic factor in the following way:

    SU≥Ω(b) ·S  .

We will now explain the derivation of the above equation in detail.
For a cut ∅≠ S ⊊ U, we denote by SU = S - SU the number of edges going from S to V ∖ U. Note that by the definition of G[U]^b / ϕ, the volume of any cut S inside of it is equal to _G[U]^b / ϕ(S) = (S) + (b/ϕ - 1)SU.
First, because we assume that G[U]^b / ϕ is an Ω(ϕ)-expander, we have

    SU≥Ω(ϕ)·_G[U]^b / ϕ(S) .

Then, applying the aforementioned formula for _G[U]^b / ϕ(S), we have

    SU≥Ω(ϕ)(S) + Ω(ϕ)(b/ϕ -1 )SU .

Since b ≫ϕ and dropping the first summand, the above simplifies to 

    SU≥Ω(b)SU .

Finally, applying SU + SU = S and b ≪ 1, we arrive back at equation (<ref>).

A consequence of equation (<ref>) is that setting δ≈ 1/ b in the cluster sparsifier produces the following guarantee for Ω(ϕ)-expander subgraphs G[U]^b / ϕ: 

    ∀  S ⊆ U,   SU - O(1) ·SU≤SU≤SU + O(1) ·SU ,

where the O(1) can be made arbitrarily small. In other words, we achieve a multiplicative approximation guarantee on subgraphs of interest, which is enough to solve the testing problem. Since b can be set to be 1/ n, the final sparsifier size does not depend on 1/ϕ. In this sense, such sparsifier can be thought of as a “universal” sketch of the graph that allows to solve the testing problem for all ϕ simultaneously.

Even though we now know how to solve the testing problem, an implementation of <ref> would need to actually find a sparse cut when the test fails (and in particular, it needs to find a balanced sparse cut, see the next section). In <ref>, we show that cluster sparsifiers enable to solve this harder task too: consider an offline algorithm that either correctly determines a graph to be a boundary-linked expander or finds a (balanced) sparse cut; we show that one can run such algorithm on a subgraph of the sparsifier as a black box and obtain essentially the same result as if the algorithm was run on the corresponding subgraph of the original graph. In this sense, cluster sparsifiers serve as small error proxies to the original graph for expander-vs-sparse-cut type of queries on vertex-induced subgraphs.



  §.§.§ Low depth recursion

Another problem that arises when using the recursive approach is that the subgraph sparsification guarantee of both power-cut sparsifiers and cluster sparsifiers is only probabilistic, and it can be shown that it cannot be made deterministic <cit.>. This means that after finding a sparse cut S in a subgraph G[U]^b / ϕ of a sparsifier, we cannot claim that the same sparsifier would preserve the cuts inside the new graph G[S]^b / ϕ with high probability, as it is dependent on another cut that we have already found inside the sparsifier. This means we cannot use the same sparsifier for two different calls to <ref> inside the same execution path.
However, we can share a sparsifier among all the calls at the same recursion level since these will operate on independent portions of G. Therefore, we want to have a separate sparsifier for every recursion level. This means that in order to minimize space requirements, it is crucial to have a small recursion depth.

To have small recursion depth, the algorithmic approach of <cit.> enforces the sparse cut S from line (<ref>) to be balanced, i.e., none of S and V∖ S is much larger than the other. In particular, they only recurse on the two sides of a cut if (S) ≳ϵ(V ∖ S). 
When there is no balanced sparse cut and yet the input is not an expander, a lemma of Spielman and Teng <cit.> suggests there should be an Ω(ϕ)-expander G[S'] that accounts for a (1-O(ϵ))-fraction of the total volume. An algorithmic version of this structural result allows us to iteratively trim off a small piece of the graph until such S' is found. At this point, the algorithm of <cit.> can simply return {S'}∪ (∪_u ∈ V ∖ S'{u}) as an ED, with at most O(ϵ|E|) inter-cluster edges between singletons. As the volume of the cluster multiplicatively decreases by 1 - O() after each call, this gives recursion depth at most (1/ϵ) ≈(1/ϕ).



  
Our contribution: adaptation of trimming. We show that a simple refinement of this approach allows us to adapt the framework of <cit.>, which leads to an algorithm with recursion depth independent of  ϕ. We run the same algorithm, but instead of separating each vertex in V ∖ S' into its own singleton cluster, we recurse with <ref> on the whole set V ∖ S'. Conceptually, this implements an analogue of the trimming step of <cit.>.

This means that at the end, fewer edges in V ∖ S become inter-cluster edges. Because of that,
we can strengthen the balancedness requirement: we recurse on the two sides of a sparse cut only if (S) ≳1/C(V ∖ S) for a large constant C. This allows us to trim more vertices each time, resulting in (1) depth of the trimming step.  On the other hand, because in each call to <ref> the volume of clusters passed to recursive calls is decreased by at least a constant factor, the total recursion depth becomes at most (1).

Other than the refinement discussed above, our space efficient implementation of <ref>, as well as  the iterative procedure to find the large expander S', are almost the same as the ones of <cit.> (which in turn are  inspired by the one of <cit.>). The details of the algorithms are given in <ref>.



  §.§.§ Putting it all together

Combining the ideas illustrated in the two sections above, neither the sparsifier's size nor the recursion depth depend on ϕ, thus giving a sparsity-independent space algorithm for boundary-linked expander decomposition  (BLD for short). This result is stated in terms of parameters b,ϵ,ϕ∈ (0,1),  γ≥ 1: a (b, ϵ, ϕ, γ)-BLD is a partition 𝒰 with  at most an ϵ fraction of crossing edges and every U ∈𝒰 induces a ϕ/γ-expander G[U]^b/ϕ (see <ref> and <ref>). Using this terminology, we obtain the following result.

[Exponential time decoding BLD]theoremmainbld
	
	Let G=(V, E) be a graph given in a dynamic stream, and let b ∈ (0,1) be a parameter such that b ≤ 1/log^2 n. Then, there is an algorithm that maintains a linear sketch of G in (n/b^3) space. For any ϵ∈ [n^-2, b log n], the algorithm decodes the sketch to compute, with high probability and in (n/b^3) space and 2^O(n) time, a (b, ϵ, ϕ, γ)-BLD of G for
	
    ϕ = Ω(ϵ/log n)    and   γ = O(1)   .


From this, one can easily conclude our main result, restated here for convenience of the reader.

[ED algorithm – exponential time decoding]
	
	Let G=(V, E) be a graph given in a dynamic stream. Then, there is an algorithm that maintains a linear sketch of G in (n) space. For any  ϕ∈ (0, 1) such that ϕ≤ c/log^2 n for a small enough constant c>0, the algorithm decodes the sketch to compute a (O(ϕlog n), ϕ)-ED of G with high probability, in (n) space and 2^O(n) time.

We remark that for ϕ≥Ω(1/log^2n), one can use the algorithm of <cit.> to still have an (n) space construction of a (O(ϕlog n), ϕ)-ED.

	First note that without loss of generality we can assume ϕ≥ 1/n^2, otherwise an ED can simply consists of the connected components of G (which can be computed in dynamic streams in (n) space <cit.>). Then, we note that since c is small enough and ϕ≤ c / log^2 n, one can always define ϵ = C ·ϕ·log n for an appropriate constant C>0 while ensuring 1/n^2 ≤ϵ≤ 1/log n. We can thus prove the theorem by equivalently showing that there is an algorithm that maintains a linear sketch of G in (n) space, and that for all ϵ∈ [1/n^2,1/log n] decodes the sketch to compute, with high probability, an (ϵ, Ω(ϵ / log n)))-ED of G in (n) space and 2^O(n) time.
	
	Let then ϵ∈ [1/n^2,1/log n]. We use the algorithm from <ref> with parameter ϵ and a parameter b of our choice. We need to meet two preconditions: b ≤ 1/log^2 n and ϵ≤ b log n. Since we assume ϵ≤ 1/log n, we can set b=1/log^2 n, and all the prerequisites are fulfilled. Then the algorithm from <ref> runs in 2^O(n) time and takes (n/b^3)=(n) bits of space. The output 𝒰 is a (b, ϵ, ϕ, γ)-BLD of G with high probability, where ϕ = Ω(ϵ/log n) and γ =O(1). Since a (b, ϵ, ϕ, γ)-BLD of G is an (ϵ,ϕ/γ)-ED of G, we have obtained an (ϵ, Ω(ϵ/log n))-ED of G with high probability.

The exponential time in the decoding is due to the subtask of finding a balanced sparse cut. As we show, one can make the decoding time polynomial by resorting to known offline approximation algorithms <cit.>. However, we only have log^Ω(1) n-approximations for finding a balanced sparse cut, and in particular, we do not expect (under NP-hardness and the Unique Games Conjecture) there to be a polynomial time O(1)-approximation <cit.>. Such super-constant factor error incurs some loss in the quality of decomposition and space requirement, which, nevertheless, remains independent of the sparsity.


[Polynomial time decoding BLD]theoremmainbldpoly
	
	Let G=(V, E) be a graph given in a dynamic stream, and let b ∈ (0,1) be a parameter such that b ≤ 1/log^5 n. Then, there is an algorithm that maintains a linear sketch of G in n/b^3 ·log^O(log n / log1/b) n space. For any ϵ∈ [n^-2, b log n], the algorithm decodes the sketch to compute, with high probability and in n/b^3 ·log^O(log n / log1/b) n space and (n) time, a (b, ϵ, ϕ, γ)-BLD of G for
	
    ϕ = Ω(ϵ/log^4 n)    and   γ = log^O(log n/log 1/b) n  .


<ref>, restated here for convenience, then follows from <ref>.

[ED algorithm – polynomial time decoding]
	
	Let G=(V, E) be a graph given in a dynamic stream, and let b ∈ (0,1) be a parameter such that b ≤ 1/log^5 n. Then, there is an algorithm that maintains a linear sketch of G in n/b^3 ·log^O(log n / log1/b) n space. For any ϕ∈ (0,1) such that ϕ≤ b/log^C ·log n / log1/bn for a large enough constant C>0, the algorithm decodes the sketch to compute a (ϕ·log^O(log n / log1/b) n, ϕ)-ED of G  with high probability, in n/b^3 ·log^O(log n / log1/b) n space and (n) time.

We remark that setting, say, b = 2^-√(log n)  in the above result gives a n^1+o(1) space algorithm for computing a (ϕ· n^o(1), ϕ)-ED for any ϕ≤ 2^-2Cloglog n √(log n). For larger values of ϕ, one can use the polynomial time algorithm of  <cit.> to still get a n^1+o(1) space construction for a  (ϕ· n^o(1), ϕ)-ED.

	As in the proof of <ref>, we can assume ϕ≥ 1/n^2. Also, by virtue of C being a large enough constant and  ϕ≤ b/log^C ·log n / log1/bn, one can always define ϵ = ϕ·log^C ·log n / log1/bn while ensuring n^-2≤ϵ≤ b log n. Then, we equivalently prove that for any b ∈ (0,1) with b ≤ 1/log^5 n there is an algorithm that maintains a linear sketch of G in n/b^3 ·log^O(log n / log1/b) n space, and that for any ϵ∈ (0,1) such that n^-2≤ϵ≤ b log n decodes the sketch to compute, with high probability, an (ϵ, ϵ/log^O(log n / log1/b) n)-ED of G in n/b^3 ·log^O(log n / log1/b) n space and (n) time.
	
	Let then b,ϵ∈ (0,1) with b ≤ 1/log^5 n and n^-2≤ϵ≤ b log n. We use the algorithm from <ref> with the same parameters b and ϵ, since every admissible pair of parameters b and ϵ fulfils the conditions of <ref>. The space complexity is also the same, and the running time is (n). Again, observe that a (b, ϵ, ϕ, γ)-BLD of G is an (ϵ,ϕ/γ)-ED of G. Hence the claim, since <ref> gives
	
    ϕ/γ = Ω(ϵ/log^4 n) ·1/log^O(log n/log 1/b) n = ϵ/log^O(log n/log 1/b) n  .



The proofs of <ref> and <ref> can be found in <ref>.



 §.§ Two-level expander decomposition incurs a sparsity dependence


Given a graph G=(V,E) in a stream and parameters ϵ,ϕ∈ (0,1), we consider the problem of computing a two-level (ϵ,ϕ)-RED of G. In other words, we study the problem of computing an (ϵ,ϕ)-ED 𝒰 of G and an (ϵ,ϕ)-ED 𝒰' of the graph G'=(V,E∖𝒰), where E∖𝒰 denotes the set of inter-cluster edges of 𝒰, i.e. the edges of E that are not entirely contained in a cluster U ∈𝒰 (see <ref> and <ref>). We remark that we wish to do so in a single pass over the stream.



  
*A natural algorithmic approach and why it fails. A naive attempt to solve this problem would be that of sketching the graph twice, for example by using our algorithm from <ref>. One can use the first sketch to construct the first level ED 𝒰. After, the hope is that one can send updates to the second sketch so as to remove the intra-cluster edges and then decode this sketch into an ED of G'=(V,E∖𝒰) using again <ref>. However, this hope is readily dashed. Indeed, sketching algorithms break down if we send a removal update for an edge that was not there in the first place, and we do not have knowledge of which of the pairs U2 are in E and which are not.



  
*Our contribution: space lower bound. We show that, in sharp contrast to our algorithm for constructing a one-level expander decomposition, this problem requires Ω(n/ϕ) space, i.e. a dependence on 1/ϕ is unavoidable. Formally, we obtain the following result.

[RED lower bound]mainthactuallb
	
	Let ℓ≥ 2 and let ϵ, ϕ∈ (0,1) such that ϵ = 1-Ω(1), ϕ≤ϵ, and ϕ≥ C ·max{ϵ^2 ,   1/n} for a large enough constant C > 0. Any  streaming algorithm that with probability at least 9/10 computes  an ℓ-level (ϵ,ϕ)-RED requires Ω(n/ϵ) bits of space.

The above theorem gives an Ω(n/ϕ) space lower bound for algorithms that compute a RED with near-optimal parameters, i.e. algorithms that achieve ϵ =(ϕ) for any 1/n ≪ϕ≪ 1/log n.



  
*Setup and hard instances.
Throughout this section, the symbols ≪ and ≫ mean smaller or larger by a large constant factor. Let us fix the RED parameters ϵ, ϕ∈ (0,1), and let us restrain ourselves to the regime ϕ≫^2 (and of course ϕ≪ϵ). We prove the lower bound by giving a distribution over hard instances G=(V, E). This distribution is parametrised by integers d and m such that 1 ≪ d ≪ m ≪ n, m ≫ 1/ϕ, m ≪ 1/^2, and d ≪1/. With these parameters fixed, our hard distribution 𝒢 is defined below in <ref>. An illustration is given in <Ref>.




	
 We partition V arbitrarily  into two sets S and T with n/2 vertices each, and further partition S into n/m sets S_1,…,S_n/m with m/2 vertices each. The edge set of the graph G=(V,E) ∼𝒢 is defined as follows.


    
  * For each i ∈ [n/m], the induced subgraph G[S_i] is an Erdős-Rényi random graph with m/2 vertices and degree ≈ d. We denote by 𝒢' the distribution of the subgraph G[S].


  * The induced subgraph G[T] is a fixed d-regular Ω(1)-expander.


  * We fix for convenience an arbitrary labelling s_i,1,…,s_i,m/2 of the vertices in each S_i, and we sample an index K uniformly from [m/2]. Then, for every i∈ [n/m], we add dm/2 edges from s_i,K to T so that each t ∈ T has d incident edges connecting to S.



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 <Ref>.




	
Let G=(V,E) ∼𝒢.  We define the set of important vertices V^*={s_i,K:i ∈ [n/m]} to be the set of vertices of S that are connected to T, and define the set of important edges E^*={{s_i,K,v} : i ∈ [n/m],  v ∈ S } to be the set of edges in the induced subgraph G[S] that are incident on V^*.

The lower bound proof has two steps: we first prove that a two-level RED leaks a non-trivial amount of information about the graph G ∼𝒢; then we prove that, in order to obtain such amount of information, the algorithm must use a lot of space.



  §.§.§ Two-level expander decomposition of the hard instance

In this section, we show that any valid two-level RED reveals a lot of informations about the important edges. The following lemma shows that a non-trivial amount of important edges are inter-cluster edges in the first level decomposition. An ideal decomposition is  illustrated in <Ref>.

 
	Let G=(V,E) ∈(𝒢). Then, any (ϵ,ϕ)-ED 𝒰 of G satisfies
	
    | E^* ∖𝒰| ≥4/5·| E^*|   .




    By definition of the graph, there are Θ(dn) edges in the graph. Since there is at most an  fraction of crossing edges, there are only O( dn) crossing edges. Note that there are Θ(dn) edges in G[T], so only an O() fraction of the edges in G[T] are crossing edges. Furthermore, G[T] is a regular expander: this implies that there is a large cluster U^* ∈𝒰 comprising a 1-O() fraction of T, together with a 1-O() fraction of important vertices. The latter is true since the edges between S and T make up a constant fraction of the total volume and only a small fraction of the edges can be crossing. We refer the reader to <Ref> for more details. 
    

    The edges in the subgraph G[S] also account for a constant fraction of the total volume. Together with the fact that each S_i induces a regular expander, for many of the S_i's we will have a cluster in 𝒰 that contains most of S_i. Now consider a set S_i such that the important vertex of S_i is in U^* and most of the vertices in S_i are all in the same cluster. If most of the vertices in S_i are also inside U^*, then consider the cut from (U^* ∩ S_i )∖{s_i,K} to (U^* ∖ S_i) ∪{s_i,K}. The cut size is at most the number of important edges in S_i, which is O(d). On the other hand, the volume of the cut is Θ(dm) since most of the vertices of S_i are in the cluster. Recalling that m ≫1/ϕ, one concludes that the cut is sparse. Therefore, we ruled out the possibility of having many vertices of S_i in U^*. See <Ref> for a detailed discussion. 
    
    In summary, as illustrated in <Ref>, in any valid expander decomposition, most of the vertices in T and most of the important vertices are inside a giant cluster U^*, and for most of the S_i's, there is a cluster other than U^* that contains most of the vertices in S_i. For any such S_i, most of the important edges inside it are then crossing edges.

The second level expander decomposition, i.e. an expander decomposition of the inter-cluster edges from the first level, is also quite structured, as illustrated in the ideal RED of <Ref>. 

 
    Let G=(V,E) ∈(𝒢), and let 𝒰_1,𝒰_2 be any 2-level (ϵ,ϕ)-RED  of G. Then, there are at most n/10 vertices in S that are non-isolated vertices[We call a vertex v non-isolated in a decomposition 𝒰 if 𝒰 puts v in a cluster with other vertices, i.e. v does not constitute a singleton cluster in 𝒰.] in 𝒰_2. Moreover, at least a 2/3 fraction of important edges are not in E∖𝒰_2, i.e. a 2/3 fraction of important edges are inside clusters of 𝒰_2.



    The number of crossing edges in the first level decomposition is O( d n), which is much less than n since d ≪1/. This means that most of the vertices are isolated vertices in the second level. Moreover, by <Ref>, most of the important edges are crossing edges in the first level decomposition. Among these Θ(dn/m) edges, at most O(^2 dn) edges can be crossing edges in the second level decomposition. Recalling that m ≪1/^2, we see that most of the important edges are not crossing edges in the second level decomposition.






  §.§.§ Lower bound via communication complexity

Our streaming lower bound will be proven in the two-player one-way communication model. In this setting, Alice gets the edges in G[S] and G[T], and Bob gets the edges between S and T. We prove that in order to give a two-level RED, Alice needs to send Ω(dn) bits of information to Bob.

The high level idea is the following. Note that the identity of the important vertices can be only revealed by edges given to Bob. Thus, given Alice's input, every vertex in S has the same probability to be an important vertex, which means that every edge in S has the same probability to be an important edge. Therefore, in order to make sure that Bob recovers most of the important edges (which is morally equivalent to computing a two-level RED, as suggested by <Ref>), Alice needs to send most of the edges in S to Bob, which is Ω(dn). 

To make the above idea concrete, we consider a communication problem where Alice is given a graph, and Bob is asked to output a not too large set of pairs that contains a good fraction of the edges of Alice's input. We first reduce this new problem to the two-level RED problem. Then, we will prove a communication complexity lower bound for this problem.

	
    In the communication problem , Alice's input is a graph G'=(S,E') where S=n/2, and Bob's output is a set of pairs of vertices F ⊆ S2 that must satisfy |F| ≤ nm/10 and |F ∩ E'| ≥Ω(|E'|), i.e. at least a constant fraction of the edges in G' are in F.


Now, the idea is to plant Alice's input for  into our instance from <ref>. The input distribution for  is sampled from  the distribution 𝒢'. In other words, the distribution of Alice's input is the same as the left-hand side part of G ∼𝒢 (i.e. the subgraph G[S]). Then, in the reduction, Alice gets the edges of G[S] and G[T] while Bob gets the edges between S and T. By virtue of the discussion in the previous section, we expect a RED of G to allow Bob to recover many important edges in G[S]. Hence, Bob could simulate the RED algorithm for all the m/2 possible choices of the random index K ∼ [m/2] that defines the important edges (see <ref>): in this way, the k-th RED should reveal information about Alice's edges that are incident on the vertices {s_i,k}_i. Therefore, by varying k over [m/2], Bob should obtain information about all the edges in Alice's graph. More precisely, the reduction is the following.

[Informal, see <ref>]
	Let 𝒜 be a deterministic streaming algorithm for computing a 2-level (ϵ,ϕ)-RED. Alice, given her input graph G'=(S,E') generated by 𝒢', feeds her edges E' to 𝒜, together with the fixed edges of G[T]. Then, she sends the memory state of 𝒜 to Bob. Upon receiving the message, Bob makes m/2 copies  of 𝒜 and initialises them to the memory state he received from Alice. Call these copies 𝒜_1, …, 𝒜_m/2. Next, for each k ∈ [m/2], call G_k = (V,E_k) the graph we obtain from 𝒢 when K=k and the left-hand side G_k[S] is exactly Alice's input G' (so that the vertices {s_i,k}_i are the important vertices in G_k, see <ref>). Then, Bob feeds the edges E_k(S,T) to 𝒜_k. Let then 𝒰^k_1,𝒰^k_2 be the RED output by 𝒜_k. Bob finally constructs his output set F as follows: for each k ∈ [m/2], add the pair {s,s_i,k} to F for every i ∈ [n/m] and every s ∈ S_i that is not an isolated vertex in 𝒰^k_2.

By <ref>, the number of non-isolated vertices in the second-level decomposition is at most n/10. Hence, the total number of pairs added to F is at most nm/10, thus satisfying the first requirement of <ref>. Moreover, by <ref>, at least a 2/3 fraction of the important edges are not crossing edges in the second level. This means that for each k, at least a 2/3 fraction of the edges that are incident on s_i,k is added to F. In turn, this implies that F contains at least a constant fraction of the edges in E', thus satisfying the second requirement of <ref>. More precisely, one can prove the following.


	
	If there is a deterministic L-bit space streaming algorithm 𝒜 that computes a 2-level (ϵ,ϕ)-RED with constant probability over inputs G ∼𝒢, then there is a deterministic protocol ℛ that solves  with constant probability over inputs G' ∼𝒢'. The communication complexity of ℛ is at most L.


The final component of the proof is the communication complexity lower bound for .


	
    The one-way communication complexity of solving  with constant probability over inputs sampled from 𝒢' is Ω(dn).



    Roughly speaking , we show that the posterior distribution of the input conditioned on the output is shifted away from its prior distribution.
    
    Recall that when the input G'=(S,E') is sampled from 𝒢', the graph is a disjoint union of n/m random graphs with m/2 vertices each and degree ≈ d. There are roughly 
    
    (m/2d^m/2)^n/m≈(m/2d)^dn/2
 
    possible inputs in total and the information complexity is Ω(dn). Conditioning on the the output F of  a correct protocol for , the number of possible inputs is greatly decreased. In particular, to determine the input E', we need to select a constant fraction, say 2/3 for example, of the pairs from F, and select the rest of the edges (a 1/3 fraction, in our example)  arbitrarily. Since |F| is at most nm/10, |E'| = Θ(dn), and S2≈ nm/2, the total number of possible inputs is then roughly 
    
    nm/102/3 · dn·nm/21/3 · dn≈(3m/20d)^1/3 · dn·(3m/2d)^1/6 · dn < (m/3d)^ dn/2.

    This means the information complexity of the input is decreased by a constant factor, which means that the protocol needs to communicate Ω(dn) bits of information.



Finally, one can conclude the main result (<Ref>) combining <ref> and <ref>. The formal proofs and definitions are deferred to <ref>.




§ PRELIMINARIES



In this section, we introduce definitions and notation that we will use in the remainder of the paper.



  
Boundary-linked expander decomposition.
In this paper we work heavily with boundary-linked EDs <cit.>. A boundary-linked ED is the same as a classical ED except that Property (<ref>) of <ref> is strengthened. 

For a cut S in a cluster U, the boundary SU of S with respect to U is the number of edges that go from S to the outside of U, i.e. SU=|E(S,V ∖ U)|. For U ⊆ V and τ≥ 0, the τ-boundary linked subgraph of G on U, denoted by G[U]^τ, is the subgraph of G induced by U with additional τ·{u}U self-loops attached to every u ∈ U.
	For cuts S ⊆ U, we adopt the following shorthand notation:
	
		
  * the volume _G[U]^τ(S) is denoted by _U^τ(S);
		
  * the sparsity Φ_G[U]^τ(S) in G[U]^τ is denoted by Φ_U^τ(S), which is equal to
		
    Φ_U^τ(S) = SU/min{_U^τ(S), _U^τ(U ∖ S)}  .

	
Let ϕ∈ (0,1), b ∈ [ϕ, 1) be some parameters. Most of the time in this paper, the value of τ for all instances of boundary linked subgraphs will be the same and equal to the ratio b/ϕ. Hence we adopt additional shorthand notation: we use G[U]^∘, _U^∘(S), Φ_U^∘(S), Φ_U^∘ for referring to G[U]^b/ϕ, _U^b/ϕ(S), Φ_U^b/ϕ(S), Φ_U^b/ϕ respectively.
One can observe that

    _U^∘(S) = _U^b/ϕ(S) = (S)+(b/ϕ-1)SU  .

Then a boundary-linked ED can be defined as follows.


	
	Let G=(V,E), let b, ϵ, ϕ∈  (0,1) be parameters such that b ≥ϕ, and let γ≥ 1 be an error parameter. A partition 𝒰 of V is a (b, ϵ, ϕ, γ)-boundary-linked expander decomposition (for short, (b, ϵ, ϕ, γ)-BLD) of G if
	
		
  *  1/2∑_U ∈𝒰U≤ϵ |E|, and
		
  *  for every U ∈𝒰, G[U]^∘ is a ϕ/γ-expander.
	




  
Expander decomposition sequence. For a partition 𝒰 of V (think of 𝒰 as an ED of G), we denote by E ∖𝒰 the set of inter-cluster (or crossing) edges with respect to 𝒰, i.e.

    E ∖𝒰 = E ∖⋃_U ∈𝒰U2  ,

Analogously, we let G∖𝒰 = (V,E∖𝒰) be the subgraph of G obtained by removing the intra-cluster edges in 𝒰.  For a sequence of partitions 𝒰_1, …, 𝒰_ℓ of V and i ∈ [ℓ], we define G^_1=G and denote by G^_i+1 = G^_i∖𝒰_i the subgraph of G obtained by removing the intra-cluster edges of the first i partitions.


	
	Let G=(V,E), let ϵ, ϕ∈ (0,1), let ℓ≥ 1, and let 𝒰_1, …, 𝒰_ℓ be a sequence of partitions of V. The sequence 𝒰_1, …, 𝒰_ℓ is an ℓ-level removal-based (ϵ, ϕ)-ED sequence (for short, ℓ-level (ϵ, ϕ)-RED or (ϵ,ϕ,ℓ)-RED) of G if, for all i ∈ [ℓ], 𝒰_i is an (ϵ, ϕ)-ED of the graph G^_i.





  
Sparsifier-specific notation.
Since our algorithms will be working on sparsifiers of the input graph, it is convenient to have short-hand notation for the above quantities in the sparsifier. For a weighted subgraph H=(V,E',w) of G, a cluster U ⊆ V and a cut S ⊆ U, we have “sparsified” counterparts S, S, SU,SU for S, (S), SU,SU. More precisely, S=w(S,V∖ S), SU=w(S,U∖ S), SU=w(S,V∖ U), and S is the sum of weighted degrees of vertices of S in H. Then, H[U]^∘ denotes the subgraph of H induced by U (retaining edge weights from w), where every vertex is attached  b/ϕ·{x}U self-loops. We then also introduce notation for the “sparsified” version of SU and SU: we denote _H[U]^b/ϕ(S) and Φ_H[U]^b/ϕ(S) by SU and SU respectively. For clarity, we note that SU = S+b-ϕ/ϕSU, reflecting the fact that _U^∘(S) = (S)+b-ϕ/ϕSU.


§ SPARSIFICATION FOR VERTEX-INDUCED SUBGRAPHS


In order to give a space efficient implementation of <ref>, we will take a subroutine computing an approximate most-balanced sparse cut of a graph, and run it as a black box on a vertex-induced subgraph of a sparsifier. From such sparsifier, we demand that the local cuts are approximated to within an additive error proportional the corresponding global cut. Formally, we rely on the following cut preserving property for vertex-induced subgraphs.

	
	Let G=(V,E), let δ∈ (0,1), let U ⊆ V be a cluster, and let H=(V,E',w) be a weighted subgraph of G on the vertex set V. Then, H is a cluster sparsifier for U in G with error δ, denoted by H[U] ≈_δ G[U], if one has
	
    ∀ S ⊆ U, SU - δ·S≤SU≤SU + δ·S   and   ∀ S ⊆ V,  (1-δ)·S≤S≤ (1+δ)·S  .


In <ref>, the second property is the same as the first one when U=V. Therefore, if one is able to sample a sparsifier where the first property holds with high probability for any cluster U⊆ V, then we get a sparsifier that with high probability embodies <ref>. Perhaps surprisingly, we show that classical constructions of cut sparsifiers give the first property of <ref>. Specifically, we use the approach of Fung et al. <cit.>, based on sampling edges with probability proportional to their edge connectivity, together with its dynamic stream implementation by Ahn, Guha, and McGregor <cit.>. Hence, we obtain the following sparsification lemma.

[Cluster sparsifiers in dynamic streams]lemmamaintechlemadd
	
	Let G=(V,E) be an n-vertex graph and let δ∈ (0,1). Then, there is a distribution 𝒟_δ such that, for any cluster U ⊆ V and a sample H=(V,E',w)  ∼𝒟_δ one has H[U] ≈_δ G[U] with high probability, and |E'| = (n/δ^2) edges. When G is given in a dynamic stream, there is an algorithm that maintains a linear sketch of G in (n/δ^2) space and decodes it to output a weighted subgraph H=(V,E',w)  in (n/δ^2) space and (n) time such that H ∼𝒟_δ.

The distribution 𝒟_δ we use is a cosmetic modification of the algorithm of Ahn, Guha, and McGregor <cit.>, hereafter referred to as the AGM algorithm. It provides a dynamic stream implementation of the sampling scheme of Fung et al. <cit.> for constructing cut sparsifiers. Even though we deviate only slightly from the original analysis of Ahn, Guha, and McGregor and Fung et al., we give a complete proof for the sake completeness. In <ref>, we give a few preliminaries on sparsification and dynamic streams that are needed to present and discuss the algorithm. In <ref>, we outline the algorithm and prove the technical lemmas that characterise its correctness. In <ref>, we use standard cut counting arguments to combine such technical lemmas into proving <ref>.



 §.§ Sparsification primer


We give a few preliminaries needed to present the AGM algorithm. We start with the following result: for a graph given in a dynamic stream, we can output a subgraph that preserves the distinction between k-edge connected and not k-edge connected cuts.


	
	Let G=(V,E) be a graph given in a dynamic stream, and let k ≥ 1 be an integer parameter. Then there is an algorithm ConnWit(k) that maintains a linear sketch of G in (kn) space. With high probability, the algorithm decodes the sketch to output a subgraph G'=(V,E') in (kn) space and (n) time such that:
	
		
  * for all ∅≠ S ⊊ V, if |E(S,V∖ S)| < k then E(S, V ∖ S) ⊆ E';
		
  * for all ∅≠ S ⊊ V, if |E(S,V∖ S)| ≥ k then |E(S, V ∖ S) ∩ E'|≥ k;
		
  * |E'|=O(kn).
	



	The algorithm works by maintaining k independent linear sketches for dynamic spanning forest <cit.>, each taking (n) space to maintain and (n) space and (n) time to decode. We use the first sketch to recover a spanning forest of G. Then, we feed edge removals for every edge in the spanning forest to the second to k-th sketch. We proceed in this fashion until we have recovered k edge-disjoint maximal spanning forest F_1, …, F_k ⊆ E of G. Then we let E' be the union of these spanning forests. This takes k ·(n) space and one has |E'| = O(kn).
	
	Now consider a cut ∅≠ S ⊊ V. Clearly E'(S,V ∖ S) ⊆ E(S,V ∖ S). Now suppose E(S,V ∖ S) < k. For the sake of a contradiction, let us say E(S,V ∖ S) ∖ E' ≠∅. By disjointness of the F_i's, there must be a j ∈ [k] such that the residual graph G ∖ (∪_i=1^j-1 F_i) still contains an edge from E(S,V ∖ S). Hence, there are two components of the spanning forest F_j which could be joint by this edge, which contradicts its maximality.
	
	Consider the case of E(S,V ∖ S) ≥ k, and suppose for the sake of a contradiction that E'(S,V ∖ S) < k. By disjointness of the F_i's there must be a forest F_j such that F_j ∩ E(S,V ∖ S) = ∅ (as otherwise E'(S,V ∖ S) ≥ k). As before, this contradicts the maximality of F_j.

Hereafter let C>0 be a large enough constant, and define for every e={u,v}∈V2 the ideal sampling probabilities

    p_e = min{1, 1/λ_e·C log^3 n/δ^2}  ,

where λ_e is the edge connectivity of e, i.e. the minimum number of edges crossing a uv-cut in G. The original AGM algorithm estimates edge connectivities (and hence sampling probabilities) via the sparsifier that is being constructed, in some sense. Here, we simplify the analysis and instead use a separate sparsifier for that purpose. For instance, one can use a spectral sparsifier, defined as follows.

	Let G=(V,E) and let ξ∈ (0,1). A (1±ξ)-spectral sparsifier of G is a weighted subgraph G̃ = (V,Ẽ,w̃) such that
	
    ∀x∈ℝ^V ,    (1-ξ)x^⊤ L x≤x^⊤L̃x≤ (1+ξ)x^⊤ L x  ,

	where L and  L̃ are the Laplacian matrices of G and G̃, respectively.
	The Laplacian matrix of a graph is L=D-A, where D denotes the degree diagonal matrix of the graph and A denotes its (weighted) adjacency matrix
It is known how to construct such sparsifiers in dynamic streams.

	
	Let G=(V,E) be a graph given in a dynamic stream, and let ξ∈ (0,1). Then, there is an algorithm Spectral(ξ) that maintains a linear sketch of G in (n/ξ^2) space. With high probability, the algorithm decodes the sketch to output in (n/ϵ^2) time and space a weighted subgraph  G̃ = (V,Ẽ,w̃) with |Ẽ| = (n/ϵ^2) that is a (1±ξ)-spectral sparsifier of G.




 §.§ Sampling algorithm for dynamic streams


With all the preliminaries in place, we can describe (our version of) the AGM algorithm. The high level approach consists in sampling edges at geometric rates as they arrive in the stream, and then use the i-th connectivity witness to recover the edges e that are sampled at rate p_e ≈ 2^i. Algorithm <ref> outlines this process, where we denote by λ̃_e the edge connectivity of e ∈V2 in G̃. As one can see from the description of the algorithm, we actually let w be a function E →ℝ_≥ 0 where w(e)=0 for all e ∈ E ∖ E'. This facilitates the discussion.



We remark that Algorithm <ref> assumes access to (n) bits of randomness. It is known that one can lift this assumption by using Nisan's pseudorandom generator <cit.> with only a (n) space blow-up factor (and a (n) time blow-up). We remark that we can do this because the random bits are only used during the stream processing, and we only compute linear sketches in this phase, which in particular are oblivious to the order of updates in the stream. Then we can already conclude a bound on the space complexity, as well as on the size of the output graph.

	
	Algorithm <ref> takes (n/δ^2) bits of space and H has at most (n/δ^2) edges.


	The edges of H can only come from the output of one of the instances ConnWit. In other words, E' ⊆∪_i E_i'. From <ref> we also know that each instance of ConnWit takes (kn) bits of space and that each E_i' contains at most (kn) edges. Hence, |E'| = (kn)=(n/δ^2) and Algorithm <ref> takes (kn) = (n/δ^2) bits of space.


We continue our analysis by bounding the probability that a certain bad event happens, which corresponds to the sampling or sketching primitives failing to preserve a needed value. To be more specific about this, first define for every i =0, …, 2log n the event ℬ_i that instance i of Theorem <ref> ConnWit_i(k) fails to correctly construct the graph G_i'. In addition, for every e ∈V2, let ℬ^(1)_e be the event that λ̃_e < 1/2 ·λ_e or λ̃_e > 3/2 ·λ_e. Finally, define for every e ∈ E the quantity

    τ_e = ⌊log1/min{1, p_e}⌋  ,
 and let ℬ^(2)_e be the event that there exists j  ∈ℕ with τ_e-2 ≤ j ≤τ_e such that λ_e(G_j) ≥ k, where k is defined in <ref> and λ_e(G_i) is the edge connectivity of e in G_i for i=0,…,2log n. With this notation, the bad event we want to avert is

    ℬ = (∨_i=0^2 log nℬ_i) ∨(∨_e ∈V2ℬ^(1)_e) ∨(∨_e ∈ Eℬ^(2)_e)   .

Intuitively, this is a bad event because the algorithm cannot trust the connectivity witnesses nor the edge connectivities computed via the spectral sparsifiers. On the contrary, when ℬ does not happen, we know that all the graphs G_i' are constructed correctly (thanks to ℬ_i), all the edges have j_e that is not too large (thanks to ℬ_e^(1)), and we can recover the sampled edges via the graphs G_i' (thanks to ℬ_e^(2)).


	
	When running Algorithm <ref>, the bad event ℬ does not happen with high probability.


	By <ref>, we know that ∨_eℬ^(1)_e does not happen with high probability for any e ∈V2. Now let i=0,…, 2 log n, and note that the randomness used to define the input G_i to ConnWit_i(k) and the randomness used by ConnWit_i(k) itself are independent. Hence, by <ref> and by union bound over i, we get that ∨_iℬ_i does not happen with high probability.  Lastly, we deal with the events ℬ^(2)_e.
	
	For ease of notation, define for any ∅≠ S ⊆ V the size of its cut projected onto the edges of G_i as ∂^i S=|E_i ∩ E(S,V ∖ S)|. Then consider any e={s,t}∈ E and any j  ∈ℕ with τ_e-2 ≤ j ≤τ_e, and let S_e ⊆ V be an st-cut in G of minimum size, i.e. λ_e = S_e. Observe that by the way the algorithm defines the sub-streams, each f ∈ E is in E_i with probability 2^-i for all i=0, …, 2 log n, so in expectation the edge connectivity of e has dropped below 4 C ·δ^-2·log^3 n in the graph G_j. More precisely,
	
    [∂^j S_e] = S_e· 2^-j   ≤ 4·S_e· 2^-τ_e
       ≤ 8λ_e min{1,  p_e}
       ≤ 8λ_e p_e  
       ≤ 8 λ_e C ·δ^-2·log n/λ_e = 8 C ·δ^-2·log^3 n   .

	Applying the Chernoff bound (since edges are sampled independently of each other)  we get that
	
    [∂^j S_e > 12 C ·δ^-2·log^3 n ]    ≤[∂^j S_e > (1+1/2) [∂^j S_e] ] 
       ≤exp(-[∂^j S_e]/12) 
       ≤exp(-[∂^τ_e S_e]/12)  .

	In order to make sure that the exponential above is in fact small enough, we now have two cases to consider. First consider the possibility that τ_e= 0, or equivalently p_e > 1/2. This means two things: E_τ_e=E (see <ref>), and λ_e < 2 C ·δ^-2·log^3 n. Then, ∂^τ_e S_e=λ_e ≤ 12 C ·δ^-2·log^3 n with probability 1, so we need not worry about this case. For the other possibility that p_e ≤1/2, one can deduce that p_e = C ·λ_e^-1δ^-2·log^3 n and thus lower bound the expectation of ∂^τ_e S_e as
	
    [∂^τ_e S_e] = ∂ S_e · 2^-τ_e≥λ_e p_e = C ·δ^-2·log^3 n   ,

	Hence, the Chernoff bound above gives ∂^τ_e S_e ≤ 12 C ·δ^-2·log^3 n < k with high probability. Thus, the edge connectivity of e in G_j must be at most ∂^j S_e < k. Taking a union bound gives that ∨_eℬ^(2)_e does not happen with high probability.


Finally, we show properties of the weight function produced by the algorithm. We first focus on the special case of edges with very low connectivity, i.e. with p_e=1, and show that these are indeed copied exactly in E', as one would expect.


	
	Let H=(V,E',w) be the output of Algorithm <ref>. If ℬ does not happen, then for any edge e ∈ E with p_e =1 we have e ∈ E' and w(e)=1 .


	Assume ℬ does not happen. This in particular means that G_0' is correctly constructed, so by Theorem <ref> any cut of size less than 16C ·δ^-2·log^3 is exactly preserved in G_0'. On the other hand, if an edge e ∈ E has p_e = 1 then its edge connectivity λ_e is at most C ·δ^-2·log^3 n. Since λ̃_e ≤ 2 λ_e, it then follows that p̃_e = 1, so j_e=0 and hence the claim.


For edges which we do not know to have p_e=1, but for which we at least know a lower bound p on their sampling probability, we wish to show that they are preserved with “very high” probability. We do this by using a Chernoff-style bound of Ahn, Guha, and McGregor.

lemmaprobsampling
	
	Let H=(V,E',w) be the output of Algorithm <ref>. Then for any edge set X ⊆ E, any p ≤min_e ∈ X p_e, and any x ≥ |X| one has
	
    [ℬ and |∑_e ∈ X w(e) - |X|| > δ· x ] ≤ 2 exp(-1/48·δ^2 ·  p x).



	For ease of notation, let λ̃ be the vector of edge connectivities (λ̃_e)_e ∈ E from <ref>, and λ is the vector of edge connectivities (λ_e)_e∈ E of G. We will condition on the values λ̂ that λ̃ can take, and define
	
    p̂_e = min{1, 2/λ̂_e·C log^3 n/δ^2}   and   ĵ_e = ⌊log1/min{1, p̂_e}⌋  .

	Then,
	
    [ℬ and |∑_e ∈ X w(e) - |X|| > δ· x ] 
    
    		=    ∑_λ̂∈ℕ^E[ℬ and |∑_e ∈ X w(e) - |X|| > δ· x   and λ̃=λ̂] 
    
    		=    ∑_λ̂∈ℕ^E  : 1/2λ≤λ̂≤3/2λ[ℬ and |∑_e ∈ X w(e) - |X|| > δ· x   and λ̃=λ̂]   .

	By conditioning we get
	
    [ℬ and |∑_e ∈ X w(e) - |X|| > δ· x ] 
    
    		=    ∑_λ̂∈ℕ^E  : 1/2λ≤λ̂≤3/2λ[ℬ and |∑_e ∈ X w(e) - |X|| > δ· x  | λ̃=λ̂] ·[λ̃=λ̂]

	We now analyse the first factor in each term of the sum above. We use three facts to do this: (1) whenever we have ℬ, for all e ∈ X one has that e ∈ E_j_e' if and only if e ∈ E_j_e (this is the case because 1/2λ≤λ̃≤3/2λ, so max{0, τ_e-2}≤ j_e ≤τ_e, and the event ℬ^(2)_e does not happen); (2) recall that, for i=0,…,2log n, e ∈ E_i if and only if ∏_t=1^ih_t(e)=1 (see <ref>); (3) also recall that <ref> assigns weight 2^j_e to an edge recovered from E'_j_e (see <ref>).
	Using these three facts, we get
	
    [ℬ and |∑_e ∈ X w(e) - |X|| > δ· x  | λ̃=λ̂]
    		= [ℬ and |∑_e ∈ X 2^j_e∏_t=1^j_eh_t(e) - |X|| > δ· x  | λ̃=λ̂]   .

	Next, by the condition λ̃=λ̂, we have ĵ_e=j_e for all e ∈ X, so we get
	
    [ℬ and |∑_e ∈ X w(e) - |X|| > δ· x  | λ̃=λ̂]
    		    =  [ℬ and |∑_e ∈ X 2^ĵ_e∏_t=1^ĵ_eh_t(e) - |X|| > δ· x  | λ̃=λ̂] 
       ≤[|∑_e ∈ X 2^ĵ_e∏_t=1^ĵ_eh_t(e) - |X|| > δ· x  | λ̃=λ̂] 
        = [|∑_e ∈ X 2^ĵ_e∏_t=1^ĵ_eh_t(e) - |X|| > δ· x ]    .

	Now we apply the following form of the Chernoff bound.
	[<cit.>]
		Let X_1,…,X_N be independent random variables distributed in [0,a]. Let X= ∑_r ∈ [N] X_r and μ = [X]. Then, for ζ∈ (0,1) and α≥ 0 one has
		
    [| X- μ| > ζμ+α] ≤ 2 exp(-ζα/3a)

	
	Before applying this bound, we note that the random variables 2^ĵ_e∏_t=1^ĵ_eh_t(e) are independent across e ∈ X and have each mean 1. Moreover, each of this random variables have value at most 2^ĵ_e≤ 2^⌊log1/min{1,p}⌋, so we set a = 1/p. We also set ζ = δ/2 and α = δ· (x-|X|)+δ|X|/2. Then we get
	
    [|∑_e ∈ X 2^ĵ_e∏_t=1^ĵ_eh_t(e) - |X|| > δ· x ] ≤ 2 exp(-δ^2/48px)   .

	This concludes the proof.




 §.§ Cut counting and proving the sparsification lemma


We hereafter fix a cluster U⊆ V, and we partition the edge set E into F_i = {e ∈ E:   2^i ≤λ_e ≤ 2^i+1 -1  } for i =0,…,log n. Note that these F_i's are pairwise disjoint and their union gives E. We recall that E(A,B) denotes the set of edges in E with one endpoint in A and one in B, for A,B ⊆ V. Then, we write SU=|F_i ∩ E(S,U ∖ S)| to denote the size of the projection of the local cut of S onto the edge set F_i, for all i=0,…, log n and ∅≠ S ⊊ U. Analogously, we also write SU=w(F_i ∩ E(S,U ∖ S)) to denote the total weight of the projection of the local cut of S onto F_i, where w is the weight function of H.

We show that H preserves the cuts of a cluster U ⊆ V within each F_i individually, with high probability. This follows by two of the technical lemmas we proved in the previous section, namely <ref> and <ref>.

 
	Let H=(V,E',w) be the output of <ref>, and let i =0,…,log n. Then
	
    [  B  and  ∃ ∅≠ S ⊊ U   :  |SU - SU| > δ·S/1+log n] ≤1/(n)  .



We proceed by first showing a probability bound for each cut S, and then combine them using a union bound to get the final result. Specifically, for all j ∈ [2log n] we define the set

    𝒴_ij={E(S,V ∖ S) :  ∅≠ S ⊊ U  and  2^i+j-1≤S≤ 2^i+j-1 }  ,

and we will show a probability bound for all j ∈ [2log n] and Y ∈𝒴_ij. Taking a careful union bound over all such choices will be enough to get the lemma statement. It shall be useful to define Π_U^i(Y)=Y ∩ F_i ∩U2 to be the projection onto F_i and onto the cluster U of the edges in Y, for any Y ⊆ E. Moreover, we denote by ℱ_Y the failure event that

    |w(Π_U^i(Y)) - |Π_U^i(Y)|| > δ|Y|/1+log n  ,

For ease of writing we shall denote Π_U^i(E(S,V ∖ S)) and ℱ_E(S,V ∖ S) by Π_U^i(S) and ℱ_S respectively. To appreciate their purpose, we remark that for any ∅≠ S ⊊ U,

    ℱ_S    |SU - SU| > δS/1+log n

since Π_U^i(S)=Π_U^i(E(S,V ∖ S)) = E(S,V ∖ S) ∩ F_i ∩U2 = F_i ∩ E(S,U∖ S).


	
	Let j ∈ [2log n] and Y ∈𝒴_ij. Then
	
    [ℬ and ℱ_Y] ≤ 2n^-C/7682^j  .




	We start by observing that we can consider only the set X = {e ∈Π_U^i(Y)   :   p_e < 1}, since edges with p_e=1 are always added to E' with weight set to 1 (when ℬ does not occur) by Lemma <ref>, so
	
    |w(Π_U^i(Y)) - |Π_U^i(Y)|| = |w(X) - |X||   .

	If X = ∅, the probability of ℱ_Y is zero, so let us consider the case that X ≠∅, for which we want to upper bound the probability
	
    [ℬ and |w(X) - |X|| > δ|Y|/1+log n]   .

	To do so, we use Lemma <ref> and set p=min{1, C · 2^-(i+1)δ^-2log^3 n}, which is a lower bound on all the probabilities {p_e}_e ∈ X. This is the case because every e ∈ X has p_e < 1 and λ_e ≤ 2^i+1 (since X ⊆ F_i). We also note that |Y| ≥ |X|, thus we can safely apply Lemma <ref> and get
	
    [ℬ and |w(X) - |X|| > δ|Y|/1+log n]    ≤ 2 exp(-1/48·δ^2 · p ·|Y|/(1+log n)^2)   .

	If we recall Y ∈𝒴_ij, and in particular |Y| ≥ 2^i+j-1, we can then conclude the claim by plugging the value of p into the exponent.

Now that we have bounded the probability that a single cut from 𝒴_ij is not well preserved once projected onto U and F_i, we show that the union over j of the collections 𝒴_ij is representative of all the local cuts of U.

	
	Let ∅≠ S ⊊ U such that Π_U^i(S)≠ ∅. Then there exists j ∈ [2log n] so that E(S,V ∖ S) ∈ 𝒴_ij.


	Since Π_U^i(S) ≠ ∅, there exists e={u,v}∈ E(S,V∖ S) that is also in F_i. In particular this means that E(S,V∖ S) is a uv-cut in G, and e has edge connectivity at least 2^i, thus S≥ 2^i. At the same time, S≤ 2^i+j-1 for some j ∈ [2log n] since S≤ |E| ≤ n^2-1.

Now, for all j ∈ [2 log n] and all Z ⊆ F_i, we define the worst-case edge set Y^*_j(Z) ⊆ E of Z as

    Y^*_j(Z) ∈_Y ∈𝒴_ij: Π_U^i(Y) = Z  |Y|  .

The reason why we call Y^*_j(Z) worst case for Z is the following. Among all the global cuts in 𝒴_ij whose projection onto F_i and U is Z,  the cut Y^*_j(Z) is the one which allows for the smallest error term, which intuitively makes ℱ_Y more likely to happen. Formally we have the following claim, which follows from the definition.


	
	If there exist j ∈ [2log n] and Y ∈𝒴_ij such that the event ℱ_Y happens, then there exist j ∈ [2log n] and Z ∈{Π_U^i(Y'): Y' ∈𝒴_ij} such that ℱ_Y_j^*(Z) happens.

Claim <ref> and <ref> together suggest that we can restrain ourselves to union bound over {Π_U^i(Y): Y ∈𝒴_ij}, which is exactly what we are going to do. Before that, we make sure that this set is not too large.

	
	For every j ∈ [2log n] we have |{Π_U^i(Y): Y ∈𝒴_ij}| ≤ n^2 · 2^j.


	We will employ the following cut counting result, where E^k denotes the set of edges e ∈ E with edge connectivity λ_e ≥ k, for any integer k.
	
		For any k, s ≥ 1 one has
		
    |{E(S,V∖ S) ∩ E^k   :  ∅≠ S ⊊ V  and S≤ s· k}| ≤ n^2s  ,

		i.e. the number of distinct subsets of edges of connectivity at least k from cuts of size at most s · k is at most n^2s.
	
	Fix j ∈ [2log n]. We recall that every e ∈ F_i has λ_e ≥ 2^i, which means F_i ⊆ E^2^i. Also, for any Y ∈𝒴_ij there is by definition a cut ∅≠ S ⊊ V such that S≤ 2^i+j-1 and Y=E(S,V∖ S). Hence
	
    |{Π_U^i(Y) :   Y ∈𝒴_ij}|
    		   ≤ |{E^2^i∩ E(S,V∖ S) : ∅≠ S ⊊ V  and S≤ 2^i+j}|   ,

	and applying Theorem <ref> with k  2^i and s  2^j we conclude the claim.

Using the above claims we finally have

    [ℬ and ∃ ∅≠ S ⊊ U  s.t. ℱ_S] 
    by Claim <ref>    ≤   [∃ j ∈ [2log n]  s.t. ∃ Y ∈𝒴_ij s.t. ℬ and ℱ_Y] 
    by Claim <ref>    ≤   [∃ j ∈ [2log n]  s.t. ∃ Z ∈{Π_U^i(Y): Y ∈𝒴_ij} s.t. ℬ and ℱ_Y_j^*(Z)] 
    by Claim <ref>    ≤   ∑_j ∈ [2log n]  ∑_ Z ∈{Π_U^i(Y) :   Y ∈𝒴_ij} 2n^-C/7682^j
    by Claim <ref>    ≤   ∑_j ∈ [2log n] n^2 · 2^j  2n^-C/7682^j
    ≤   1/(n)


Finally, we can conclude the main sparsification lemma <ref> by a simple combination of <ref>, <ref>, and <ref>.


Recall that the F_i's partition and cover E entirely, and that ℬ happens with high probability by <ref>. Then, one can see that conditioning on ℬ, summing over i=0,…, log n, and applying <ref> gives <ref>.



§ TESTING EXPANSION AND FINDING SPARSE CUTS IN SPARSIFIERS


The key ingredient to our ED algorithms is that sparsifiers as per <ref> serve as good proxies to the subgraphs of G for any subroutine that either asserts expansion or outputs an approximate most-balanced sparse cut. We will in fact show that the result of running such subroutine on a boundary-linked subgraph of G is almost the same as if we run it on the corresponding subgraph of a sparsifier.

Before we proceed further, we need to define what we demand exactly from the approximate most-balanced sparse cut subroutine. Loosely speaking, it is a procedure that takes as input a graph and a sparsity parameter, and either asserts that the graph is an expander, or outputs a sparse cut. In particular, the returned cut should be not too small compared to the largest cut among those certifying that the input is not an expander. For technical reasons, we ask that the algorithm also returns an approximation to the volume of the returned cut. Inspired by the definition of <cit.>, we have the following definition, which captures what the subroutine should return.


	
	Let ψ, ξ∈ [0,1] and α,λ≥ 1, and let H=(U,E',w) be a weighted graph with self-loops. A (ψ,ξ,α,λ)-balanced sparse cut witness of H (for short, (ψ,α,λ,ξ)-BSCW) is an element ω of {}∪ ({R : ∅≠ R ⊊ U}×ℝ_>0) such that:
	
		
  *  if ω =, then H is a ψ-expander;
		
  * if ω = (R,ν), then:
		
			
  *  Φ_H(R) < α·ψ,
			
  *  for every other cut ∅≠ T ⊊ U with Φ_H(T) <  ψ and _H(T) ≤_H(U ∖ T) one has _H(T) ≤λ·_H(R),
			
  *  _H(R) ≤ (1+ξ) _H(U ∖ R),
			
  *  (1-ξ)  ·RU≤ν≤  (1+ξ)  ·RU.
		
	

A balanced sparse cut subroutine is then simply an algorithm returning a balanced sparse cut witness. For convenience of later discussions, we also have the following definition.


	
	Let α,λ≥ 1. An algorithm  is an (α, λ)-balanced sparse cut algorithm (for short, (α,λ)-BSCA) if, taken as input a weighted graph with self-loops H=(U,E',w) and a parameter ψ∈ (0,1), (H,ψ) outputs a (ψ,α,λ,0)-BSCW of H.

Ultimately, we will use either an exponential time brute force BSCA, or a fast BSCA with worse parameters, leading to our exponential and polynomial time ED algorithms, respectively.

Using these definitions, the main result of this section is the following: one can almost seamlessly run a BSCA on the sparsifier, without heavily deteriorating the quality of the BSCW hence obtained.
[Proxying lemma]lemmareduction
	
	Let b, ϕ, c,δ∈ (0,1) such that c ≤ 1/30 is a constant, ϕ < b, b ≤ c, δ≤ c^2b/ log n, and  let  be an (α,λ)-BSCA with α≤1/2b. Fix a cluster U ⊆ V and also let H=(V,E',w) such that H[U] ≈_δ G[U]. Let ω be the output of (H[U]^∘, (1+1/2log n) ·ϕ). Then, ω is a  (ϕ,(1+1/log n)α,(1+c)λ,c)-BSCW of G[U]^∘.

In <ref> and <ref>  we show properties that will let us compare cuts and volumes in H[U]^∘ and G[U]^∘. In <ref> we use these tools to prove <ref>.



 §.§ Characterizing boundary-linked cuts


Structurally, we will divide the cuts of a subgraph G[U]^∘ into two groups: those those that are boundary-linked and those that are not. This concept[The notion of boundary-linked cuts was already used in previous works, but not in the context of sparsification and streaming <cit.>]., which we introduce next, is key to our goal: it captures the cuts that we are able to sparsify to within multiplicative error. Loosely speaking, a cut of G[U]^∘ is boundary-linked if its local cut is a decent fraction of its global cut.


	
	Let β∈ (0,1) be a parameter, let U ⊆ V be a cluster, and let S ⊆ U be a cut. We say that S is β-boundary-linked in U if
	
    SU≥β·min{S, (U ∖ S)}  .


We shall then group the cuts of G[U]^∘ into boundary-linked ones and those that are not. As shown by the two lemmas below, each of these groups has a useful properties for our goal: for a correct set of parameters, boundary-linked cuts are very well approximated by a sparsifier, while those that are not boundary-linked must be sparse.


	
	Let b, ϕ, c,δ∈ (0,1) such that c ≤ 1/2 is a constant, ϕ≤ b, b ≤ c, and δ≤ c^2b/ log n.  Fix a cluster U ⊆ V and also let H=(V,E',w) such that H[U] ≈_δ G[U]. Then, the following hold:
	
		
  *  for all non b/2-boundary-linked cuts ∅≠ S ⊊ U we have SU < ϕ, and
		
  *  for all b/2-boundary-linked cuts S ⊆ U we have (1-c/log n)·SU≤SU≤ 	(1+c/log n)·SU.
	


	To show (<ref>), let ∅≠ S ⊊ U be a cut with SU≥ϕ. By definition this means that SU≥ϕmin{SU,U ∖ SS}. Since SU=(U∖ S)U, we can in fact assume without loss of generality that SU≥ϕSU. Recalling how these volumes are defined, we have that every vertex in u ∈ S has a contribution of at least bϕ·{u}U to SU, so SU≥ b/ϕ·SU. Hence, SU≥ϕSU yields SU≥ b ·SU. Finally, we observe that the global cut of S, i.e. S, can be decomposed as the sum of SU and SU. By virtue of this decomposition, from SU≥ b ·SU we get SU≥ b · (S-SU). Rearranging the terms, and since we assume that b is bounded by c ≤ 1/2, we conclude SU≥ b/2 ·S, i.e. S is b/2-boundary-linked.
	
	To show (<ref>), from definition of boundary-linked we know SU≥ b/2 ·min{S, (U ∖ S)}, while from the assumption that H[U] ≈_δ G[U] we know |SU - SU | ≤δ·S. Again, without loss of generality we can assume SU≥ b/2 ·S, since SU=(U∖ S)U and SU=(U∖ S)U. Therefore, the sparsification error |SU - SU | can actually be bounded by δ·S≤ c^2b/ log n · 2/b ·SU≤  c/log n ·SU (since c≤ 1/2).




 §.§ Preserving volumes and sparsities


 <ref> says that for any cut S in U, either S is sparse, or the sparsifier gives a multiplicative approximation to its local cut. Intuitively, for the latter cuts, one would expect the sparsifier to preserve their sparsity as well. However, this is not trivially true, because the sparsity depends on both the local cut and the volume in the boundary-linked subgraph: while we have a multiplicative preservation of boundary-linked cuts, we may not have the same guarantee for their volume. To circumvent this issue, we consider the case of sparse and expanding cuts separately: the former have in fact their volumes preserved within a relative error, while for the latter we get that their volume in the sparsifier is still not too large. We combine these observations by treating separately boundary-linked and non boundary-linked cuts, and conclude that the distinction between sparse and expanding is very accurately preserved in a sparsifier. We begin with analysing the volume of sparse cuts in the sparsifier.


	
	Let b, ϕ,ϕ̂, c,δ∈ (0,1) such that c ≤ 1/5 is a constant, ϕ < b, δ≤ c^2 / log n, and ϕ̂≤ϕ/b. Fix a cluster U ⊆ V and also let H=(V,E',w) such that H[U] ≈_δ G[U]. Then, for all cuts ∅≠ S ⊊ U with SU < ϕ̂ we have
	
    (1-c/log n) ·SU≤SU≤(1+c/log n) ·SU  .



	By definition of SU, the error in estimating the volume can be written as
	
    |SU- SU| ≤|S- _U(S)| + b-ϕ/ϕ|SU - SU|   .

	The first term is easily upper-bounded by δ·(S), because of the global cut preservation property of H[U] ≈_δ G[U] (see <ref>) applied to singleton cuts. For the second term, we can further split it as
	
    |SU - SU| ≤|S-S|+|SU-SU|   ,

We now upper-bound the right hand side using again the cut preservation properties from <ref>: we employ the multiplicative error for the global cut S, and the additive error for SU. Combining these with the assumption that S is sparse, one gets
	
    |S - S| + |SU-SU| 
    		   ≤  2δ·S
        =   2δ·(SU + SU) 
     since SU < ϕ̂      <  2δ·ϕ̂·_U^∘(S) + 2δ·SU
     since ϕ̂≤ϕ/b and _U^∘(S) ≥ϕ/bSU     ≤ 2δ·ϕ/b·_U^∘(S) + 2δ·ϕ/b·_U^∘(S)
       ≤ 4δ·ϕ/b-ϕ·_U^∘(S)   ,

We now backtrack and plug (<ref>) into (<ref>), and then (<ref>) into (<ref>) to conclude the claim:
	
    |SU- SU|    ≤|S- _U(S)| + b-ϕ/ϕ|SU - SU| 
       ≤δ·(S) + 4δ·_U^∘(S) 
       ≤ 5δ·_U^∘(S) 
       ≤5c^2/log n·SU
       ≤c/log n·SU  ,

since c ≤ 1/5.

Using this fact together with the cut preservation properties of a cluster sparsifier, we can already conclude that there cannot be cuts that look “very” expanding in H[U]^∘ but are actually sparse in G[U]^∘. In particular, if the sparsity of a cut in the sparsifier is above ϕ by a factor that dominates the error of the sparsifier, then its sparsity must be at least ϕ in the original graph. We show this in <ref>.

	
	Let b, ϕ,ϕ̂, c,δ∈ (0,1) such that c ≤ 1/30 is a constant, ϕ < b, b ≤ c, δ≤ c^2 b/ log n, and ϕ̂≥ (1+1/3log n)·ϕ.  Fix a cluster U ⊆ V and also let H=(V,E',w) such that H[U] ≈_δ G[U]. Then, for all cuts ∅≠ S ⊊ U with SU≥ϕ̂ we have SU≥ϕ.


	For the sake of a contradiction, let ∅≠ S ⊊ U be a cut with SU≥ϕ̂ such that SU < ϕ.
	
	Consider first the case that S is b/2-boundary-linked. Then we know from H[U] ≈_δ G[U] (see <ref>) that SU = (1 ± c/log n) SU. Also, as we are assuming SU < ϕ, from <ref> (our parameters verify stronger conditions than what is demanded by the lemma, so it applies) we know SU= (1 ± c/log n)SU. These two together give SU < (1+10c/log n)ϕ < ϕ̂ for small enough c, a contradiction.
	
	Next consider the case that S is not b/2-boundary-linked. Then we do not have a multiplicative approximation to SU. However, S is ϕ-sparse in G[U]^∘ so we still have SU= (1 ± c/log n)SU and U ∖ SU= (1 ± c/log n)U ∖ SU by Lemma <ref>. Therefore, because ϕ̂≥ (1+1/3log n) ϕ we get
	
    SU   ≥(1-c/log n) (1+1/3log n)·ϕ·min{SU, U ∖ SU}
       ≥(1+1/10log n)·ϕ·min{SU, U ∖ SU}  ,

	and at the same time the additive error approximation from <ref> is enough to yield
	
    SU≤SU + δ·S < ϕ·min{SU, U ∖ SU}  + δ·S  .

	Therefore,
	
    S   ≥1/δ·10 log n·ϕ·min{SU, U ∖ SU}
     since δ≤ c^2 b/ log n     ≥1/10c^2·min{SU, U ∖ SU}  .

	Now let us assume SU≤U ∖ SU without loss of generality. Then the above is essentially saying that S is much larger than SU.	Recalling now that we can decompose S=SU+SU, the above lower bound is actually saying that much of the advantage that S has over SU must come from SU. More precisely, since c ≤ 1/30 we get
	
    SU≥1/c·S > b/2·S  ,

	which contradicts the assumption that S is not b/2-boundary-linked.

Next, we handle the case of expanding cuts, and show that their volume does not get overshot too much. Even though this is a much weaker guarantee than the one we obtained in Lemma <ref> for sparse cuts, it will  still be enough for our purposes: this will later be useful in concluding that their sparsity has not dropped by a lot.


	
	Let b, ϕ,ϕ̂, c,δ∈ (0,1) such that c ≤ 1/2 is a constant, ϕ≤ b, δ≤ c^2 / log n, and ϕ̂≤ϕ/b. Fix a cluster U ⊆ V and also let H=(V,E',w) such that H[U] ≈_δ G[U]. Then, for all cuts ∅≠ S ⊊ U with Φ_U^∘(S) ≥ϕ̂ we have
	
    min{SU,U ∖ SU}≤1+c/log n/ϕ̂·SU  .



	Let S^* ∈{S, U ∖ S} be the side of the cut achieving the minimum min{SU, U ∖ SU}. Even though S^*U may not be a very good approximation of S^*U, we can upper-bound it by decomposing  S^*=SU+SU and using the local cut preservation property of H[U] ≈_δ G[U] (see <ref>): we get
	
    S^*U    = S^* - S^*U≤S^*U+δ·S^*  .

Using the above bound, together with the global approximation from <ref> applied to singleton cuts, we can upper-bound S^*U as
	
    S^*U    = S+b-ϕ/ϕSU
       ≤  (1+δ) ·(S^*)+b-ϕ/ϕS^*U + b-ϕ/ϕ·δ·S^*
     since S^*=SU+SU     ≤ (1+δ) ·(S^*)+ (1+δ) ·b-ϕ/ϕ·S^*U+ b-ϕ/ϕ·δ·S^*U
     by definition of SU     ≤ (1+δ) ·_U^∘(S^*)+ b-ϕ/ϕ·δ·S^*U
     since ϕ̂≤ϕ/b     ≤ (1+δ) ·S^*U + δ·1/ϕ̂·S^*U  .

By our assumption that Φ_U^b/ϕ(S) ≥ϕ̂, we also know _U^b/ϕ(S^*) ≤1/ϕ̂SU. We then conclude

    S^*U   ≤ (1+2δ) ·1/ϕ̂SU≤(1+c/log n) 1/ϕ̂SU  ,

since c ≤ 1/2.

Having a bound on the volumes of expanding cuts, allows to bound the sparsity of those cuts in the sparsifier (since all such cuts are boundary-linked, and hence the local cut is well preserved). This is almost the reverse of <ref>.


	
Let b, ϕ,ϕ̂, c,δ∈ (0,1) such that c ≤ 1/6 is a constant, ϕ≤ b, b ≤ c, δ≤ c^2 b/ log n, and ϕ≤ϕ̂≤ϕ/b.  Fix a cluster U ⊆ V and also let H=(V,E',w) such that H[U] ≈_δ G[U]. Then, for all cuts ∅≠ S ⊊ U with SU≥ϕ̂ we have SU≥ (1 - 1/3log n) ϕ̂.


	First note that our parameter regime is strictly stronger than that of <ref> and <ref>. Hence, by <ref>, we know that S is b/2-boundary-linked, since it is ϕ̂-expanding and ϕ̂≥ϕ. <ref> then also guarantees that SU≥ (1-c/log n) SU. On the other hand, <ref> gives min{SU,U ∖ SU}≤ (1+c/log n)/ϕ̂·SU. Hence,
	
    min{SU,U ∖ SU}≤1+c/log n/1-c/log n1/ϕ̂·SU≤1/1-1/3log n·1/ϕ̂·SU  ,

since c ≤ 1/6 is small enough.




 §.§ Proving the proxying lemma


From the previous section, we have that the distinction between sparse and expanding cuts of G[U]^∘ is very accurately preserved by H[U]^∘, and also the volume of sparse cuts of G[U]^∘ is approximated to within a small relative error in H[U]^∘. As these are exactly the quantities that a BSCA is interested in, we can then prove the main lemma of the section, restated here for convenience of the reader.

*


	By definition of , we know that ω is a ((1+1/2log n) ·ϕ, α,λ,0)-BSCW of H[U]^∘, i.e.
	
		
  *  if ω=, then H[U]^∘ is a (1+1/2log n) ·ϕ-expander;
		
  * if ω=(R,ν), then:
		
			
  *  RU < (1+1/2log n) ·α·ϕ,
			
  *  RU≤U ∖ RU,
			
  *  for every other cut ∅≠ T ⊊ U with RU <(1+1/2log n) ·ϕ and TU≤U ∖ TU one has TU≤ B RU:
			
  *  ν =RU.
		
	
Our goal is to translate these properties to G[U]^∘ by showing that ω is a  (ϕ,(1+1/log n)α,(1+c)λ,c)-BSCW of G[U]^∘, i.e.

	
  *  if ω=, then G[U]^∘ is a ϕ-expander;
	
  * if ω=(R,ν), then:
	
		
  *  RU < (1+1/log n) ·α·ϕ,
		
  *  RU≤ (1+c)U ∖ RU,
		
  *  for every other cut ∅≠ T ⊊ U with RU <ϕ and TU≤U ∖ TU one has TU≤ (1+c)B RU:
		
  *  (1-c)·RU≤ν≤ (1+c)·RU.
	


	

  
Correctness of the case ω =. The idea is that if the cluster U is non-trivially more than a ϕ-expander in the sparsifier, then it should be at least a ϕ-expander in G. Let us say that ω=, i.e. SU≥  (1+1/2log n)·ϕ for all ∅≠ S ⊊ U. Let ϕ̂= (1+1/2log n) ·ϕ, so that we are in the parameter regime of <ref>. Then, this lemma ensures that SU≥ϕ for all ∅≠ S ⊊ U. In other words, G[U]^∘ is a ϕ-expander.
	
	

  
Correctness of the case ω=(R,ν).
Assume ω=(R,ν). We need to show the four properties of a BSCW for G[U]^∘.
	
		
  * Property (<ref>). Intuitively, R cannot be much more expanding in G than what it looks like in H, so if it is sparse in H it is basically just as sparse in G. To prove this formally, it is convenient to distinguish the case of this cut being boundary-linked or not.
		
		If R is not b/2-boundary-linked, then <ref> implies RU < ϕ. The property is  then already proved in this case. 
		
		If it is b/2-boundary-linked, suppose for the sake of a contradiction that R has RU≥ (1+1/log n)α·ϕ.  Let ϕ̂=(1+1/log n)α·ϕ. This value of ϕ̂ fulfils the condition that ϕ̂≤ 1/b from <ref>, since α≤ 1/(2b) by assumption. We then meet the requirements to apply <ref> (all other parameters also meet its preconditions, as our parameter regime for b,ϕ,c,ϕ is no weaker than its), so
		
		
    RU≥(1-1/3log n)·(1+1/log n)·α·ϕ≥(1+1/2log n) α·ϕ,

		which contradicts the definition of . We have then showed property (<ref>).
		
		
		
		
  * Properties (<ref>) and (<ref>). From the previous point we know that RU <(1+1/log n)α·ϕ. Since our parameter regime is only stronger than that of <ref> if we set ϕ̂=(1+1/log n)α·ϕ, we get RU= (1 ± c/log n)RU and U ∖ RU= (1 ± c/log n)U ∖ RU. Recalling that RU≤U∖ RU (see (<ref>) for H[U]^∘), this yields
		
    RU≤1/1-c/log nRU≤1/1-c/log nU∖ RU≤1+c/log n/1-c/log nU∖ RU  ,

		so RU≤ (1+c)U∖ RU. Recalling that ν = RU (see (<ref>) for H[U]^∘), one also has
		
    |ν-RU|=|RU-RU|≤ c/log n ·RU≤ c RU  .

		
		
		
		
  * Property (<ref>). This property aims to bound the volume of R against the volume of every other ϕ-sparse cut. We want to exploit the bound that  gives for these cuts in H, i.e. that for every cut ∅≠ T ⊊ U with RU <  (1+1/2log n)  ϕ and TU≤U ∖ TU one has TU≤λRU (see (<ref>) for H[U]^∘). Now one can see that if we prove all such T to be also ϕ-sparse in G[U]^∘, then we could conclude simply using the fact that the volumes of H[U]^∘ are good proxies for those in G[U]^∘. We now implement this strategy.
		
		By virtue of property (<ref>), we have that RU<(1+1/log n)α·ϕ, and from an application of <ref> we have RU= (1 ± c/log n)RU (again, the preconditions of the lemma are met if we take ϕ̂=(1+1/log n)α·ϕ).
		
		Consider now any other cut ∅≠ T ⊊ U with TU < ϕ and TU≤U ∖ TU. Note that for any such T we have TU= (1 ± c/log n)TU and U ∖ TU= (1 ± c/log n)U ∖ TU, again by applying <ref> (setting ϕ̂ =ϕ≤ϕ/b, and all other parameters satisfy the needed preconditions).
		
		Moreover, any such T is also ((1+1/2log n) ·ϕ)-sparse in H[U]^∘, by applying Lemma <ref> with parameter ϕ̂=(1+1/2log n) ϕ≥ (1+1/3log n) ϕ. From (<ref>) for H[U]^∘, we then know
		
    min{TU,U ∖ TU}≤λRU  .

		Recall that RU, TU, U ∖ TU all are within a (1 ± c/log n) multiplicative error of RU, TU, U ∖ TU respectively. Hence, min{TU,U ∖ TU}≤λRU translates to
		
    TU = min{TU,U ∖ TU}≤ (1+10c/log n) λ·RU≤ (1+c) λ·RU  .

	
	We have then proved (<ref>).
	


§ SPACE EFFICIENT RECURSIVE PARTITIONING



The main goal of this section is to show Theorems <ref> and <ref>, restated here for convenience.

*
*
The only difference between the algorithms of Theorem <ref> and <ref> lies in the balanced sparse cut subroutine that they employ. Therefore, we present and analyse them in a unified manner by deferring the choice of the balanced sparse cut algorithm to later. Using the results from <ref> and <ref> (i.e. <ref> and <ref> respectively), we prove the following.


[Unified algorithm]lemmaunified
	
	Let G=(V,E) be a graph given in a dynamic stream, let b ∈ (0,1) be a parameter such that b ≤1/log n. Let  be an (α,λ)-BSCA where α≤1/blog n and λ= O(1). Also let k be an integer such that k ≥log(n^5 α )/log(b^-1/2/λ), and k ≤log n. Then there is an algorithm that maintains a linear sketch of G in ( n/b^3) ·α^O(k) space. For all ϵ∈ [n^-2,blog n], the algorithm decodes the sketch using  to compute, with high probability, a (b,ϵ,ϕ,γ)-BLD of G for
	
    ϕ = Ω(ϵ/αlog n)    and   γ = O(α^k+1)   .

	Moreover, the decoding runs in ( n/b^3) ·α^O(k)+S(n,( n/b^2) ·α^O(k)) space and  T(n,( n/b^2) ·α^O(k)) ·(n) time, where S(p,q) and T(p,q), denote the space and time complexity of  on a graph with p vertices and q edges respectively. Furthermore, the decoding only makes calls to (·, ψ) with sparsity parameters ψ∈ (0,1) that satisfy ψ≤1/10α.


From Lemma <ref> 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.


	It is easy to get an exponential time (1,1)-BSCA as per Definition <ref>. Given a graph and a parameter ψ∈ (0,1), one can do this by brute-forcing all possible cuts in the input graph: either return ω= if all the cuts are ψ-expanding, or return ω=(R,ν) where R is the ψ-sparse cut with maximum volume, and ν is its volume. The space requirement of this algorithm is linear in the size of its input.
	
	We then have parameters α=1,λ=1, and we set k=log n.  Hence, for any b ≤ 1/log^2 n and ϵ≤ b log n, we meet the preconditions  of  <ref>: b ≤ 1/log n, α = 1 ≤1/blog n, λ= O(1), k ≤log n, and
	
    logn^5α/log1/λ√(b)≤O(log n)/Ω(loglog n)≤ k   ,

	where the first inequality follows because α=λ=1, and b ≤ 1/log^2 n.
	Therefore, by <ref> there is a dynamic stream algorithm that with high probability outputs a (b, ϵ, ϕ, γ)-BLD of G where
	
    ϕ = Ω(ϵ/αlog n) = Ω(ϵ/log n)    and   γ = O(α^k+1)= O(1)   .

	Its space complexity is
	
    (k · n/b^3) ·α^O(k) = (n/b^3)   ,

	since for the brute force algorithm we have S(p,q)=(q). The running time is 2^O(n) since the brute force algorithm has T(p,q)=(q)· 2^p.


	For the polynomial time version, we use the following BSCA.
	[<cit.>]theoremfastbalsparse
		
		For p-vertex q-edge input graphs with polynomially bounded edge weights and self-loops, there is a (c_log^3 p,C_)-BSCA that runs in time (p+q) and works with high probability for every input sparsity parameter 0 <ψ≤1/10 c_log^3 p,  where c_,C_≥ 1 are absolute constants.
	
	This easily follows from the ED-based BSCA of <cit.>, combined with the faster ED algorithm of <cit.>, except that here we explicitly allow for input graphs with arbitrary self-loops. We defer to Appendix <ref> a discussion on how to reduce from inputs with self-loops to self-loop free ones. Another technical detail is that the algorithm from <ref> 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/(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 <ref> (i.e. <Ref>) calls  on disjoint portions of (1/b)·α^O(k) sparsifiers (see the proof of <ref>).  Since the running time of this BSCA (with the probability boosting) is (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 (1/b)·α^O(k) sparsifiers, each having at most ( n/b^2) ·α^O(k) edges, we only need  ( n/b^3) ·α^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/(n). As this fits into our claimed space budget, we can then pretend that this BSCA is deterministic. From <ref> we also know that the algorithm never calls  with sparsity parameters larger than 1/10α, so if we set α=c_log^3 n ≥ c_log^3 p our setting matches the requirement of <ref>.
	
	Now we plug α=c_log^3 n,λ=C_ and set k = logn^5 α/logb^-1/2/λ, and verify the preconditions of <ref>. For any b ≤ 1/log^5 n and ϵ≤ b log n, have that λ=C_ = O(1) and
	
    α=c_log^3 n ≤log^4 n ≤1/b log n  .

	We also have that k = O(log n /loglog n) ≤log n, since α = O(log^3 n), λ = O(1), and b ≤ 1/log^5 n. Therefore, the lemma gives a dynamic stream algorithm that with high probability outputs a (b, ϵ, ϕ, γ)-BLD of G where
	
    ϕ = Ω(ϵ/αlog n) = Ω(ϵ/log^4 n)    and   γ = O(α^k+1)= log^O(log n/log 1/b)n   .

	Since the BSCA from <ref> runs in time (q) on a q-edge graph, its space requirement must also be (q). Hence the overall space complexity is
	
    (k · n/b^3) ·α^O(k) + ( n/b^2) ·α^O(k) = (n/b^3)·log^O(log n/log 1/b)n   .

 The running time is (n), since  takes at most (n) time, since in our setting for b, k, and α we have ( n/b^2) ·α^O(k)≤ n^O(1).




  
Overview of the algorithm. We now give the BLD construction for Lemma <ref>. Algorithms <ref> and <ref> outline the core procedure, which is almost the same as the one of <cit.>. For BLD parameters b and ϵ we set ϕ appropriately in terms of ϵ, and our goal is to show that calling Algorithm <ref> as Decompose(V,0) gives a BLD of G.






Algorithm <ref> is a space efficient implementation of <ref> for BLD. In line (<ref>), 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 (<ref>) 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 <ref>. This procedure is supposed to either trim off a small volume mass from the cluster in line (<ref>) so that the remainder induces an expander (see return statement in line (<ref>)), or find a less sparse but more balanced cut than the one obtained in line (<ref>) of <ref> (see return statement in line (<ref>)). In the former case, <ref> can then recurse only on the trimmed part of the cluster (recursion of line (<ref>)), whereas in the latter it is still acceptable to recurse on both sides while keeping the recursion depth under control (recursion of line (<ref>)).


As both algorithms run a BSCA on weighted subgraphs of G, we use <ref> 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 (<ref>) and (<ref>)  in <Ref> respectively via the algorithm from Lemma <ref>. Crucially, we want to instantiate enough independent copies of the sparsification algorithm, so that lines (<ref>) and (<ref>) 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 <ref>.



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



 §.§ Offline analysis


The algorithms have hardwired parameters k,α,λ,C,c. The BLD parameters b,ϕ∈ (0,1) are given as input (for now, we parametrize the BLD by b and ϕ instead of b and ϵ, and will later specify how to define ϕ from ϵ).
Hereafter, whenever we use b,ϕ,k,C,c,α,λ,(b_j)_j,(ϕ_j)_j, we are referring to the corresponding parameter in <Ref>.

As one can see from the pseudocode, the input graph G is not simply fed to <Ref>, but  they have restricted access to it: their interaction with G is limited to lines (<ref>) and (<ref>) 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 <ref>, i.e. they are cluster sparsifiers  with appropriate error (see <ref>).


	
	Every time line (<ref>) of <ref> calls Sparsifier^c_ℓ(U,b) for some ℓ≥ 0,  U ⊆ V, it gets a graph H=(V,E',w) such that H[U] ≈_δ G[U], where δ = c^2b/log n.



	
	Every time line (<ref>) of <ref> calls Sparsifier^c_ℓ,j,h(A,b_j) for some ℓ ≥ 0, j,h ≥ 1, A ⊆ V, it gets a graph H=(V,E',w) such that H[A] ≈_δ_j G[A], where δ_j = c^2b_j/log n.


Throughout this section, we will use the definition δ=c^2b/log n and  δ_j = c^2b_j/log n for all j ∈ [k+1], as in <ref> and <ref>. To illustrate why in the second assumption we have δ_j instead of δ, we make the following observation.

	
	For  a constant c ≤ 1/30, ϕ < b, b ≤ c, α≤1/2b, a cluster A ⊆ V, and a sparsifier  H=(V,E',w) such that H[A] ≈_δ_j G[A], <ref> guarantees that calling an (α,λ)-BSCA as (H[A]^∘, (1+1/2log n) ·ϕ_j) gives a (ϕ_j,(1+1/log n)α,(1+c)λ, c)-BSCW of G[A]^∘  (as in line (<ref>) of <ref>).



For  a constant c ≤ 1/30, parameters b, ϕ, δ,α such that ϕ < b, b ≤ c, α≤1/2b, a cluster A ⊆ V, and a sparsifier  H=(V,E',w) such that H[A] ≈_δ G[A], <ref> guarantees that calling an (α,λ)-BSCA as (H[A]^∘, (1+0.5/log n) ·ϕ) gives a  (ϕ,(1+1/log n)α,(1+c)λ, c)-BSCW of G[A]^∘. Then, we recall that G[A]^∘ = G[A]^b/ϕ and H[A]^∘ = H[A]^b/ϕ, so it also holds that G[A]^∘ = G[A]^b_j/ϕ_j and H[U]^∘ = H[U]^b_j/ϕ_j, since we can see from <ref> that b_j/ϕ_j=b/ϕ for all j ∈ [k+1]. Moreover, observe the following: ϕ < b if and only if ϕ_j < b_j, α≤1/2b implies α≤1/2b_j (by definition of b_j in <ref>), and b ≤ c implies b_j ≤ c (again, by definition of b_j in <ref>). One can then use <ref> replacing b,ϕ,δ with b_j,ϕ_j,δ_j respectively, hence getting <ref>.


The goal of this section is threefold: in <ref>, we bound the number of iterations that any execution of <ref> can go through; in <ref>, we bound the recursion depth of <ref>; in <ref>, we show the output of calling <ref> as (V,0) is a BLD of G. Interestingly,  <ref> crucially uses the results from <ref> and  <ref> about recursion depth and number of iterations. Before, we give some preliminary results: in <ref> we give properties of cuts of boundary-linked subgraphs; in <ref>, we show how relations between volume estimates (such as the comparisons performed by <ref> in line (<ref>) and by <ref> in lines (<ref>) and (<ref>)) translate to relations between the actual volumes of the corresponding cuts.



  §.§.§ Properties of nested cuts


When <ref> makes a cut in the input cluster U, this cut is then fed as input to the recursive call in line (<ref>), which will in turn try to find a cut inside it. Similarly, <ref> makes a cut in the current cluster A in line (<ref>), 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.


	
	Let b, ϕ∈ (0,1) and δ > 0 be such that ϕ≤ b, δ < 1/b. Fix a cluster U ⊆ V, let ∅≠ S ⊊ U be a cut such that SU<δ·ϕ, and let T ⊆ S. Then we have the following relations between volumes:
	
    TU(1)≤TS(2)<TU+δ b ·min{SU, U ∖ SU}(3)≤UU  .

	If it also holds that ∅≠ T ⊊ S has TS < δ·ϕ and T ∪ (U ∖ S)U < 1/2UU then
	
    T ∪ (U ∖ S)U < δ·ϕ  .



For convenience let ψ= δ·ϕ. Inequality (1) holds simply because T ⊆ S ⊆ U, so the number of self-loops attached to T cannot decrease when going from G[U]^∘ to G[S]^∘. Inequality (2) can be obtained by rewriting the volumes in G[S]^∘ as
	
    TS = (T) + b-ϕ/ϕTS    = TU + b-ϕ/ϕ |E(T,U ∖ S)| 
       ≤TU + b/ϕ |E(T,U ∖ S)|   .

	Since S is ψ-sparse in G[U]^∘, we can upper-bound |E(T,U ∖ S)| by SU < ψmin{SU, U ∖ SU}, thus getting the bound. For inequality (3), note TU≤SU because T ⊆ S and δ  b·min{SU, U ∖ SU}≤U ∖ SU for δ≤ 1/b. Since SU+U ∖ SU=UU, we have the bound (3).
	
	Suppose now that ∅≠ T ⊊ S has TS < ψ and T ∪ (U ∖ S)U < 1/2UU. First observe that because TS < ψ, the definition of TS yields TS < ψTS. By <ref>, we also have
	
    TS < ψTS≤ψTU + ψ b/ϕ· |E(T,U ∖ S)| ≤ψTU +|E(T,U ∖ S)|   ,

	where we used that ψ  b / ϕ≤ 1 since ψ = δϕ and δ≤ 1/b. Due to T ∪ (U ∖ S)U < 1/2UU, the definition of T ∪ (U ∖ S)U finally yields
	
    T ∪ (U ∖ S)U    = (T ∪ (U ∖ S))U/T ∪ (U ∖ S)U
    since T ⊆ S, so T ∩ (U ∖ S) = ∅      = TS +SU-|E(T,U ∖ S)|/TU+U ∖ SU
    by (<ref>)      < ψTU + |E(T,U ∖ S)| +SU-|E(T,U ∖ S)|/TU+U ∖ SU
        = ψTU +SU/TU+U ∖ SU
       ≤max{ψ, SU/U ∖ SU} = max{ψ, SU}
    since SU <ψ     ≤ψ  .


<Ref> makes cuts iteratively. It finds a cut in the cluster, it trims it off in line (<ref>), 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 (<ref>)) nor too small (see condition (<ref>)). The following lemma proves properties of such cut sequences. <Ref> should help the reader to visualize the statement and the proof.




	
	Let b, ϕ∈ (0,1) be such that ϕ≤ b, and δ∈ (0,1]. Fix a  cluster U ⊆ V, let θ∈ℝ_≥ 0 be such that θ≤1/5UU, and let R_1, …, R_t be a sequence of cuts ∅≠ R_i ⊊ U^<i where U^<i = U ∖ (∪_z =1^i-1 R_z) for all i ∈ [t]. If
	
		
  *  for all ∅≠  X ⊊ U with XU < δϕ and XU≤U ∖ XU one has XU < θ, and
		
  *  for all i ∈ [t] one has R_iU^<i < δϕ and R_iU^<i < 1/5UU,
	
	then we have the following.
	
		
  *  For all i ∈ [t], one has ∪_z=1^i R_zU < δϕ and  ∪_z=1^i R_zU < θ.
		
  *  For all i ∈ [t], if there is θ^∈ℝ_≥ 0 such that R_iU^<i≥θ^ then one also has R_iU≥θ^-b·θ.
		
  *  Let U^<t+1 = U ∖ (∪_z =1^t R_z). If ∅≠ R ⊊ U^<t+1 is a cut such that RU^<t+1 < δϕ and θ^≤RU^<t+1≤5/9U^<t+1U^<t+1 for some θ^≤4/9UU, then RU < δϕ·UU/θ^-b ·θ and θ^-b ·θ≤RU≤5/9UU.
	

 
 The end goal of part (<ref>) is to upper bound the number of edges crossing and the remaining volume when <ref> returns (A,⊤) and therefore <ref> recurses on U ∖ A only (see line (<ref>) in <ref>). The idea is that in this case U ∖ A corresponds to the union of nested cuts that are trimmed off by <ref>.
 
 Part (<ref>) will be useful to bound the number of iterations that <ref> can take. In every iteration a cut is trimmed off, and from condition (<ref>) we know the volume of these cuts to be not too small in U^<i. From part (<ref>) 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 (<ref>) is to upper bound the number of edges crossing and the remaining volume when <ref> returns (R,) and therefore <ref> recurses on R and U ∖ R (see line (<ref>) in <ref>). The idea is that in this case, every cut trimmed off by <ref> is sparse and far from being balanced (because of condition (<ref>) in <ref>), whereas the last one is both sparse and somewhat balanced (because of condition (<ref>) in <ref>).
 
 

 In the remainder of this section we prove the three parts of this lemma.
 
 	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 ∈ [t]. Denote for convenience ψ = δ ϕ.
 	
 	The base case for i=1 readily follows. Since U^1 =U, we have R_1U < ψ and also R_1U < 1/5UU from precondition (<ref>). Moreover,  by precondition (<ref>), there is no ψ-sparse cut X with θ≤XU < 1/2UU. Hence, it must be the case that R_1U < θ.
 	
 	For the inductive step, take i ∈ [t-1] and assume that ∪_z=1^i R_zU < ψ and ∪_z=1^i R_zU < θ. We now apply Lemma <ref> with S = U^<i+1 and T = R_i+1. We can do so because SU = ∪_z=1^i R_zU < ψ, so the lemma gives
 	
    R_i+1U≤R_i+1U^<i+1≤1/5UU  < 1/4UU  .

 	Combining this bound with the inductive hypothesis that ∪_z=1^i R_zU < θ, one has
 	
    ∪_z=1^i+1 R_zU = ∪_z=1^i R_zU+R_i+1U < θ+R_i+1U < 1/5UU+ 1/4UU  < 1/2UU  ,

 which rewrites as T ∪ (U ∖ S)U < 1/2UU with  S = U^<i+1 and T = R_i+1. Also, from precondition (<ref>), we have R_i+1U^<i+1 < ψ, or in other words TS < ψ with S = U^<i+1 and T = R_i+1. Then, the second part of Lemma <ref> gives ∪_z=1^i+1 R_zU < ψ, so one part of the induction is proved. For the other part, we combine ∪_z=1^i+1 R_zU < ψ and ∪_z=1^i+1 R_zU < 1/2UU with precondition (<ref>): since we assume there is no ψ-sparse cut in G[U]^∘ with volume sandwiched between θ and 1/2UU, it must be the case that ∪_z=1^i+1 R_zU < θ.


 
 	We prove this using part (<ref>) and <ref>. The case of i=1 follows from the preconditions, since U^1=U. Let then i =2, …, t, and denote for convenience ψ = δ ϕ. Then, part (<ref>) gives that ∪_z=1^i-1 R_zU < ψ. If we set S=U^<i and T=R_i we have SU = ∪_z=1^i-1 R_zU < ψ, and can then apply <ref> to get the lower bound
	
    R_iU    > R_iU^<i - δ b ·∪_z=1^i-1 R_zU
    since δ≤ 1     ≥R_iU^<i - b ·∪_z=1^i-1 R_zU  .

	Part (<ref>) also gives ∪_z=1^i-1 R_zU < θ, and since we assume that R_iU^<i≥θ^, one concludes
		
    R_iU > R_iU^<i - b ·∪_z=1^i-1 R_zU≥θ^ - b·θ  .



 
	We begin by analysing the volume RU. Again, from part (<ref>) we have
	
    ∪_i=1^t R_iU < δϕ  ,   ∪_i=1^t R_iU < θ .

	Setting ψ = δϕ, S=U^<t+1 and T=R,  we have SU = ∪_z=1^t R_zU < ψ, so we can apply <ref> to yield
	
    RU > RU^<t+1 - b ·∪_i=1^t R_iU > θ^-b ·θ  ,

	and
	
    RU≤R_tU^<t+1≤5/9U^<t+1U^<t+1  .

	We can once more apply Lemma <ref> with S=T=U^<t+1 (since again SU = ∪_z=1^t R_zU < ψ), so
	
    U^<t+1U^<t+1≤UU  .

	We then have from (<ref>), (<ref>), (<ref>)
	
    θ^-b ·θ≤RU≤5/9U^<t+1U^<t+1≤5/9UU  .

	Next we analyse the sparsity of R by first upper-bounding the quantity RU:
	
    RU   ≤RU^<t+1+(∪_i =1^tR_i)U
    since RU^<t+1 <ψ by assumption      < ψ·RU^<t+1+(∪_i =1^tR_i)U
    since ∪_i =1^tR_iU <ψ from part (<ref>)      < ψ·RU^<t+1+ψ·∪_i =1^tR_iU
    since RU < 5/9UU from (<ref>)      < ψ·5/9·UU+ψ·∪_i =1^tR_iU
    since ∪_i =1^tR_iU< θ from  part (<ref>)      < ψ·5/9·UU+ψ·θ
    by assumption on θ      < ψ·UU  .

On the other hand, the bounds in (<ref>) yield

    min{RU,U ∖ RU}   ≥min{θ^-b ·θ, 4/9UU}
    since θ^≤4/9UU by assumption      = θ^-b ·θ  .

From the bound (<ref>) and (<ref>) we finally conclude

    RU = RU/min{RU,U ∖ RU} < ψ·UU/θ^-b ·θ  .





  §.§.§ Relations between volume estimates


In this section we show how relations between volume estimates (such as the comparisons performed by <ref> in line (<ref>) and by <ref> in lines (<ref>) and (<ref>)) translate to relations between the actual volumes of the corresponding cuts.


	
	Let b, ϕ, c ∈ (0,1) be such that c ≤ 1/4 is a constant and ϕ≤ b. Fix a cluster U ⊆ V, and also let H=(V,E',w) such that H[U]^∘≈_c G[U]^∘, and let ω be a  (ψ,α',λ', c)-BSCW of G[U]^∘ for some ψ∈ (0,ϕ] and α',λ' ≥ 1. If ω = (R,ν) for some ∅≠ R ⊊ U and ν∈ℝ_>0, then for any ρ,τ∈ [0,1] and X ⊆ V we have
	
		
  * if ν≥ρ·(XX)^τ, then RU≥ρ/2 ·(XX)^τ.
		
  * if ν < ρ·(XX)^τ, then RU < 2ρ·(XX)^τ and for every cut ∅≠  S ⊊ U with SU < ψ and SU≤U ∖ SU one has SU < 2λ' ρ·(XX)^τ.
	


	From property (<ref>) of the definition of BSCW (see <ref>), we know (1-c)RU≤ν≤ (1+c)RU, and from property (<ref>) we know  that for every cut ∅≠  S ⊊ U with SU < ψ and SU≤U ∖ SU one has SU < λ'  ·RU.
	
	On the other hand, (1-c)XX≤XX≤ (1+c)XX for any X ⊆ V. To see why, first note that XX=X+b-ϕ/ϕXX=X+b-ϕ/ϕX, and analogously XX=(X)+b-ϕ/ϕX. Then, since H[U]^∘≈_c G[U]^∘, we have the approximation guarantee for global cuts (see <ref>): applying it to all singleton cuts in X we can approximate (X), and applying it to X we can approximate X.
	
	From the above discussion it follows that for all ρ,τ∈ [0,1] and X ⊆ V, ν≥ρ·(XX)^τ implies RU≥ρ1-c/1+c·(XX)^τ≥ρ/2 ·(XX)^τ, since c ≤ 1/4.  If instead ν < ρ·(XX)^τ, we have RU < ρ1+c/1-c·(XX)^τ≤ 2ρ·(XX)^τ. Moreover, since by definition of ω one has SU < λ'  ·RU  for every cut ∅≠  S ⊊ U with SU < ψ and SU≤U ∖ SU, we get SU < λ'  ·RU≤λ' 2ρ·(XX)^τ for any such S.




  §.§.§ Bounding the number of iterations



Combining the structural properties of nested cuts together with <ref>, we can show the correctness of the algorithms. We begin by observing that whenever <ref> breaks the inner loop in line (<ref>) we have j ≤ k. This ensures that restraining the outer loop to indices j=1,…, k+1 (see line (<ref>)) does not lead to undefined behaviour.


	
	Let b, ϕ,c ∈ (0,1) such that c ≤ 1/30 is a constant, ϕ < b and b ≤ c. Also let C ≥ 3 be a constant, and let  be an (α,λ)-BSCA where α≤1/2b. If <ref> holds, then if Algorithm <ref> breaks in line (<ref>) it is in some outer loop iteration j with j ≤ k.


	We prove this by contradiction, so suppose the algorithm enters line (<ref>) with j=k+1 for some inner loop iteration h ≥ 1. Let A be the value of the corresponding variable in <ref> at the beginning of inner loop iteration h within outer loop iteration k+1. Also let H=(V,E',w) be the graph gotten from line (<ref>) in the same iteration. From the description of the algorithm, since it entered line (<ref>), the call (H[A]^∘, (1+1/(2log n)) ·ϕ_k+1) from line (<ref>) has returned a BSCW of the form (R,ν) such that ν< 1/Cλ(UU)^1-(k+1-1)/k=1/Cλ(UU)^0. Moreover, since we have c ≤ 1/30, ϕ < b, b ≤ c, α≤1/2b,  and H[A] ≈_δ_k+1 G[A] (from <ref>), <ref> ensures that (R,ν) is a (ϕ_j,(1+1/log n)α,(1+c)λ, c)-BSCW of G[A]^∘ (see <ref>).
	
	We now want to use Lemma <ref> with ψ = ϕ_k+1, α'=(1+1/log n)α, λ' =(1+c)λ, ρ= 1/Cλ, τ=0, and X=U. These parameters verify the conditions for applying <ref> to (R,ν) on G[A]^∘: c ≤ 1/30 ≤ 1/4, ψ = ϕ_k+1≤ϕ (by definition of ϕ_k+1 in the algorithm), α',λ' ≥ 1, ρ≤ 1, τ∈ [0,1], H[A] ≈_c G[A] (since H[A] ≈_δ_k+1 G[A] and δ_k+1≤ c), and  hence (R,ν) is a (ϕ_j,(1+1/log n)α,(1+c)λ, c)-BSCW of G[A]^∘. Then <ref> gives
	
    RA < 2 ρ (UU)^τ = 2/Cλ < 1   ,

	which in particular implies R=∅. However, this contradicts the fact that (R,ν) is a BSCW of G[A]^∘ (see <ref>).


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


	
	Let b, ϕ,c ∈ (0,1) such that c ≤ 1/30 is a constant, ϕ < b and b ≤ c. Also let C ≥ 11 be a constant, and let  be an (α,λ)-BSCA where α≤1/2b. Consider an execution of <ref> called from <ref> on input cluster U ⊆ V. Also let R_1,…,R_q ⊆ U be the sequence of q cuts trimmed in line (<ref>) by <ref>, and let U^<i=U ∖ (∪_z-1^i-1R_z). If <ref> and <ref> hold, then
	
		
  *  for all ∅≠  S  ⊊ U with SU < ϕ, SU≤U ∖ SU, one has SU<3/CUU,
		
  *  for all i ∈ [q] one has R_iU^<i < ϕ and R_iU^<i < 1/5UU.
	


	From the description of Algorithms <ref> and <ref>, we see that Algorithm <ref> starts only if line (<ref>) of <ref> returns a BSCW ω=(R,ν) such that ν < 1/C λUU, as per line (<ref>) (otherwise, <ref> would not call <ref>). Now we want to apply <ref> to ω. Because we have c≤ 1/30, ϕ < b, b ≤ c, δ=c^2 b/log n, α≤1/2b and H[U] ≈_δ G[U] from <ref>, all the preconditions of <ref> are met for us to apply it to the call (H[U]^∘, (1+1/2log n) ·ϕ) from line (<ref>) of <ref>: hence, ω is a  (ϕ,(1+1/log n)α,(1+c)λ, c)-BSCW of G[U]^∘. Since we observed just above that ω is of the form (R,ν) and ν < 1/C λUU, we now use <ref> with parameters ψ=ϕ, α'=(1+1/log n)α, λ' =(1+c)λ, ρ = 1/Cλ, τ=1, and X=U. These parameters verify the requirement of <ref> since we have c≤ 1/30 ≤ 1/4, H[U] ≈_c G[U] (from <ref>, since δ≤ c), ψ≤ϕ, α',λ' ≥ 1, ρ,τ≤ 1, and  (R,ν) is a (ϕ,(1+1/log n)α,(1+c)λ,c)-BSCW of G[U]^∘. Then we get that for every cut ∅≠  S ⊊ U with SU < ϕ and SU≤U ∖ SU one has
	
    SU < 2λ' ρ·UU = 2(1+c)λ/CλUU≤3/C·UU  .

	This gives part (<ref>).
	
	For all i ∈ [q], denote by j(i) ∈ [k+1] the outer loop iteration of <ref> where R_i was trimmed, and also let U^<i=U ∖ (∪_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 ν_R_i such that (R_i,ν_R_i) was the result of (H[U^<i]^∘, (1+1/2log n) ·ϕ_j(i)-1), where H=(V,E',w) verifies H[U^<i] ≈_δ_j(i) G[U^<i] because of <ref>. As we have c≤ 1/30, ϕ < b, b ≤ c, α≤1/2b, <ref> ensures that the pair (R_i,ν_R_i) is a (ϕ_j(i),(1+1/log n)α,(1+c)λ,c)-BSCW of G[U^<i]^∘ for all i ∈ [q] (see <ref>).  From the description of the algorithm  we also know that ν_R_i must also not satisfy condition (<ref>), as otherwise <ref> would have returned, so ν_R_i < 1/C λUU for all i ∈ [q]. For each i ∈ [q], we now use <ref> with parameters ψ=ϕ_j(i), α'=(1+1/log n)α, λ' =(1+c)λ, ρ = 1/Cλ, τ=1, and X=U. These parameters verify the requirement for applying <ref> to (R_i,ν_R_i) in G[U^<i]: c≤ 1/30 ≤ 1/4, H[U^<i] ≈_c G[U^<i] (from <ref> and δ_j(i)≤ c), ψ=ϕ_j(i)≤ϕ, α',λ' ≥ 1, ρ,τ≤ 1, and (R_i,ν_R_i) is a (ϕ_j(i),(1+1/log n)α,(1+c)λ, c)-BSCW of G[U^<i]^∘. Then, for all i ∈ [q] <ref> gives
	
    R_iU^<i < 2/CλUU < 1/5UU  ,

	since C ≥ 11.
	Furthermore, because every (R_i,ν_R_i) is a (ϕ_j(i),(1+1/log n)α,(1+c)λ, c)-BSCW of G[U^<i]^∘, we have by <ref>
	
    R_iU^<i < (1+1/log n) αϕ_j(i) = (1+1/log n) αϕ/( (1+1/log n) α)^j(i)≤ϕ  ,

	since j(i) ≥ 1. The bounds in (<ref>) and (<ref>) give part (<ref>).


Finally, we argue that <ref> 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 (<ref>), but we can also lower bound the volume of each individual cut.


	
	Let b, ϕ,c ∈ (0,1) such that c ≤ 1/30 is a constant, ϕ < b and b ≤ c. Also let C ≥ 31 be a constant, let  be an (α,λ)-BSCA where α≤1/2b and λ≤c/2b, and let k be an integer such that k ≥logn^2/ϕ/logc/λ· b. If <ref> and <ref> hold, then <ref> goes through at most 1/b inner loop iterations within each outer loop iteration.


	Let U be the input cluster of <ref>. Fix hereafter an outer loop iteration j=1,…, 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 (<ref>) of <ref> 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∈ [t] define A^<h to be the value of variable A at the beginning of inner loop iteration h.
	
	Since <ref> holds,  we also know that to every inner loop iteration h ∈ [t] corresponds a graph H=(V,E',w) from line (<ref>) which satisfies H[A^<h] ≈_δ_j G[A^<h]. As we have c ≤ 1/30, ϕ < b, b ≤ c, α≤1/2b,  and H[A^<h] ≈_δ_j G[A^<h], <ref> ensures that calling (H[A^<h]^∘, (1+1/2log n) ·ϕ_j) gives a (ϕ_j,(1+1/log n)α,(1+c)λ, c)-BSCW of G[A^<h]^∘ in line (<ref>) of <ref> (see <ref>). Moreover, from the description of the algorithm, it must be the case that the BSCW obtained is of the form (R_h,ν_h) for all h ∈ [t-1], where ∅≠ R_h ⊊ A^<h and ν_h ∈ℝ_> 0. One can then see that for every h ∈ [t] we have A^<h=A ∖ (∪_z=1^h-1R_z), and because of conditions (<ref>) and (<ref>) we have that for every h ∈ [t-1] the following holds:
	
    1/Cλ(UU)^1-(j-1)/k≤ν_h < 1/CλUU  .

	We now want to translate the above bounds to R_hA^<h using <ref>. To do so, note that H[A^<h] ≈_δ_j G[A^<h] in particular implies H[A^<h] ≈_c G[A^<h] (since we have defined δ_j=c^2 b_j/log n ≤ c), and as discussed before we know that
	
    (R_h,ν_h) is a (ϕ_j,(1+1/log n)α,(1+c)λ,c)-BSCW of G[A^<h]^∘

	Let us then set ψ=ϕ_j, α'=(1+1/log n)α, λ' =(1+c)λ, ρ = 1/Cλ, τ 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 <ref> to (R_h,ν_h) on G[A^<h]^∘: c ≤ 1/30 ≤ 1/4, ψ =ϕ_j≤ϕ, α',λ' ≥ 1, ρ≤ 1, both values of τ are bounded by 1 (this is because j ≤ k+1), H[A^<h] ≈_c G[A^<h] (since from <ref> we have H[A^<h] ≈_δ_j G[A^<h]), and (R_h,ν_h) is a (ϕ_j,(1+1/log n)α,(1+c)λ,c)-BSCW of G[A^<h]^∘ (see (<ref>)). Then <ref> gives
	
    1/2Cλ(UU)^1-(j-1)/k≤R_hA^<h <2/CλUU  ,

	where the lower bound is obtained with τ=1-(j-1)/k and the upper bound with τ=1. The application of <ref> with τ=1 also gives that for every cut ∅≠  S ⊊ A^<h with SA^<h < ϕ_j and SA^<h≤A^<h∖ SA^<h one has
	
    SA^<h < 2λ' ρ·UU = 2(1+c)λ/CλUU≤3/C·UU  .

	We consider now the case of j=1 and 2 ≤ j ≤ k+1 separately.
	
	

  
Case j=1. In this case A is identical to the input cluster U.	We then want to apply Lemma <ref> with δ=1 and θ = 3/CUU to the sequence of cuts R_1,R_2, …, R_t-1 in the cluster U. Let for convenience U^i = U ∖ (∪_z =1^i-1 R_z) for all i ∈ [t].
	
	First note that this value of θ meets the requirement of <ref> that θ< 1/5UU, since C ≥ 16. Secondly, our set of assumptions matches that of <ref>, so we get that for all ∅≠  S  ⊊ U with SU < ϕ, SU≤U ∖ SU, one has SU<3/CUU, and for all i ∈ [q] one has R_iU^<i < ϕ and R_iU^<i < 1/5UU. These facts match preconditions  (<ref>) and (<ref>) of <ref> for δ and θ as we set them above.
	
	Part (<ref>) of <ref> then upper-bounds the total volume of the sequence as
	
    ∪_h=1^t-1 R_hU < 3/CUU  .

	Since the lower bound of (<ref>) with j=1 means that R_hU^<h≥1/2CλUU for all h ∈ [t-1], using part (<ref>) of <ref> with θ^ =1/2CλUU we further get
		
    R_hU≥1/2CλUU - b·3/CUU≥1/3CλUU   for all h ∈ [t-1]  ,

since  λ≤1/18b.
	Therefore, taking the ratio of the cumulative upper bound in (<ref>) and the individual lower bounds from (<ref>), we conclude that t-1 cannot exceed
	
    ∪_h=1^t-1 R_hU/min_h ∈ [t-1]R_hU≤3/CUU/1/3CλUU≤ 9 λ  .

Thus, the number of inner loop iterations for j=1 is at most 9λ +1 ≤1/2b+1 ≤ 1/b.
	
	

  
Case 2 ≤ j ≤ k+1. The approach is analogous to the first iteration, except that we use the bounds from <ref> on the sequence R_1,…,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 <ref> at the very end of outer loop iteration j-1.
	
	Consider the call (H[A]^∘, (1+1/2log n) ·ϕ_j-1) to  in the last inner loop iteration within outer loop iteration j-1, where H=(V,E',w) is accordingly the graph obtained from line (<ref>) at the last inner loop iteration within outer loop iteration j-1. Since <ref> holds,  we know that the graph H satisfies H[A] ≈_δ_j-1 G[A]. As we have c ≤ 1/30, ϕ < b, b ≤ c, α≤1/2b,  and H[A] ≈_δ_j-1 G[A], <ref> ensures that the call (H[A]^∘, (1+1/2log n) ·ϕ_j-1) gives a (ϕ_j-1,(1+1/log n)α,(1+c)λ,c)-BSCW ω of G[A]^∘ (see <ref>). On the other hand, from the description of the algorithm we know that iteration j starts only if this ω is of the form (R,ν) with ν < 1/C λ(UU)^1-(j-2)/k (due to condition (<ref>)). We now use <ref> with parameters ψ=ϕ_j-1, α'=(1+1/log n)α, λ' =(1+c)λ, ρ = 1/Cλ, τ=1-(j-2)/k, and X=U. These parameters verify the requirement of <ref> since we have c≤ 1/30 ≤ 1/4, H[A] ≈_c G[A] (from <ref> and δ_j-1≤ c), ψ=ϕ_j-1≤ϕ, α',λ' ≥ 1, ρ,τ≤ 1, and (R,ν) is a (ϕ_j-1,(1+1/log n)α,(1+c),cλ)-BSCW of G[A]^∘. Then we get that for every cut ∅≠  S ⊊ A with SA < ϕ_j-1 and SA≤A ∖ SA one has
	
    SA < 2λ' ρ(UU)^τ =  2(1+c)λ/Cλ( UU)^1-(j-2)/k≤3/C·(UU)^1-(j-2)/k  .

	This is still not enough to apply <ref> to cluster A: the bound in (<ref>) bounds the volumes of nested cuts R_h in A^<h by 2/CλUU, but applying <ref> demands an upper bound of 1/5AA 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.
	
	
		
		We have UU≤ 2 AA.
	
	
		If A=U the statement is trivial. Otherwise, we know there must have been a sequence of nested cuts S_1,…,S_r ⊆ U that <ref> trimmed off from U in line (<ref>) so that A=U ∖ (∪_i ∈ [r] S_i). We then want to apply Lemma <ref> to the sequence of cuts S_1,S_2, …, S_r in the cluster U with δ=1 and θ = 3/CUU. Let for convenience U^<i = U ∖ (∪_z =1^i-1 S_z) for all i ∈ [r+1].
		
		First note that this value of θ meets the requirement of <ref> that θ< 1/5UU, since C ≥ 16. Secondly, our set of assumptions matches that of <ref>, so we get that for all ∅≠  S  ⊊ U with SU < ϕ, SU≤U ∖ SU, one has SU<3/CUU, and for all i ∈ [r] one has S_iU^<i < ϕ and S_iU^<i < 1/5UU (the latter follows because part (<ref>) of <ref> bounds the sparsity and volume of every cut in the entire sequence of cuts trimmed by the algorithm, and S_1,…,S_r is a prefix of the entire sequence). These facts match preconditions  (<ref>) and (<ref>) of <ref> for δ and θ as set above. Part (<ref>) of <ref> then upper-bounds the total volume of the sequence as
		
    ∪_i=1^r S_iU < 3/CUU  .

		To conclude it is sufficient to notice
		
    UU    = AU+U ∖ AU
        = AU+∪_i =1^r S_iU
    AA cannot have less self-loops than AU     ≤AA+∪_i =1^r S_iU
    by (<ref>)      < AA+3/CUU  ,

	and the claim follows since C ≥ 6.
	
	
	By <ref> and (<ref>), we have that for every h ∈ [t-1]
	
    R_hA^<h < 2/CλUU≤4/CλAA < 1/5AA  ,

	since C ≥ 21. Furthermore, because every (R_h,ν_h) is a (ϕ_j,(1+1/log n)α,(1+c)λ,c)-BSCW of G[A^<h]^∘, we have
	
    R_hA^<h < (1+1/log n) αϕ_j = (1+1/log n) αϕ/( (1+1/log n) α)^j≤ϕ_j-1  .

	We are now in shape to apply Lemma <ref> to the sequence of cuts R_1,R_2, …, R_t+1 in the cluster A. Specifically, we do this with δ=ϕ_j-1/ϕ and θ = 3/C(UU)^1-(j-2)/k. First observe that δ≤ 1 (by definition of ϕ_j-1) and θ≤3/CUU≤1/5AA (again by <ref> and C ≥ 31), as demanded by <ref>. For these parameters, one can see that precondition (<ref>) is given by (<ref>) and (<ref>). Precondition (<ref>) is instead given by (<ref>). Part (<ref>) of <ref> then upper-bounds the total volume of the sequence as
	
    ∪_h=1^t-1 R_hA < θ =  3/C(UU)^1-(j-2)/k  .

	We are left with lower bounding the volume of each individual cut. We do this with part (<ref>) of <ref> with θ^ = 1/2Cλ(UU)^1-(j-1)/k, which meets the requirement that R_hA≥θ^ thanks to the bound in (<ref>). Part (<ref>) of <ref> then gives that for all h ∈ [t-1]
	
    R_hA≥θ^ - b ·θ = 1/2Cλ(UU)^1-(j-1)/k - b ·3/C(UU)^1-(j-2)/k  .

	Therefore, taking the ratio of the upper bound on the total volume from (<ref>) and the lower bound on the volume of each individual cut from (<ref>), we conclude that t-1 is at most
	
    ∪_h=1^t-1 R_hA/min_h ∈ [t-1]R_hA   ≤3/C(UU)^1-(j-2)/k/1/2Cλ(UU)^1-(j-1)/k - b ·3/C(UU)^1-(j-2)/k
        = 3/C(UU)^1/k/1/2Cλ - b ·3/C(UU)^1/k  .

	Next, we observe that UU≤(V)· b/ϕ≤(V)/ϕ≤ n^2/ϕ (since in the worst case we over-count every edge in G as a self-loop in G[U]^∘ and  at most b/ϕ times). Then, using that k ≥log (n^2/ϕ) / log (c/λ· b), it holds that (UU)^1/k≤c/λ· b. Now we can upper-bound the above as
	
    3/C(UU)^1/k/1/2Cλ - b ·3/C(UU)^1/k≤3/C(UU)^1/k/1/2Cλ - b ·3/Cc/λ· b≤3/C·(n^2/ϕ)^1/k/1/5C λ≤3/C·c/λ· b/1/5C λ = 15 c/b  ,

	since c ≤1/30.	Hence, the number of inner loop iterations for 2 ≤ j ≤ k+1 is at most 15c/b +1≤1/b.




  §.§.§ Bounding the recursion depth


From the description of the algorithms one can see that we recurse on both sides of a cut (in line (<ref>) of <ref>) only when the conditions (<ref>) in <ref> and (<ref>) in <ref> suggest that the cut is balanced, so as to maintain the recursion depth small. When instead <ref> recurses on one side only, in line (<ref>), 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.


	
	Let b, ϕ,c ∈ (0,1) such that c ≤ 1/30 is a constant, ϕ < b, b ≤ c. Also  let C ≥ 16 be a constant, and let  be an (α,λ)-BSCA where α≤1/2b and λ≤1/18b. If <ref> and <ref> hold, whenever Algorithm <ref> with input cluster U ⊆ V makes a recursive call, the recursion is on a cluster ∅≠ X ⊊ U such that
	
    XU < (3Cλ+2α)·ϕ   and   XU≤(1-1/3Cλ)UU  .



	There are three lines where a recursive call can happen: (<ref>), (<ref>), (<ref>). We analyse them separately.
	
	

  
Recursion in line (<ref>). Let H=(V,E',w) be the graph returned in line (<ref>) of <ref>. Since the algorithm recurses in line (<ref>), the call (H[U]^∘, (1+1/2 log n) ·ϕ) of line (<ref>) must have returned a BSCW of the form (R,ν) such that
	
    ν≥1/C λUU  .

	As we have c ≤ 1/30, ϕ < b, b ≤ c, α≤1/2b, and H[U] ≈_δ G[U] (because of <ref>),  Lemma <ref> gives that (R,ν) is a  (ϕ,(1+1/log n)α,(1+c)λ,c)-BSCW of G[U]^∘. By <ref>, this means
	
    RU < (1+1/log n)α·ϕ≤ 2α·ϕ  .

	We now want to use Lemma <ref> with ψ = ϕ, α'=(1+1/log n)α, λ' =(1+c)λ, ρ= 1/Cλ, τ = 1, and X=U. These parameters verify the conditions for applying <ref> to (R,ν) on G[U]^∘: c ≤ 1/30 ≤ 1/4, ψ≤ϕ, α',λ' ≥ 1, ρ≤ 1, τ≤ 1, H[U] ≈_c G[U] (since H[U] ≈_δ G[U] and δ≤ c), and (R,ν) is a (ϕ,(1+1/log n,c)α,(1+c)λ)-BSCW of G[U]^∘. Then <ref> with (<ref>) gives
	
    RU≥ρ/2 (UU)^τ = 1/2CλUU  ,

	which we can use to upper bound the volume of U ∖ R:
	
    U ∖ RU = UU - RU≤( 1 -  1/2Cλ) UU.

	Finally, by property (<ref>) of BSCW applied to R, RU≤ (1 + c) U ∖ RU. Because c ≤ 1/30 ≤ 1/2 and C ≥ 2,
	
    RU≤1+c/2UU≤( 1 -  1/2Cλ) UU.

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

  
Recursion in lines (<ref>) and (<ref>). These cases can only happen if <ref> resorts to <ref>. Let then R_1,…, R_q ⊆ U be the sequence of cuts trimmed off by <ref> in line (<ref>). We then want to apply Lemma <ref> to the sequence of cuts R_1,R_2, …, R_q in the cluster U with δ=1 and θ = 3/CUU. Let for convenience U^<i = U ∖ (∪_z =1^i-1 R_z) for all i ∈ [q+1].
	
	First note that this value of θ meets the requirement of <ref> that θ< 1/5UU, since C ≥ 16. Secondly, our set of assumptions matches that of <ref>, so we get that for all ∅≠  S  ⊊ U with SU < ϕ, SU≤U ∖ SU, one has SU<3/CUU, and for all i ∈ [q] one has R_iU^<i < ϕ and R_iU^<i < 1/5UU. These facts match preconditions  (<ref>) and (<ref>) of <ref> for δ and θ as we set them above.
	
		
  * Line (<ref>). Part (<ref>) of <ref> then upper-bounds the total sparsity and volume of the sequence as
		
    ∪_z=1^q R_zU < ϕ  and  ∪_z=1^q R_zU < 3/CUU  .

		For <ref> to recurse in line (<ref>), it must be the case that <ref> returned a pair (S,⊤) in line (<ref>) (see condition (<ref>)). Looking into <ref>, one can then see that if it returns a pair of the form (S,⊤), it must be the case that S is the value of variable A at the end of the algorithm, i.e. S=A=U ∖ (∪_z ∈ [q] R_z). In line (<ref>), the recursive call is (U ∖ S,ℓ+1), so we recurse on U ∖ S = ∪_z ∈ [q] R_z.  From (<ref>) we then have the claim since C ≥ 6.
		
		
  * Line (<ref>). The difference from the previous case is that for <ref> to recurse in line (<ref>), it must be the case that <ref> returned a pair (S,) in line (<ref>) (see condition (<ref>)), and in particular this implies that <ref> returned in line (<ref>).
		
		Let p be the outer loop iteration where <ref> returns, and let H=(V,E',w) be the graph from line (<ref>) 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 ω be the result of (H[U^q+1]^∘, (1+1/2 log n)ϕ_p) in that same iteration.
		As we have c ≤ 1/30, ϕ < b, b ≤ c, α≤1/2b, and H[U^<q+1] ≈_δ_p G[U^<q+1] (from <ref>), <ref> ensures that ω is a (ϕ_p,(1+1/log n)α,(1+c)λ,c)-BSCW of G[U^<q+1]^∘ (see <ref>). Moreover, since <ref> returned in line (<ref>), it must be the case that ω is of the form (S,ν), where S is the cut returned from <ref> to <ref> in the pair (S,). From the description of the algorithm it must also be the case that
		
    ν≥1/CλUU  .

		As we have c ≤ 1/30 ≤ 1/4, ϕ < b, b ≤ c, α≤1/2b, and H[U^<q+1] ≈_c G[U^<q+1] (from <ref> and δ_p ≤ c), the fact that (S,ν) is a (ϕ_p,(1+1/log n)α,(1+c)λ,c)-BSCW of G[U^<q+1]^∘, and the bound (<ref>), <ref> gives
		
    SU^<q+1≥1/2CλUU  .

		Since (S,ν) is a (ϕ_p,(1+1/log n)α,(1+c)λ,c)-BSCW of G[U^<q+1]^∘, by <ref> we also know
		
    SU^<q+1≤ (1+c) U ∖ SU^<q+1  ,

		so
		
    SU^<q+1≤5/9UU^<q+1  ,

	since c ≤ 1/30 ≤  1/10. Now, setting R=S and θ^=1/2CλUU, the bounds in (<ref>) and (<ref>), together with the fact that θ^≤4/9UU (since C ≥ 2), allow us to apply part (<ref>) of <ref>. This gives
	
    SU    < ϕUU/θ^-b·θ
        = ϕ·UU/1/2CλUU- b ·3/CUU
    since b ≤1/18 λ     ≤ 3Cλ·ϕ  ,

	and
	
    1/3CλUU≤θ^-b·θ≤SU≤5/9UU  .

	We can now conclude: since the result of <ref> is (S,), <ref> recurses on both S and U ∖ S in line (<ref>). Let X ∈{S,U∖ S}. Then from (<ref>) we have that XU < 3Cλ·ϕ, and from (<ref>) we have that XU≤ (1-1/3Cλ) UU since C ≥ 2.
	
	


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


	
	Let b, ϕ,c ∈ (0,1) such that c ≤ 1/30 is a constant, ϕ < b, b ≤ c. Also let C ≥ 16 be a constant, and let  be an (α,λ)-BSCA where α≤1/144Cλ b, λ≤min{1/18b,  1/15C √(b)}. If <ref> and <ref> hold, then the recursion depth of (V,0) (i.e. <ref>) is at most 9Cλ·log n.



	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 <ref> (note that the preconditions are the same except α≤1/144Cλ b≤1/2b and λ≤min{1/18b,  1/15C √(b)}≤1/18b), we get the following: for any recursion from U to X
	
    XU < (2α+3Cλ)ϕ   and   XU≤(1-1/3Cλ) UU

	To get a bound on the recursion depth, we translate these bounds to a bound on XX.
	
	We use <ref> with δ=3Cλ+2α, S=X, and T=X. These setting verifies the requirements of <ref>: δ≤ 1/b (since α≤1/4b, and λ≤1/6Cb), SU < δϕ from (<ref>), and T ⊆ S. Hence, inequality (2) from <ref> gives
	
    XX    = TS
    inequality (2) of <ref>     < TU + δ b ·min{SU, U ∖ SU}
       ≤  (1+δ b) ·XU
    from (<ref>)     ≤(1+δ b) (1-1/3Cλ) UU
    since α≤1/144Cλ b and λ≤1/15C √(b)     ≤(1+1/36Cλ) (1-1/3Cλ) UU
       ≤(1-1/4Cλ) UU  .

	From this we conclude that if we do a recursion on X at level ℓ, then
	
    XX≤(1-1/4Cλ)^ℓVV =  (1-1/4Cλ)^ℓ(V) <  (1-1/4Cλ)^ℓ n^2   .

	The bound follows.




  §.§.§ Correctness



Finally, one can see from the algorithms that they recurse only on the sides of cuts resulting from . 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.


	
	Let b, ϕ,c ∈ (0,1) such that c ≤ 1/30 is a constant, ϕ < b, b ≤ c. Also let C ≥ 31 be a constant, let  be an (α,λ)-BSCA where α≤1/144Cλ b, λ≤min{1/18b,  1/15C √(b)}, and let k be an integer such that k ≤log n. If <ref> and <ref> hold, then the result of (V,0) (i.e. <ref>) 
	is a (b,ϵ,ϕ,γ)-BLD of G where
	
    ϵ = 4 (3Cλ+2α) ·ϕ· 9Cλ·log n ·^2b (3Cλ+2α) 9Cλ·log n   and   γ = 6 α^k+1  .




	First note that our assumptions subsume the preconditions of <ref>. Hence, if Algorithm <ref> breaks in line (<ref>) it is in some outer loop iteration j with j ≤ k, so the behaviour of the algorithm is well defined (see the outer loop for j=1,…,k+1 in line (<ref>) of <ref>).
	
	From the description we then see that (V,0) always outputs a valid partition 𝒰 of V. We show that 𝒰 verifies the two properties of Definition <ref>.
	
	

  
Property (<ref>). Let X ∈𝒰, which can either be the result of the return statement in line (<ref>) or in line (<ref>) of Algorithm <ref>.
	
		
  * Return statement in line (<ref>). Let U ⊆ V be the input cluster to the  instance of <ref> that returned X. Also let H=(V,E',w) be the graph from line (<ref>) and ω be the result of (H[U]^∘, (1+1/2 log n) ·ϕ) in line (<ref>) of that same instance. From the description of the algorithm, we know that the return statement in line (<ref>) only occurs if ω=, and in particular X is the input cluster U.
		
		As our parameter regime implies c ≤ 1/30, ϕ < b, b ≤ c, α≤1/2b, and also we have H[U] ≈_δ G[U] from  <ref>, we can use Lemma <ref>. This ensures that ω is a (ϕ,(1+1/log n)α,(1+c)λ,c)-BSCW of G[U]^∘. From <ref>, ω= implies that G[U]^∘ is a ϕ-expander.
		
		
  * Return statement in line (<ref>).  In this case, <ref> must have called <ref>, which in turn returned a pair (S,⊤). Then, <ref> must have returned in line (<ref>). Denoting by A the value of the corresponding variable in <ref> when it returns, we must have A=X. Also let  p ∈ [k+1] be the outer loop iteration where <ref> returns, let H=(V,E',w) be the graph from line (<ref>), and let ω be the result of (H[A]^∘, (1+1/2 log n) ·ϕ_p) in line (<ref>) of the inner loop iteration where the algorithm returns.
		
		As our parameter regime implies c ≤ 1/30, ϕ < b, b ≤ c, α≤1/2b, and also we have H[A] ≈_δ_p G[A] from  <ref>, we can use Lemma <ref>. This ensures that ω is a (ϕ_p,(1+1/log n)α,(1+c)λ, c)-BSCW of G[U]^∘ (see <ref>). From <ref>, ω= implies that G[A]^∘=G[X]^∘ is a ϕ_p-expander. Since p ≤ k+1, k ≤log n, and ϕ_p is defined as
		
    ϕ_p = ϕ/((1+1/log n)α)^p  ,

		we conclude that G[X]^∘ is in fact a ψ-expander with
		
    ψ = ϕ/((1+1/log n)α)^p≥ϕ/((1+1/log n)α)^k+1≥ϕ/6α^k+1  .

	
	From the above case analysis we conclude that for every X ∈𝒰, G[U]^∘ is a ϕ/γ-expander with γ = 6 α^k+1.
	
	

  
Property (<ref>). 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λ·log n. We can then employ Lemma <ref> (since our set of assumptions matches that of the lemma), which bounds the recursion depth by D.
	
	Next, for ℓ=0,1,…, D, let ℐ^ℓ be the set of instances of Algorithm <ref> at the ℓ-th level of the recursion triggered from (V,0). Each instance ℐ∈ℐ^ℓ is a pair ℐ=(U,X), where U ⊆ V is the input cluster to the instance, and:
	
		
  *  if the instance returns {U} in line (<ref>), then X=∅;
		
  * if the instance makes a recursive call, then ∅≠ X ⊊ U is a set on which the instance invokes Algorithm <ref>.
	
	Then, since our set of assumptions matches that of <ref>, we get that XU < (2α+3Cλ)ϕ for every ℓ = 0,…, D and every (U,X) ∈ℐ^ℓ such that X≠∅. Hence,
	
    for all ℓ = 0,…, D, and all (U,X) ∈ℐ^ℓ, we have   XU < (2α+3Cλ)ϕXU  .

	With this notation, define the set of edges cut at level ℓ to be
	
    C_ℓ = ⋃_(U,X) ∈ℐ^ℓ E(X,U ∖ X)   .

	Now let μ = (3Cλ+2α), and for ℓ=0, …, D also define
	
    T(ℓ) = μϕ(V) +2  μ· b∑_ℓ'=0^ℓ-1T(ℓ')   .

	To bound the number of inter cluster edges, we first show that |C_ℓ| ≤ T(ℓ), then we resolve the recurrence T(ℓ), and finally we sum over ℓ=0,…, D to conclude.
	
	
		
		For every ℓ=0,1,…, D one has |C_ℓ| ≤ T(ℓ).
	

	We prove the statement by induction. At level 0 there can be only one instance (V,X) ∈ℐ^0, so the number of edges cut is |C_0| = XV. By (<ref>)
	
    |C_0| < μϕXV =  μϕ(X) ≤μϕ(V) = T(0)   ,

thus proving the base case.

Next take any 1 ≤ℓ≤ D, and assume that |C_ℓ'|≤ T(ℓ') for all ℓ'=0,…, ℓ-1. By (<ref>) we know XU < μϕ·XU for all (U,X) ∈ℐ^ℓ. Using the definition of XU, we get
	
    XU  < μϕ·XU    =  μϕ·((X) + b-ϕ/ϕXU) 
    since XU≤U     ≤μϕ·(X) + μ b ·U  .

	Observe that the union of all E(U , V ∖ U) on level ℓ is a subset of all edges cut on previous recursion levels. This means that
	
    ∑_(U,X) ∈ℐ^ℓU≤ 2 ∑_ℓ' =0^ℓ-1 |C_ℓ'|   ,

	since every e ∈ C_ℓ' is counted at most twice by the sum over ℐ^ℓ.

	Using the induction hypothesis and observing that the cuts {X : (U,X) ∈ℐ^ℓ} must be disjoint, we can upper-bound |C_ℓ| as
	
    |C_ℓ|     = ∑_(U,X) ∈ℐ^ℓXU
    by (<ref>) and disjointness of the X's      < μϕ(V) + μ  b ∑_(U,X) ∈ℐ^ℓU
    by (<ref>)     ≤μϕ(V) + 2 μ  b ∑_ℓ' =0^ℓ-1 |C_ℓ'| 
    by the induction hypothesis     ≤μϕ(V) + 2 μ b ∑_ℓ' =0^ℓ-1 T(ℓ') 
        = T(ℓ)  .

	thus showing the inductive statement.

Now we solve the recurrence.

	
	T(ℓ) ≤μϕ(V) (1+2μ b)^ℓ for all ℓ≥ 0.


	Let ℓ≥ 1 and assume the statement holds true for all 0≤ℓ'≤ℓ-1. Then,
		
    T(ℓ)     = μϕ(V) + 2μ b ∑_ℓ'=0^ℓ-1 T(ℓ') 
       ≤μϕ(V) + 2μ b ∑_ℓ'=0^ℓ-1μϕ(V) (1+2μ b)^ℓ'
        = μϕ(V) (1+2μ b∑_ℓ'=0^ℓ-1 (1+2μ b)^ℓ') 
        = μϕ(V) (1+2μ b (1+2μ b)^ℓ-1/1+2μ b-1) 
        = μϕ(V) (1+2μ b)^ℓ  .


	Now combing <ref> and <ref>, one has that the number of inter-cluster edges in 𝒰 is
	
    ∑_U ∈𝒰U≤ 2 ∑_ℓ=0^D |C_ℓ| ≤ 2 ∑_ℓ=0^D T(ℓ) ≤ 2 μϕ(V)· (D+1) · (1+2μ b)^D≤ 4 μ·ϕ·(V) · D ·  e^2bμ D  .





 §.§ Dynamic stream implementation


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

*


	Let C=40, c=1/40, and define the quantities D=9Cλ·log n, δ=c^2b/log n, and δ_j=δ· (α(1+1/log n))^-j for j ∈ [k+1]. We process the stream as follows.
	
		
  * We maintain D+1 independent samples from the distribution 𝒟_δ using the algorithm of  <ref>, resulting in a collection of sparsifiers H_ℓ for 0 ≤ℓ≤ D.
		
  * For every j ∈ [k+1], we maintain (D+1) · 1/b samples from the distribution 𝒟_δ_j using the algorithm of  <ref>, resulting in a collection of sparsifiers H_ℓ,j,h for 0 ≤ℓ≤ D, j ∈ [k+1], h ∈ [1/b].
	
	
	After having processed the stream as described above, we want to use <ref>  and <ref> to decode these samples into a BLD. In <ref> and <ref> we have hardwired parameters k,α,λ,C,c: the parameters k,α,λ are as in the lemma statement, and C,c are set as defined above (i.e. C=40, c=1/40). <ref> and <ref> also use BLD parameters b,ϕ: b is just the value in the lemma statement, and we set
	
    ϕ = ϵ/4 (3Cλ+2α) · D ·^2b (3Cλ+2α) 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 ≤ℓ≤ D,  we define the procedure Sparsifier^c_ℓ(U,·) from line (<ref>) in <ref> to return H_ℓ for every U ⊆ V;  similarly, for 0 ≤ℓ≤ D, j ∈ [k+1], h ∈ [1/b], we define the procedure Sparsifier^c_ℓ,j,h(A,·) from line (<ref>) in <ref> to return H_ℓ,j,h for every A ⊆ V.
	
	

  
Correctness. Since C,λ = O(1), α b ≤ 1/log n, D = O(log n), one can see that ϕ= Ω(ϵ/αlog n). From this value of ϕ we also get ϕ < b, since C,λ,α≥ 1, ϵ≤ b log n, the exponential is at least 1, and D > log n . Then, our parameter regime has all the conditions for using <ref>, <ref>, <ref>: we have an (α,λ)-BSCA , ϕ < b, b ≤ 1/log n ≤ c ≤ 1/30, C ≥ 31, α≤1/b log n≤1/144C λ b≤1/2b, λ = O(1) so λ≤min{1/18b,  1/15C√(b), c/2b},  k ≥logn^5 α/logb^-1/2/λ implies k ≥logn^2/ϕ/logc/λ· b (since ϕ= Ω(ϵ/αlog n), ϵ≥ 1/n^2, and c is a constant), and k ≤log n. We now just want to lift <ref> and <ref>, so as to apply these lemmas. From our definition of Sparsifier_ℓ(U,·) and Sparsifier_ℓ,j,h(A,·) above, we have the following claim.
	
		
		Assumptions <ref> and <ref> hold with high probability as long as ℓ≤ D and h ≤ 1/b.
	
	
		The claim follows from the way we process the stream, described above, and from our definition of Sparsifier^c_ℓ(U,·) and Sparsifier^c_ℓ,j,h(A,·).
		
			
  * For every 0 ≤ℓ≤ D and any U ⊆ V, Sparsifier^c_ℓ(U,·) outputs the graph H_ℓ, independently sampled from 𝒟_δ.  <ref> only calls Sparsifier^c_ℓ(U,b) for a cluster U that was found using randomness from levels before ℓ (simply by the description of the algorithm, see recursive calls in lines (<ref>), (<ref>), (<ref>) of <ref>). Thus, by <ref> we know that H_ℓ[U] ≈_δ G[U] with high probability. Since there can be at most n calls to Sparsifier^c_ℓ(U,b) for any ℓ, we can conclude that H_ℓ works for each of them with high probability.
			
  * For every 0 ≤ℓ≤ D, j ∈[k+1], h ∈ [1/b] and any A ⊆ V, Sparsifier^c_ℓ,j,h(A,·) outputs the graph H_ℓ,j,h, independently sampled from 𝒟_δ_j. Similarly as before, we can see from the description of <ref> that Sparsifier^c_ℓ,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 <ref>) or a previous iteration (in case A was updated in line (<ref>)). Thus, A is independent from H_ℓ,j,h. Thus, by <ref> we know that H_ℓ,j,h[A] ≈_δ_j G[A] with high probability. Also in this case there can be at most n calls to Sparsifier^c_ℓ,j,h(A,b_j) for any triple ℓ,j,h, so H_ℓ,j,h works for each of them with high probability.
		
	
	Provided  <ref> and <ref> hold, <ref> and <ref> are guaranteeing that there is no point in the execution of the algorithm with recursion level ℓ larger than D or with inner loop index h (see line (<ref>)) larger than 1/b. On the other hand, <ref> ensures that <ref> and <ref> hold with high probability as long as ℓ≤ D and h ≤ 1/b. Hence, we have that the results from <ref>, <ref>, <ref> hold simultaneously with high probability. In particular, the output 𝒰 of (V,0)
	is a (b,ϵ,ϕ,γ)-BLD of G with high probability for γ = O(α^k+1) (note that we set ϕ exactly by rearranging the value of ϵ given by <ref>).
	
	

  
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  for the decoding phase. From <ref> we know that sampling from 𝒟_δ can be done by maintaining a linear sketch of (n/δ^2) bits, and sampling from 𝒟_δ_j can be done maintaining a linear sketch of (n/δ_j^2) bits.  Since we maintain D+1 samples from 𝒟_δ, and (D+1) · 1/b samples from 𝒟_δ_j for every j ∈ [k+1], the space complexity for processing the stream is
	
    (D+1) ·(n/δ^2) + (D+1) ·1/b·∑_j=1^k+1(n/δ_j^2)   .

	Because we defined D=9Cλ·log n, δ=c^2b/log n, δ_j=δ· (α(1+1/log n))^-j, and we have C,λ = O(1), k = O(log n), c = Ω(1), we use at most
	
    O(log n) (n/b^2) + O(log n)  O(1/b)O(k) ·(n/b^2) ·α^O(k) = (n/b^3) ·α^O(k)

	bits of space for the sparsifiers. Finally, note that <Ref> run  on sparsifiers with at most n vertices and at most
	
    max{(n/δ^2),max_j ∈ [k+1]{(n/δ_j^2)}} =  (n/b^2) ·α^O(k)

	edges, by <ref>. As we can reuse the space for each call, this takes an extra S(n,(n/b^2)α^O(k)) bits of space, leading to the claimed space complexity for the decoding.
	
	

  
Time complexity.
	Throughout the recursion of (V,0),  <Ref> make at most (n) calls to . As noted above, each of these calls is on a graph with at most n vertices and (n/b^2)α^O(k) edges. <ref> also guarantees that decoding the linear sketch to get a sample from 𝒟_δ and 𝒟_δ_j takes (n) time. Hence the running time of the decoding is (n)· T(n,(n/b^2)α^O(k)).
	
	

  
Sparsity parameter in BSCA calls. By the way we set ϕ and by definition of the algorithm, we have that every call to (·, ψ) is made with a sparsity parameter ψ∈ (0,1) that is ψ≤ϕ≤1/10α.
	



§ 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.

*
By Yao's minimax principle, it is sufficient to give a distribution 𝒢 over graphs with vertex set V such that any deterministic streaming algorithm that computes, with probability at least 0.9, an (ϵ,ϕ,ℓ)-RED of G ∼𝒢  takes Ω(n/ϵ) 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 ∼𝒢  in an arbitrary order serves our purposes.

We then proceed as follows. In <ref> we describe our hard distribution over graphs, and show a structural property of its two-level (ϵ,ϕ)-RED. In <ref> we introduce a communication problem, , and show a reduction to RED. Finally, in <ref> we give a communication lower bound for . We combine these results into proving <ref> in <ref>.




 §.§ Hard distribution


The randomness of our hard distribution 𝒢 arises from sampling Erdős-Rényi graphs. We recall the definition for convenience of the reader.

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

Let d,m be integers such that 3 ≤ d < m < n. We now define our hard distribution 𝒢 over n-vertex  graphs G=(V, E), and we illustrate it in <Ref>.


	
 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,…,S_n/m with m/2 vertices each. The distribution 𝒢_n,d,m is supported over graphs G=(V,E) where E is defined as follows.



  * For each i ∈ [n/m], the induced subgraph G[S_i] is sampled independently from the Erdős-Rényi distribution (m/2,4d/m) (see Definition <ref> above). We denote by 𝒢'_n,d,m the distribution of the subgraph G[S], i.e. 𝒢'_n,d,m= (m/2,4d/m)^⊗ n/m.


  * The induced subgraph G[T] is a fixed d-regular ψ-expander, for ψ = Ω(1) independent of d, m, n. 


  * We fix for convenience an arbitrary labelling s_i,1,…,s_i,m/2 of the vertices in each S_i,   i ∈ [n/m], and we sample K ∼([m/2]). Then, for every i∈ [n/m], we add dm/2 edges from s_i,K to T so that each t ∈ T has d incident edges in E(S,T) (one way to do so is by partitioning T into n/(dm) subsets T_1, …, T_n/(dm) with dm/2 vertices each and connecting s_i,K to each vertex of T_⌈ i/d ⌉ for every i ∈ [n/m]).

Since the parameters n,d,m are fixed hereafter, we may drop the subscript from 𝒢_n,d,m and 𝒢'_n,d,m and simply denote them by 𝒢 and 𝒢' respectively.




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 <Ref>. 



 
	
Let G=(V,E) ∈(𝒢). Denote by k ∈ [m/2] the unique index such that {s_i,k:i ∈ [n/m]}= {s ∈ S: {t ∈ T: {s,t}∈ E}≠∅}. Then, we define the set of important vertices V^*={s_i,k:i ∈ [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 ∈ S  , v^* ∈ V^*} to be the set of edges in the induced subgraph G[S] that are incident on V^*.



	
	Note that any sample G ∼𝒢 can be defined by (G',K), where G'=(S,E') is the graph consisting of the disjoint union of the subgraphs (G[S_i])_i ∈ [n/m], and K ∈ [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 ∼𝒢, and the edges E(S,T) are determined by K. By virtue of this observation we abuse notation and write G=(G',K) ∼𝒢. Moreover, for any (G',K) ∼𝒢 one has G' ∼𝒢', and conversely, for any G' ∼𝒢' and K ∼([m/2]) one also has (G',K) ∼𝒢.


In the remainder of the section, we call a graph (1 ±δ)Δ-regular for an integer Δ>0 and δ∈ [0,1], if each of its vertices has degree in the range [(1-δ)Δ , (1+δ)Δ]. With this terminology, we show that in any valid (ϵ,ϕ)-ED of G, most of the important edges are crossing edges, as depicted in <Ref>. This works under the assumption that each G[S_i] is a near-regular expander.



 
	Let G=(V,E) ∈(𝒢), and let ϵ,ϕ∈ (0,1) such that ϵ≤ 10^-5·ψ·d/m and ϕ≥ 11/m. If n ≥ 100 m, m≥ 500, and every subgraph (G[S_i])_i ∈ [n/m] is a (1 ± 1/10)2d-regular 1/3-expander, then any (ϵ,ϕ)-ED 𝒰 of G satisfies
	
    | E^* ∖𝒰| ≥4/5·| E^*|   .



 
	Let G=(V,E) ∈(𝒢) and let k ∈ [m/2] such that the important vertices are s_i,k for i ∈ [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 <ref> together with our assumption, the graph G has at most 11/10· dn/2+3/4 · dn ≤ 1.3 dn edges.
	
	Hereafter, let 𝒰 be any (ϵ,ϕ)-ED of G. We begin by arguing that there is a giant cluster in 𝒰 that covers most of T and most of the important vertices.
	
	
		
		There is a component U^* ∈𝒰 such that
		
    |T ∩ U^*| ≥(1-12ϵ/ψ) |T|   and   |V^* ∩ U^*| ≥(1-12ϵ/ψ) |V^*|   .

	
	
		For any valid (ϵ,ϕ)-ED 𝒰, we must have |E ∖𝒰| ≤ϵ· 1.3 dn. Since G[T] is a d-regular ψ-expander, there is a component U^* ∈𝒰 that contains at least (1-3 ϵ/ψ) · n/2 vertices from T, i.e.
		
    |T ∩ U^* | ≥(1-3ϵ/ψ)·n/2 = (1-3ϵ/ψ)|T|     .

		To see why, note that if this was not the case then we could construct a cut S = ∪_U ∈𝒰' U ∩ T for some 𝒰' ⊆𝒰 such that 3ϵ/ψ· |T| < |S| ≤ |T|/2 and conclude that there would be at least ψ_G[T](S) > ϵ· 1.5 dn edges crossing 𝒰.
		
		Since each vertex in T has an edge to d important vertices (see <ref>), there are at least (1-6ϵ/ψ) · n/m important vertices with at least dm/4 neighbours in U^* ∩ T, i.e.
		
    |{s ∈ V^*:  |{t ∈ U^* ∩ T: {s,t}∈ E}| ≥1/4dm}| ≥(1-6ϵ/ψ) ·n/m = (1-6ϵ/ψ)· |V^*|   .

		To see why, note that if this was not the case, we would have |{s,t}∈ E:  s ∈ V^*  , t∈ T ∖ U^* }| to be larger than (6ϵ/ψ· n/m) · dm/4, which is impossible since every t ∈ T has d incident edges in E(S,T) and |T ∖ U^*| ≤ 3ϵ/ψ· n/2.
		
		Now, because most of the important vertices have many edges to T ∩ U^*, most of these should also be in U^*, otherwise too many edges would cross: since |E ∖𝒰| ≤ϵ· 1.3 dn, there must be at most 6ϵ/ψ· n/m+ϵ· 1.3 dn/dm/4≤ 12ϵ/ψ· n/m important vertices that are not in U^*, i.e.
		
    |V^* ∩ U^*| ≥(1-12ϵ/ψ) ·n/m  =  (1-12ϵ/ψ) · |V^*|   .

	
	We want to confine our attention to important vertices whose corresponding subgraph G[S_i] locally preserves property (<ref>) of <ref>, i.e. has few inter-cluster edges as compared to its own volume. Formally, we consider the set of good vertices, defined as
	
    V^*_g = {s_i,k∈ V^* : s_i,k∈ U^*   , |(E ∖𝒰) ∩S_i2| ≤200ϵ dm}  .

	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^*.
	
	
		
		Let s_i,k∈ V^*_. Then, there is a cluster U ∈𝒰 such that
		
    s_i,k∉ U   and   |U∩ S_i| ≥(1-700ϵ)  |S_i|   .

	

	Since G[S_i] is a (1 ± 1/10)2d-regular 1/3-expander by assumption, there is at least one component U ∈𝒰 containing at least (1-700ϵ)m/2 vertices in S_i, i.e.
	
    |U ∩ S_i| ≥(1-700ϵ) m/2  = (1-700ϵ)  |S_i|   ,

	To see why, note that if this was not the case we could construct a cut R = ∪_W ∈𝒰' W ∩ S_i for some 𝒰' ⊆𝒰 such that 10/9 · 700ϵ· |S_i| < |R| ≤ 9/11 ·  |S_i|/2 and conclude that there would be at least 1/3·_G[S_i](R) > 230ϵ dm edges crossing 𝒰 inside S_i, contradicting the fact that s_i,k∈ V^*_ (see the definition in (<ref>)).
	
	Hereafter, let U ∈𝒰 be the cluster that satisfies (<ref>) (which is unique, since ϵ≤ 10^-5). We know from <ref> that there is a cluster U^* ∈𝒰 that contains all good vertices (by definition of good vertex, see (<ref>)) and that covers most of T.	To show that s_i,k∉ U, we leverage the fact that s_i,k∈ U^* and that G[U^*] must be a ϕ-expander by property (<ref>) of <ref>. Suppose towards a contradiction that U^* = U, and let Q = (U^* ∩ S_i) ∖{s_i,k}. Because G[S_i] is (1 ± 1/10)2d-regular, the volume of this set in G[U^*] is at least
	
    _G[U^*](Q)    ≥ -_G[S_i](s_i,k) + ∑_u ∈ U^* ∩ S_i_G[U^* ∩ S_i](u) 
       ≥  -11/102d + ∑_u ∈ U^* ∩ S_i: _G[U^* ∩ S_i](u) ≥ (1-600ϵ) _G[S_i](u)_G[U^* ∩ S_i](u)   .

	We next observe that the sum above has at least |U^* ∩ S_i|/2 many terms, for if this was not the case we would have at least 300ϵ |U^* ∩ S_i| · 9/10 ·  2d ≥ 200ϵ dm edges from U^* ∩ S_i to S_i ∖ U^*, which would contradict s_i,k∈ V^*_ (see the definition in (<ref>)). We then continue from above and hence get
	
    _G[U^*](Q)    ≥  -11/102d + 1/2 |U^* ∩ S_i|·(1-600ϵ) _G[S_i](u)
       ≥  -11/102d + 1/2 |U^* ∩ S_i|·(1-600ϵ) 9/10 2d
    since |S_i ∩ U^*| ≥ (1-700ϵ) |S_i|     ≥ -11/102d+9/102d 1/2(1-1400ϵ) m/2  .

	Moreover, we know that |U^* ∩ T| ≥ (1-3ϵ/ψ)n/2 ≥ (1-1/8000)n/2 by our assumption on ϵ, so the fact that G[T] is d-regular implies _G[U^*](U^*) ≥_G[U^* ∩ T](U^* ∩ T) ≥ dn/10. Also, by near-regularity of G and because m ≤ n/100, we have _G[U^*](Q) ≤ 3d · m/2 < dn/20 ≤1/2_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.
	
    QU^* = _G[S_i](s_i,k) ≤11/10 2d   .

	Therefore, U_i = U^* implies
	
    Φ_G[U^*]≤Φ_G[U^*](Q) = QU^*/_G[U^*](Q)≤11/10 2d/9/10d (1-1400ϵ) m/2-11/102d≤10/m < ϕ  ,

	a contradiction. Here we used that m ≥ 500, ϕ≥ 11/m, and ϵ≤ 10^-5.

	By virtue of <ref>, we have the following setting: for every good vertex s_i,k∈ V^*_g, there is one component U covering a (1-700ϵ) 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'}∈ E^* :   s = s_i,k, s' ∉ U^*}⊆ E(U^* ∩ S_i, S_i ∖ U^*) ⊆ E ∖𝒰  for all s_i,k∈ V^*_g,

	and
	
    |U^* ∩ S_i| ≤  |U ∖ S_i| ≤ 700ϵ  |S_i| = 700ϵm/2  for all s_i,k∈ V^*_g.

	In particular, the above conditions implies that, among the important edges incident on each good vertex, at most 700ϵ· m/2 of them can land in the same cluster U^* as the good vertex itself, i.e.
	
    |{{s,s'}∈ E^* :   s = s_i,k, s' ∉ U^*}| ≥9/102d - 700ϵm/2  for all s_i,k∈ V^*_g.

	If there are many good vertices, we can conclude that a lot of the important edges are crossing.
		
		
		One has |V^*_| ≥49/50|V^*|.
	
	
		Since the number of crossing edges is |E ∖𝒰| ≤ϵ· 1.3 dn, one has
		
    |{s_i,k∈ V^* :  |(E ∖𝒰) ∩S_i2| ≤200ϵdm }| ≥(1-1/100)n/m= (1-1/100)|V^*|   .

		Combining <ref> and the above bound, we know V^*_ to be large:
		
    |V^*_g| ≥(1-12ϵ/ψ-1/100) · |V^*| ≥(1-1/50) · |V^*|   ,

		where we use the assumption that ϵ≤ 10^-5·ψ·d/m.
	
By <ref> and the bound in (<ref>), we can conclude the proof:
	
    |E^*  ∖𝒰| ≥∑_s_i,k∈ V^*_g |{{s,t}∈ E^* :   s = s_i,k}|   ≥(9/10 - 700ϵm/21/2d)2d · |V^*_g|   ,

	and by <ref> we get
	
    |E^*  ∖𝒰|  ≥(9/10 - 700ϵm/21/2d)2d ·49/50·n/m≥4/5· |E^*|    ,

	where we used ϵ≤ 10^-5ψd/m in the last inequality.




 §.§ Reduction to a communication problem


We introduce the two-party one-way communication problem , defined as follows.

	
	Let ξ >0  be a real parameter. In the communication problem _ξ,
	Alice's input is a graph G'=(S,E'), and Bob's output is a set of pairs of vertices F ⊆ S2 such that
	
		
  *  |F| ≤ 6 ξ· |E'|, and
		
  *  at least a 1/10 fraction of the pairs in F are edges of G', i.e. |F ∩ E'| ≥ 1/10· |E'|.
	

We give a reduction from _ϵ m to (ϵ, ϕ,2)-RED, in the setting where Alice's input G' is an n/2-vertex graph drawn from 𝒢'. We recall that 𝒢'=𝒢'_n,d,m = (m/2, 4d/m)^⊗ n/m is the distribution over n/2-vertex graphs G'=(S,E') consisting of the disjoint union of n/m disjoint Erdős-Rényi graphs on m/2 vertices (see <ref>). We then begin by verifying that, with high probability, an input G' ∼𝒢' is a collection of n/m nearly regular expanders.

 
	Let G' ∼𝒢'. If m≥ 500 and d ≥ 600 log n then,  with probability at least 1-1/n, for every i ∈ [n/m] one has that the subgraph G'[S_i] is a (1 ± 1/10)2d-regular 1/3-expander



	The statement follows from the following fact about Erdős-Rényi graphs, whose proof is deferred to <ref>.
	facterdos
		
		Let N ≥ 10 be an integer and p ∈ [0,1]. Then, letting d̅ = p(N-1) one has
		
    _H=(U,F) ∼(N,p)[(Φ_H < 1/3) or (∃ u ∈ U  s.t. |_H(u)-d̅|>1/11d̅)] ≤ 4N ·exp(-pN/600)   .

	
	
	In our case, each subgraph G'[S_i] is drawn from (m/2, 4d/m), and note that m/2 ≥ 250 ≥ 10, thus meeting the precondition of <ref>. Hence, for any i ∈ [n/m] <ref> gives
	
    [(Φ_G'[S_i] < 1/3)  or (∃ u ∈ S_i  s.t. |_G'[S_i](u)-2d|>1/102d)] ≤ 2m ·exp(-d/300)   ,

	where we used m ≥ 500 to express the degree bounds in terms of 2d instead of d̅.
	Therefore, taking a union bound gives
	
    [∀  i ∈ [n/m]  , ( Φ_G'[S_i]≥1/3 and ∀ u ∈ S_i  , |_G'[S_i](u)-2d|≤1/10 2d)] ≥1- 1/n  ,

	where we used d ≥ 600 log n ≥ 600 ln n.

By virtue of the above, most of Alice's inputs  can be embedded into a sample from 𝒢 where a large fraction of important edges are inter-cluster edges of any ED, as per <ref>. This will allow Alice and Bob to solve _ϵ m.


	
	Let 𝒜 be a deterministic streaming algorithm for computing a 2-level (ϵ,ϕ)-RED of a graph given in a stream of edges. For a graph G'=(S,E') ∼𝒢', we reduce _ϵ m to computing a 2-level (ϵ,ϕ)-RED as follows. Alice instantiates 𝒜 for the vertex set V, and feeds her edges E' and the fixed edges of G[T] to 𝒜. Then, she sends the memory state Π of 𝒜 to Bob. Then, Bob instantiates m/2 copies of 𝒜, call them 𝒜_1, …, 𝒜_m/2, and sets the memory state of them to Π. Next, for each k ∈ [m/2] let G_k = (V,E_k) be the graph defined by (G',k), and note that Bob knows the edges between S and T (see <ref>). Then, Bob feeds the edges E_k(S,T) to 𝒜_k. For each k ∈ [m/2], let 𝒰^k_1,𝒰^k_2 be the output of 𝒜_k. Bob finally constructs his output set F as follows: for each k ∈ [m/2], if the number of non-isolated vertices in 𝒰^k_2 is at most 3 ϵ d n, add the pair {s,s_i,k} to F for every i ∈ [n/m] and every s ∈ S_i that is not an isolated vertex in 𝒰^k_2. More formally, for a partition 𝒰 of V, let V ∖𝒰 = {u ∈ V:  {u}∉𝒰} be the set of non-isolated vertices in 𝒰. With this notation, Bob outputs
	
    F = ⋃_k∈ [m/2] : |V ∖𝒰_2^k| ≤ 3ϵ dn F_k   ,     with  F_k={{s,s_i,k} : i ∈ [n/m],  s ∈ S_i ∩ (V ∖𝒰_2^k) }  .
 

We remark that if Bob learns the important edges E^*_k for all k ∈ [m/2], then he learns all of E'.

	
	In the setting of <ref>, we have E' = ⋃_k ∈ [m/2] E^*_k and |E'| = 1/2∑_k ∈ [m/2] |E^*_k|.

As suggested by <ref>, it is enough to ensure that each instance 𝒜_k recovers the important edges of G_k in order for Bob to learn the edges of G'. We in particular restrict ourselves to indices k for which the algorithm 𝒜_k, the graph G_k, and the RED 𝒰_1^k,𝒰_2^k are well behaved, as defined below.


	
	In the setting of <ref>, for every k ∈ [m/2] let 𝒫_k be the property that
	
    𝒰_1^k,𝒰_2^k is an (ϵ,ϕ,2)-RED of  G_k  ,  | E^*_k ∖𝒰^k_1| ≥4/5·|E^*_k|   ,    |E_k^*| ≥9/5dn/m ,    |E_k|≤ 1.3 dn  .


We first show a preliminary result: if there are many k ∈ [m/2] that satisfy 𝒫_k, then Bob's output set contains many edges of G'.

	
	In the setting of <ref>, if ϵ∈ (0,1) satisfies ϵ≤1/30√(m), then
	
    |E' ∩ F|  ≥49/100dn/m  |{k∈ [m/2] : 𝒫_k}|   .



Recall from <ref> that F is made by the union of F_k over 	k ∈ [m/2]. We then first give a guarantee on the F_k's individually.
	
		
		Let k ∈ [m/2] such that 𝒫_k holds. Then
		
			
  *  |V ∖𝒰_2^k| ≤ 3 ϵ dn, and
			
  *  |F_k  ∩ (E^*_k ∖𝒰^k_1) | ≥dn/m-ϵ^2 · 1.3 dn.
		
	
	
		Since 𝒫_k is verified, 𝒰_1^k,𝒰_2^k is an (ϵ,ϕ,2)-RED of  G_k (see <ref>). By definition of RED (see <ref>), we know |E_k ∖𝒰^k_1| ≤ϵ |E_k|. Moreover, one can note that the number of non-isolated vertices in 𝒰_2^k is at most twice the number of edges in E_k ∖𝒰_1^k. This is because every non isolated vertex must have at least one edge incident on it in E_k ∖𝒰_1^k (which is the input to the second level ED), as otherwise property (<ref>) of <ref> would be violated for any ϕ > 0. Thus,
		
    |V ∖𝒰_2^k| ≤ 2|E_k ∖𝒰^k_1| ≤ 2ϵ |E_k|  ≤ 3 ϵ dn  ,

		where the last inequality follows because |E_k|≤ 1.3 dn (see <ref>).
	
	
		From part (<ref>), together with the assumptions that 𝒰_1^k,𝒰_2^k is an (ϵ,ϕ,2)-RED of G_k and |E_k|≤ 1.3 dn (see <ref>), we have
		
    |V ∖𝒰^k_2 |   ≤ 3ϵ dn  and  |E_k ∖𝒰_2^k | = |(E_k ∖𝒰_1^k ) ∖𝒰_2^k| ≤ϵ|E_k ∖𝒰_1^k | ≤ϵ^2 · |E_k| ≤ϵ^2 1.3 dn  .

		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 <ref>). To do this, we make the following observation for any edge {s,s'}∈ E^*_k ∖𝒰^k_1: if none of s,s' is an isolated vertex in 𝒰_2^k, i.e. {s}∉𝒰_2^k and {s'}∉𝒰_2^k, then {s,s'}∈ F_k; otherwise, if {s}∈𝒰_2^k or {s'}∈𝒰_2^k, then {s,s'}∈(E_k ∖𝒰_1^k) ∖𝒰_2^k (and this is because  𝒰_2^k is an ED of the graph (V,E_k ∖𝒰_1^k) and {s,s'}∈ E_k ∖𝒰_1^k by assumption). Therefore,
		
    |F_k ∩ (E^*_k ∖𝒰^k_1)| ≥ |E^*_k ∖𝒰^k_1| - |(E_k ∖𝒰_1^k) ∖𝒰_2^k|   .

		To conclude the claim, we use again the property 𝒫_k: since 𝒰_1^k,𝒰_2^k is an (ϵ,ϕ,2)-RED of  G_k, we have
		
    |(E_k ∖𝒰_1^k) ∖𝒰_2^k | ≤ϵ |E_k ∖𝒰_1^k| ≤ϵ^2 · |E_k|   .

		Using again 𝒫_k, we know | E^*_k ∖𝒰^k_1| ≥4/5· |E^*_k|,  |E_k^*| ≥9/5dn/m,  and |E_k| ≤  1.3 dn, so from (<ref>) we conclude
		
    |F_k ∩ (E^*_k ∖𝒰^k_1)| ≥ |E^*_k ∖𝒰^k_1| - |(E_k ∖𝒰_1^k) ∖𝒰_2^k| ≥4/5· |E^*_k|- ϵ^2 1.3 dn ≥dn/m- ϵ^2 1.3 dn  .

	
	
	From the definition of Bob's output F (see <ref>) and by <ref>, one has
	
    |E' ∩ F|  = | (⋃_k ∈ [m/2] E_k^*) ∩(⋃_k ∈ [m/2] : |V ∖𝒰_2^k| ≤ 3ϵ dn F_k ) |
    		   ≥| ⋃_k∈ [m/2] : |V ∖𝒰_2^k| ≤ 3ϵ dn( E_k^* ∩  F_k ) | 
    by <ref>     ≥1/2∑_k∈ [m/2] : |V ∖𝒰_2^k| ≤ 3ϵ dn| E_k^* ∩  F_k |   ,

	and we finish using <ref>:
	
    |E' ∩ F|     ≥1/2∑_k∈ [m/2] : |V ∖𝒰_2^k| ≤ 3ϵ dn| E_k^* ∩  F_k |  
    by part (<ref>) of <ref>     ≥1/2∑_k∈ [m/2] : 𝒫_k   holds| E_k^* ∩  F_k |   ,

	and then
		
    |E' ∩ F|  ≥1/2∑_k∈ [m/2] : 𝒫_k   holds| E_k^* ∩  F_k |  ≥1/2∑_k∈ [m/2] : 𝒫_k  holds| (E^*_k ∖𝒰^k_1) ∩ F_k|   ,

	so by part (<ref>) of <ref> we have
	
    |E' ∩ F|  ≥1/2∑_k∈ [m/2] : 𝒫_k   holds(dn/m -ϵ^2 · 1.3 dn)   ≥49/100dn/m  |{k∈ [m/2] : 𝒫_k}|   ,

	where we used ϵ≤1/30√(m) in the last inequality.

Finally, we prove that an efficient RED algorithm gives an efficient  protocol, using the lemma we just showed.
 
	Let ϵ,ϕ∈ (0,1) such that ϵ≤min{ 10^-5ψd/m, 1/30√(m)} and ϕ≥ 11/m. If n ≥ 100 m, m≥ 500, d ≥ 600 log n, and there is a deterministic L-bit space streaming algorithm 𝒜 that computes an (ϵ,ϕ,2)-RED with probability at least 9/10 over inputs G  ∼𝒢, then there is a deterministic protocol that solves _ϵ m with probability at least 3/5 over inputs G' ∼𝒢' with communication complexity at most L.


	The protocol is given by <ref>.  We observe that the communication complexity bound immediately follows, since 𝒜 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 <ref> provided that some conditions hold, and then verify that such conditions occur with constant probability.
	
	[Property (<ref>) of <ref>]
		
		If |{k ∈ [m/2]:  𝒫_k}| ≥m/3, then |F| ≤ 6 ·ϵ m |E'|.
	

	[Property (<ref>) of <ref>]
		
		If |{k ∈ [m/2]:  𝒫_k}| ≥m/3, then |F ∩ E'| ≥ 1/10 · |E'|.
	
	
	
		
		One has _G' ∼𝒢'[|{k ∈ [m/2]:  𝒫_k}| ≥m/3] ≥3/5.
	
	By <ref> and <ref>, the protocol given by <ref> succeeds provided that the input G' satisfies |{k ∈ [m/2]:  𝒫_k}| ≥m/3. By <ref>, the latter condition is verified with probability at least 3/5. The lemma statement is then proven, modulo showing <ref>, <ref>, and <ref>, which we do next.
	
		
		As per <ref>, F is the union of F_k={{s,s_i,k} : i ∈ [n/m],  s ∈ S_i ∩ (V ∖𝒰_2^k) } over k such that |V ∖𝒰_2^k| ≤ 3ϵ dn. Note that |{{s,s_i,k} : i ∈ [n/m],  s ∈ S_i ∩ (V ∖𝒰_2^k) }| is in fact upper-bounded by |V ∖𝒰_2^k|. One then gets that |F| ≤ 3ϵ dn m/2. In order to relate this bound to |E'|, we use our assumption: for at least m/3 values of k ∈ [m/2], |E^*_k| ≥ 9/5 · dn/m. By <ref>, this means |E'| ≥ 1/2 · m/3 · (9/5 · dn/m) = 3/10 · dn, so one concludes |F| ≤ 6 ϵ |E'| m.
	
	
		
		We can use <ref>, since our bound on ϵ ensures the precondition of the lemma. We then have |E' ∩ F|  ≥49/100dn/m  |{k∈ [m/2] : 𝒫_k}|.  Now, we conclude the claim by virtue of our assumption:
		
    |E' ∩ F| ≥49/100dn/m  |{k∈ [m/2] : 𝒫_k}|  ≥m/349/100dn/m≥1/10 |E'|   ,

		where in the last inequality we used that our assumption further implies |E'| ≤ |E_k| ≤ 1.3dn for some k ∈ [m/2].
	
	
	
	
		We recall that for G' ∼𝒢' and K ∼([m/2]) one has (G',K) ∼𝒢 (see <ref>). For k ∈ [m/2], we then interchangeably write 𝒜(G) and 𝒜(G',k) to refer to an execution of 𝒜 on the graph G associated with (G',k). Our assumption on 𝒜 rewrites as
		
    _G' ∼𝒢',   K ∼([m/2])[𝒜(G',K) fails]  = _(G',K) ∼𝒢[𝒜(G',K) fails] ≤1/10  .

		Now recall <ref>: for each k ∈ [m/2], the result of 𝒜_k computed by Bob is exactly 𝒜(G',k), where G' denotes Alice's input. Therefore, using that G' and K are independent and that K is drawn uniformly, we get
		
    _G' ∼𝒢'[ | {k ∈ [m/2] : 𝒜_k fails }| ] =_G' ∼𝒢'[ | {k ∈ [m/2] : 𝒜(G',k) fails }| ] ≤1/10·m/2  .

		Hence, if we sample G' ∼𝒢', only a small fraction of the values of k will make (G',k) a failing instance. Specifically, for any α∈ [1/10, 1], Markov's inequality gives
		
    _G' ∼𝒢'[| {k ∈ [m/2] : 𝒜(G',k) fails }| > 1/α1/10·m/2] ≤α  .

		In other words, at least a 1-α fraction of the probability measure of 𝒢' yields a graph G' such that (G',k) is a succeeding instance for 𝒜 with at least a 1-0.1/α fraction of the possible values for k ∈ [m/2]. By <ref> (which applies since we assume m≥ 500, d ≥ 600 log n), we also have that a 1-1/n fraction of the measure of 𝒢' yields a graph G' where each component is a (1 ± 1/10)2d-regular 1/3-expander. This in particular implies that at least a 1-α-1/n fraction of the probability measure of 𝒢' yields a graph G' such that:
		
			
  * for every k ∈ [m/2], the graph G_k=(V,E_k) given by (G',k) has |E_k| ≤ 1.3 dn, by near-regularity and <ref>;
			
  * for every k ∈ [m/2], the graph G_k=(V,E_k) given by (G',k) has |E^*_k| ≥9/5dn/m, by near regularity and <ref>;
			
  * with at least a 1-0.1/α fraction of the possible values for k ∈ [m/2] we have the following: 𝒜_k outputs an (ϵ,ϕ,2)-RED 𝒰^k_1,𝒰^k_2 of the graph G=(V,E_k) given by (G',k). Moreover, by <ref> (which applies, since our assumptions on n, m, ϵ, ϕ meet its preconditions) one has that 𝒰_1^k verifies the property
			
    | E^*_k ∖𝒰^k_1| ≥4/5·|E^*_k|    .

		
		We have then obtained that at least a 1-α-1/n fraction of the probability measure of 𝒢' yields a graph G' such that 𝒫_k holds for at least a 1-0.1/α fraction of the possible values for k ∈ [m/2]. Setting α = 3/10 gives the claim.
	




 §.§ Hardness of the communication problem


We show that _ξ requires linear communication in the number of edges when G' ∼𝒢' and ξ = ϵ m. Intuitively, this is because Bob is only allowed to output an ≈ϵ m factor more pairs than |E'|, and for an appropriate parameter regime ϵ m | E'| < 1/1000m/22n/m (where m/22n/m is the total number of vertex pairs in a graph consisting of n/m disjoint subgraphs on m/2 vertices).

 
	Let ϵ∈ (0,1) such that ϵ≤10^-33/d. If m≥ 500 and d ≥ 600 log n, then any deterministic protocol that solves _ϵ m with probability at least 3/5 over inputs G' ∼𝒢' requires Ω(dn) bits of communication.


	Let us fix hereafter 𝒬 to be a deterministic protocol that solves _ϵ m with probability at least 3/5 over inputs G' ∼𝒢'. We define ^(1)⊆(𝒢')  to be the subset of input graphs G'=(S,E') in the support of 𝒢' such that 𝒬 outputs correctly on input G'. We also partition (𝒢') based on the number of edges, so for every integer t we define _t  ⊆(𝒢') to be the subset of graphs G'=(S,E') ∈(𝒢') with |E'| = t. We also let for convenience ^(1)_t =^(1)∩_t be the subset of correct graphs with t edges. For any G'=(S,E') ∈(𝒢'), we denote by M_G'∈{0,1}^* the message sent by Alice on input G' using the protocol 𝒬.
		
	
			
			If t is an integer such that t ∈ [9/10 · dn/2 ,   11/10 · dn/2] and  |ℐ^(1)_t| ≥1/2· |ℐ_t|, then
			
    (M_G' |   G' ∈_t^(1))  ≥dn/3  .

	
	
		For any G' ∈ℐ^(1)_t, following the reception of  M_G', Bob deterministically outputs at most  6·(
		m)·|E'| = 6 ·ϵ m t pairs of vertices F ⊆ S2, such that at least 1/10 · |E'| = t/10 of them are actually edges of G'. Thus, for any t and any message M ∈{0,1}^≤ nm (where we restrained messages to be at most nm-bit long without loss of generality), the number of G'∈ℐ^(1)_t such that M_G'=M is at most
		
    | {G' ∈ℐ^(1)_t:   M_G' = M}|    ≤∑_j=0.1 t^t6 ·ϵ m tj·n/mm/22t-j
       ≤∑_j=0.1 t ^t(· 6 ·ϵ m t/j)^j ·(· nm/8/t-j)^t-j
       = ^t∑_j=0.1t^t(60 ·ϵ m t/ t)^j ·( nm/8/t)^t-j·(t/t-j)^t-j  .

		We employ the following fact to bound the above, whose proof is deferred to <ref>.
		factmath
			For any 0 < x ≤ y, (y/x)^x ≤^y/.
		
		We apply <ref> to the factor (t/t-j)^(t-j) with x = t-j and y=t, and hence we get
		
    | {G' ∈ℐ^(1)_t:   M_G' = M}|    ≤^(1+1/)t∑_j=0.1t^t(60 ϵ m )^j ·(nm/8/t)^t-j
        =  ^(1+1/)t(nm/8t)^t∑_j=0.1t^t(60·ϵ 8t/n)^j
       ≤^(1+1/)t(nm/8t)^t( 500·ϵ t/n)^ t/10 t   ,

		where in the last inequality we used the upper bounds on ϵ and t. On the other hand, by virtue of our assumption that |ℐ_t^(1)| ≥1/2· |ℐ_t|, one has
		
    |ℐ^(1)_t|    ≥1/2|{G' = (S,E') ∈(𝒢'):   |E'|  = t }|  
       ≥1/2|{G' = (S,E') ∈(𝒢'):  ∀  i ∈ [n/m] , |E' ∩S_i2|  = t/n/m}| 
        = 1/2m/22t/n/m^n/m≥1/2m^2/16t/n/m^n/m≥1/2(m^2/16/t/n/m)^t/n/m· n/m =  1/2( nm/16t)^t  .

		Next, we rewrite
		
    (M_G' |    G' ∈_t^(1))      ≥(G' ; M_G' |   G' ∈_t^(1)) 
         =  (G'  |   G' ∈_t^(1))  -  (G'   |   M_G',  G' ∈_t^(1))   .

		Now, observing that all the graphs with same number of edges have the same probability of being sampled, one can employ the upper and lower bounds derived above:
		
    (G'  |   G' ∈_t^(1))  -  (G'   |  M_G',   G' ∈_t^(1))
       ≥log(	|ℐ^(1)_t|) - log(max_M ∈{0,1}^≤ nm| {H ∈ℐ^(1)_t:   M_H = M_G'}|) 
    by (<ref>) and (<ref>)   ≥ t log(1/2nm/16t/^(1+1/)·nm/8t·(t)^1/t·( 500·ϵ t/n)^1/10)   .

		Then, we finish using 9/10 · dn/2 ≤ t ≤ 11/10 · dn/2 and ϵ≤10^-33/d:
		
    (M_G' |   G' ∈_t^(1))   ≥ t log( 1/120/( 500 ·ϵ 11 dn/20n)^1/10)  ≥ t log 6 ≥9/10dn/2≥dn/3  .

	
	
	
		
		One has
		
    _G'=(S,E') ∼𝒢'[  |E'| ∈[9/20dn ,  11/20dn]    and  |_|E'|^(1)|/|_|E'| |≥1/2] ≥1/10  .

	
	
		We begin by defining for convenience
		
    x  = _G'=(S,E') ∼𝒢'[  |_|E'|^(1)|/|_|E'| | < 1/2]    .

		Then, by <ref> (which applies by our assumption on m and d), one has
		 
    _G'=(S,E') ∼𝒢'[  |E'| ∈[9/20dn ,  11/20dn]    and  |_|E'|^(1)|/|_|E'| |≥1/2]  ≥ 1-1/n - x  .

		 We are left with the task of upper-bounding the probability x. Letting = {0, …, m/22n/m} be  the set of possible numbers of edges in G' ∼𝒢', we have
		 
    _G'=(S,E') ∼𝒢'[𝒬 outputs correctly on input  G']
        = _G'=(S,E') ∼𝒢'[G' ∈^(1)] 
        =∑_t ∈_G'=(S,E') ∼𝒢'[|E'|=t] _G'=(S,E') ∼𝒢'[G' ∈^(1)  |   |E'|=t] 
        = ∑_t ∈_G'=(S,E') ∼𝒢'[|E'|=t]  ·|_t^(1)|/|_t|  ,

		where the last equality holds because all the graphs with t  edges have the same probability of being sampled. Hence, splitting the sum one has
		
    _G'=(S,E') ∼𝒢'[𝒬 outputs correctly on input  G']
       ≤∑_t ∈ : 
     |_t^(1)| < 1/2|_t^(1)| _G'=(S,E') ∼𝒢'[|E'|=t] ·1/2 + ∑_t ∈ : 
     |_t^(1)| ≥1/2|_t^(1)| _G'=(S,E') ∼𝒢'[|E'|=t]· 1
        = _G'=(S,E') ∼𝒢'[  |_|E'|^(1)|/|_|E'| | < 1/2] ·1/2 + _G'=(S,E') ∼𝒢'[ |_|E'|^(1)|/|_|E'| |≥1/2] · 1
        = x ·1/2 + (1-x) · 1 = 1-x/2  .

		 If we suppose for the sake of a contradiction that x ≥ 449/500, then
		 
    _G'=(S,E') ∼𝒢'[𝒬 outputs correctly on input  G'] ≤551/1000 < 3/5  ,

		 which contradicts our assumption on 𝒬. Therefore, we plug x < 449/500 into (<ref>) together with the assumption n > m ≥ 500, thus  getting the claim.
	
	Let now 𝒞 be the event that |E'| ∈ [9/10 · dn/2 ,   11/10 · dn/2] and  |ℐ^(1)_|E'|| ≥1/2· |ℐ_|E'||.
	The size of Alice's message on input G'=(S,E') ∼𝒢' is lower bounded by
	
    (M_G')
    			   ≥(M_G' |  _𝒞, |E'|)  
       ≥[  𝒞]    ∑_t ∈[9/20dn ,  11/20dn] ∩ℕ:
    |ℐ^(1)_t| ≥1/2·|ℐ_t| [|E'|=t  |  𝒞] ·(M_G' |  𝒞, |E'|=t)  ,

		and because conditioning does not increase entropy we rewrite
		
    (M_G')    ≥[  𝒞]     ∑_9/20dn ≤ t ≤11/20dn :
     |ℐ^(1)_t| ≥1/2· |ℐ_t| [|E'|=t  |  𝒞] ·(M_G' |  _G' ∈^(1) ,𝒞, |E'|=t)  
       ≥[  𝒞]     ∑_9/20dn ≤ t ≤11/20dn:
     |ℐ^(1)_t| ≥1/2· |ℐ_t| [|E'|=t  |  𝒞] ·[G' ∈^(1) |    |E'|=t] ·(M_G' |   G' ∈_t^(1))   .

		Finally, we use <ref> and  <ref> and get
		
    (M_G')    ≥[  𝒞]     ∑_9/20dn ≤ t ≤11/20dn:
     |ℐ^(1)_t| ≥1/2· |ℐ_t| [|E'|=t  |  𝒞] ·1/2·dn/3
        =  dn/6_G'=(S,E') ∼𝒢'[  |E'| ∈[9/20dn ,  11/20dn]    and  |_|E'|^(1)|/|_|E'| |≥1/2] 
       ≥dn/60  .





 §.§ Proving  the lower bound


Finally, we set d and m depending on ϵ,ϕ,n so as to combine <ref> and <ref> and conclude our streaming lower bound.
*


	We recall that for any ϵ = 1-Ω(1), computing an (ϵ,ϕ)-ED with constant probability requires Ω(n log n) bits for all ϕ∈ (0,ϵ]. To see why, consider an input graph that is a matching of size n/10, and notice that an ED is a 1-ϵ fraction the edges. Therefore, we now consider the case ϵ =  O(1/log n) and prove an Ω(n/ϵ) lower bound.
	
	Let ϵ,ϕ∈ (0,1) be any ED parameters and define c = ψ· 10^-40. Note that c is a constant since ψ = Ω(1) is the fixed sparsity from <ref>. In order to apply  <ref> and <ref>, we use distributions  𝒢 and 𝒢' from <ref> with d and m set as follows:
	
    d = ϵ/2c^3 ϕ + c/2 ϵ  and   m = 11/c ϕ  .

	We verify that these values meet the preconditions set by <ref> and <ref>, i.e. we show that d and m satisfy
	
    ϵ≤min{10^-5ψd/m ,  1/30√(m),  10^-33/d}  ,   ϕ≥11/m  ,    500 ≤ m ≤n/100  ,    600log n ≤ d < m   ,

	for all ϵ,ϕ such that
	
    ϵ≤c^2/log n  ,   ϕ≥1/c^2n  ,   and  ϵ^2/c^4≤ϕ≤ϵ  .

	Substituting d and m as defined in (<ref>) into (<ref>) we get
	
    10^-5ψd/m = 10^-5ψ(ϵ/2c^3 ϕ + c/2 ϵ) ·cϕ/11≥ 10^-5ψϵ/2c^2 11  = 10^75ϵ/2ψ 11 ≥ϵ  ,


    1/30√(m) = √(c)√(ϕ)/30√(11)≥√(c)ϵ/30√(11)c^2≥ϵ  ,


    10^-33/d = 10^-334c^3ϵϕ/2ϵ^2 + 2c^4ϕ=10^-334c^3ϵ/2ϵ^2/ϕ + 2c^4≥ 10^-334c^3ϵ/2c^4 + 2c^4 = 10^-33ϵ/c≥ϵ  ,


    11/m = cϕ≤ϕ  ,


    m = 11/c ϕ≥11/c ϵ≥log n ≥ 500   ,


    m = 11/c ϕ≤ 11 c n ≤n/100  ,


    d = ϵ/2c^3 ϕ + c/2 ϵ≥c/2 ϵ≥log n/2c≥ 600 log n   ,


    d = ϵ/2c^3 ϕ + c/2 ϵ≤ϵ/2c^3 ϕ + c/2 ϕ≤1/2c log n ϕ + c/2 ϕ  < 11/c ϕ = m   ,

so all the conditions (<ref>) are verified.
	
	With any ϵ,ϕ as in (<ref>) and for our choice of d,m as in (<ref>), <ref> gives that if there is an L-bit space deterministic streaming algorithm 𝒜 that outputs an (ϵ,ϕ,2)-RED of G ∼𝒢_n,d,m with probability at least 9/10, then there is a deterministic protocol 𝒬 that solves _ϵ m with probability at least 3/5 over inputs G' ∼𝒢' with communication complexity L. On the other hand, by <ref> we know that, in the parameter regime of (<ref>), the complexity of 𝒬 over 𝒢' is at least Ω(dn). Hence,
	
    L = Ω(dn)  = Ω((ϵ/ϕ+1/ϵ) · n ) = Ω(n/ϵ)  .

 	By Yao's minimax principle, the theorem statement is proved with C = c^-4.
	




tocsectionReferences
alpha








§ TECHNICAL FACTS



 §.§ Fast balanced sparse cut algorithm


In this section, we prove the following fast BSCA, used for our polynomial time BLD construction.

*


Hereafter we use n and m to denote the number of vertices and edges respectively. An algorithm was recently given that, for n-vertex m-edge input graphs with polynomially bounded edge weights, produces a (O(ϕlog^3 n), ϕ)-ED[In this case, the definition of ED uses the weight of edges across cuts, and weighted volumes, including self-loops.] with high probability in (m) time, for any ϕ∈ (0,1) <cit.>. One can then use this ED algorithm to efficiently compute a an approximate balanced ψ-sparse cut for all ψ∈ (0,1): as it was observed in <cit.>, given access to a graph and its (O(ψlog^3 n), ψ)-ED, one can easily obtain a (ψ,c' ·log^3 n, C',0)-BSCW for some constants c',C'≥ 1. This gives a (c' ·log^3 n, C')-BSCA that runs in (m) time for all input sparsity parameters ψ∈ (0,1). However, these results were not stated for graphs with arbitrary self-loops, which is what we need. Hence, we give a simple reduction from the self-loop case to the self-loop free one, without increasing the size of the graph by more than constant factors, so as to fit our setting.

Let G=(V,E,w) be a weighted undirected graph with one weighted self-loop per vertex, where w: E ∪ V →ℝ_≥ 0 and E ⊆V2. The idea is to construct a graph with two copies of every vertex, where the surplus vertices are solely connected to their corresponding vertex with weight equal to half the weight of the self-loop. If a vertex has no self-loops then we make only one copy for it. Formally, let A={u ∈ V:w(u) > 0} be the set of vertices with self-loops. Then let B be a copy of A representing the self-loops of vertices in A, and let s: A → B be a bijection mapping u ∈ A to its corresponding self-loop vertex s(u) ∈ B. We define the self-loop free graph to be Ĝ=(V̂,Ê,ŵ), where V̂ = V ∪ s(A), Ê=E ∪ (∪_u ∈ A{{u, s(u)}}), and ŵ(e)=w(e) for every e ∈ E and ŵ({u, s(u)})=1/2w(u) for all u ∈ A. This is illustrated in <Ref>. We highlight that Ĝ has the same number of vertices and edges as G, up to constants.



We run a BSCA for self-loop free graphs on Ĝ, and if it asserts Ĝ to be an expander we conclude the same for G, whereas if it returns a cut then we tweak it to get a solution for G. This is summarised in Algorithm <ref>. The following claim gives the correctness of the reduction. The idea is that the subgraphs given by {u,s(u)} for u ∈ A are expanders, so there is no good reason for a sparse cut to cross them. Hence, u and s(u) should be on the same side of the sparse cuts.





	
	Let  be an (α,λ)-BSCA. Then SelfLoopBalSparseCut is a (2α,4λ)-BSCA, provided that the input sparsity parameter ϕ∈ (0,1) satisfies ϕ≤1/10α.


	For any cut ∅≠ X ⊊ V, let us define for convenience ∂_G X=w(X,V ∖ X) to be the total weight of the edges crossing the cut X in G, and for any cut ∅≠ R ⊊V̂ define ∂_Ĝ R=ŵ(R,V̂∖ R) to be the total weight of edges crossing R in Ĝ. A preliminary observation is that for any cut ∅≠ X ⊊ V we have that _Ĝ(X ∪ s(X ∩ A))=_G(X), ∂_Ĝ (X ∪ s(X ∩ A)) = ∂_G X, and consequently Φ_Ĝ(X ∪ s(X ∩ A)) = Φ_G(X). By definition of , we know that ω̂ is a (ϕ, α,λ,0)-BSCW of Ĝ, i.e.
	
		
  *  if ω̂=, then Ĝ is a ϕ-expander;
		
  * if ω̂=(R,ν), then:
		
			
  *  Φ_Ĝ(R) < α·ϕ,
			
  *  _Ĝ(R) ≤_Ĝ(V̂∖ R),
			
  *  for every other cut ∅≠ T ⊊V̂ with Φ_Ĝ(T) < ϕ and _Ĝ(T) ≤_Ĝ(V̂∖ T) one has _Ĝ(T) ≤λ_Ĝ(R):
			
  *  ν =_Ĝ(R).
		
	
	Our goal is to translate these properties to G by showing that ω, as constructed in SelfLoopBalSparseCut, is a  (ϕ,2α,4λ,0)-BSCW of G, i.e.
	
		
  *  if ω=, then G is a ϕ-expander;
		
  * if ω=(X^*,ν), then:
		
			
  *  Φ_G(X^*) < α·ϕ,
			
  *  _G(X^*) ≤_G(V∖ X^*),
			
  *  for every other cut ∅≠ T ⊊V with Φ_G(T) < ϕ and _G(T) ≤_G(V∖ T) one has _G(T) ≤λ_G(X^*):
			
  *  ν =_G(X^*).
		
	
	

  
Correctness of the case ω̂=. This  means that for every cut ∅≠ R ⊊V̂ one has Φ_Ĝ(R) ≥ϕ. This in particular holds for cuts of the form X ∪ s(X ∩ A) with ∅≠ X ⊊ V. As we observed that Φ_Ĝ(X ∪ s(X ∩ A)) = Φ_G(X), we conclude that G is also a ϕ-expander.
	
	

  
Correctness of the case ω̂=(R,ν).
	The idea is that adding missing self-loops and removing dangling self-loops makes R a solution for G. This is illustrated in <Ref>.
	
	

	We know from (<ref>) that
	
    ∂_Ĝ R/_Ĝ (R) < αϕ  .

	Consider the cut Q=R ∪ s(R ∩ A), i.e. a version of R where we have added the self-loops of all the vertices in R that have one. Then Q ⊊V̂, as otherwise V ⊆ R, which would imply that R contains more than half the volume of _Ĝ(V̂), contradicting (<ref>). Next, we remark that the volume of Q cannot decrease compared to R, since we added vertices, i.e.
	
    _Ĝ(Q) = _Ĝ(R) + ∂_Ĝ(s(R ∩ A) ∖ (R ∩ B)) ≥_Ĝ(R)  .

	At the same time, we do not increase the number of crossing edges since we move the self-loop edges inside the cut, so
	
    ∂_Ĝ Q/_Ĝ(Q) = ∂_Ĝ R - ∂_Ĝ(s(R ∩ A) ∖ (R ∩ B))/_Ĝ(R) + ∂_Ĝ(s(R ∩ A) ∖ (R ∩ B))≤∂_Ĝ R/_Ĝ (R)  .

	Thus, we have added self-loops to R without increasing its sparsity nor decreasing its volume. Now we remove the dangling self-loops from Q, i.e. we remove the set D=(Q ∩ B) ∖ s(Q ∩ A), and consider the cut P=Q ∖ D. We remark that P ≠∅, as otherwise R is solely made of vertices from s(A), which contradicts Φ_H(R) < αϕ≤ 1/10 < 1. Since we removed an equal amount of mass from both the crossing edges and the volume, we get
	
    ∂_Ĝ P/_Ĝ(P)≤min{∂_Ĝ P/_Ĝ(P), 1}≤∂_Ĝ P + ∂_Ĝ D/_Ĝ(P)+∂_Ĝ D  = ∂_Ĝ Q/_Ĝ (Q)  .

	Thus, removing the dangling self-loops does not increase sparsity. However we may have decreased the volume, which threatens the balancedness property of the cut. We then bound the decrease: because we proved before ∂_Ĝ Q/_Ĝ (Q) < αϕ, we know
	
    ∂_Ĝ D < αϕ/1-αϕ_Ĝ(P)   ,

	so
	
    _Ĝ(Q) = _Ĝ(P) + ∂_Ĝ D < 2 _Ĝ(P)   .

	Now one can see that P is identical to (R ∩ V) ∪ s(R ∩ A), and X as defined in Algorithm <ref> equals R ∩ V. Hence ∂_G X = ∂_Ĝ P and _G(X)=_Ĝ(P). Therefore,
	
    ∂_G X/_G (X) < αϕ  .

	To handle the case where X is the larger volume side of the cut, <ref> takes X^* to be the side of (X,V∖ X) with smaller volume. We show that the volume of V∖ X is within a small constant factor of the volume of X. To do so, recall that Φ_Ĝ(R)<αϕ, so
	
    ∂_Ĝ Q + ∂_Ĝ(s(R ∩ A) ∖ (R ∩ B))/_Ĝ(Q) - ∂_Ĝ(s(R ∩ A) ∖ (R ∩ B)) < αϕ ,

	which implies
	
    ∂_Ĝ(s(R ∩ A) ∖ (R ∩ B)) < αϕ_Ĝ(Q)   .

	Hence, by property (<ref>) of R, we have
	
    _G(X) ≤_Ĝ(Q) < 1/1-αϕ_Ĝ(R) ≤1/2·1/1-αϕ_Ĝ(V̂) = 1/2·1/1-αϕ_G(V)   .

	Therefore, we have that X^* = {_G(X), _G(V∖ X)} satisfies
	
    (1-2αϕ)_G(X) ≤_G(X^*) ≤_G(V∖ X^*)   ,

	and
	
    _Ĝ(R) < 2/1-2αϕ_G(X^*)   ,

by (<ref>), (<ref>). We now conclude by verifying properties (<ref>), (<ref>), (<ref>), (<ref>).


	
  * Property (<ref>). From (<ref>) and (<ref>), we get Φ_G(X^*) < 	αϕ /(1-2αϕ) ≤ 2 αϕ.
	
  * Property (<ref>). This property follows by definition of X^* in <ref>.
	
  * Property (<ref>). Consider any cut ∅≠ T ⊊ V such that Φ_G(T) < ϕ and _G(T) ≤_G(V ∖ T). Then we know that
	
    Φ_G(T) = Φ_Ĝ(T ∪ s(T ∩ A)) < ϕ  ,

	and
	
    _Ĝ(T ∪ s(T ∩ A)) = _G(T) ≤_G(V ∖ T) = _Ĝ(V̂∖ (T ∪ s(T ∩ A))  ,

	as well as
	
    _G(T) = _Ĝ(T ∪ s(T ∩ A)) ≤λ·_Ĝ(R) < 2λ/1-2αϕ_G(X^*) ≤ 4λ_G(X^*)  ,

	by an application of (<ref>) to the cut T ∪ s(T ∩ A) and (<ref>).
	
  * Property (<ref>). Follows directly by definition of ω in <ref>.


We use <ref> with α=c' log^3 n and λ = C' (where c',C'≥ 1 are the constants one gets from the self-loop free BSCA of <cit.>). Then, we get a (c_log^3 n,C_)-BSCA where c_=2c' and C_ = 4C', provided that ϕ≤1/10α. Using ϕ = ψ and since we impose ψ≤1/10 c_log^3 n, we get ϕ≤1/10α. This concludes the proof of <ref>.




 §.§ Expansion and regularity of random graphs


*

	Let H=(U,F) be a sample from (N,p), so that |U|= N. Also let L=D-A be the Laplacian matrix of H, where D denotes its degree diagonal matrix and A denotes its adjacency matrix. We use the following matrix Bernstein concentration bound on L to lower bound its second eigenvalue, and then lower bound the expansion of H using Cheeger's inequality.
	
		 Let S_1,…, S_κ∈ℝ^N × N be independent symmetric random matrices such that [S_ι]=0 and S_ι≤λ for every ι∈ [κ], and let S = ∑_ι=1^κ S_ι. Then, for all θ≥ 0
		
    [S≥θ] ≤ 2N ·exp(-θ^2/2/∑_ι=1^κ[S_ι^2]+λθ/3)   .

	
	We start by rewriting L so that we can apply the above result. For each e={u,v}∈V2 let z_e ∼(p) be an independent Bernoulli random variable with bias p, and also let L_e be the Laplacian matrix of the graph (U,{e}), i.e. (L_e)_ab = 1 if a=b=u or a=b=v, (L_e)_ab = -1 if {a,b}=e, and (L_e)_ab=0 otherwise. Define S_e = z_e L_e - [z_eL_e] and S = ∑_e ∈V2 S_e. One can now note that
	
    [S_e]=0   and  S_e≤max{(1-p)L_e,-pL_e}≤ 2  for all e∈V2.

	Letting J be the all-ones N × N matrix we  also have
	
    S = ∑_e ∈V2 z_e L_e - ∑_e ∈V2[z_eL_e] = L- p · (N · I-J)  .

	Hence, <ref> with λ=2 gives
	
    [L-p · (N · I-J)≥θ] ≤ 2N ·exp(-θ^2/2/∑_e ∈V2[(z_e L_e - [z_eL_e])^2]+2θ/3)  .

	Now we observe that the first term in the denominator can be rewritten as
	
    ∑_e ∈V2[(z_e L_e - [z_eL_e])^2]    = ∑_e ∈V2 2L_e[(z_e-z_e· p+p^2)]
        = ∑_e ∈V2 2pL_e
        = 2p N · I-J
        = 2pN	  ,

	where the last equality holds because K  N · I-J is the Laplacian matrix of the complete graph on N vertices. If we now set θ = pN/10 in (<ref>), we get
	
    [L-p · K≥1/10pN] ≤  2N ·exp(-pN/600)   .

	Now, in order to use a Cheeger type of inequality, it is convenient to view H as a regular graph, so that its normalized Laplacian matrix is simply a scalar multiple of L. If we denote with (u) the degree of u ∈ U in H, we get by a Chernoff bound that
	
    [∃ u ∈ U, |(u) - p· (N-1)| > 1/14p · (N-1)] ≤ 2N ·exp(-p· (N-1)/600)  .

	From (<ref>) and (<ref>), we then have
	
    [(L-p K≥1/10pN) or (∃ u ∈ U : |_H(u)-d̅|>1/14d̅)] ≤ 4N ·exp(-pN/600)   .

	We conclude by showing that if the event in the above probability does not occur, then the event argument of the probability in the statement of <ref> does not occur either. To see this, let λ_2 be the second smallest eigenvalue of 1/d̅· L, and μ_2 be the second smallest eigenvalue of 1/(N-1) · K. Hence, L-p K < 1/10pN implies λ_2 ≥μ_2-1/9 by Weyl's inequality. Moreover, we know that μ_2 = N/(N-1), so λ_2 ≥ 9/10. Finally, let ∅≠ S ⊊ U be a cut with (S) ≤(U∖ S) such that Φ_H(S) = Φ_H. Assuming |_H(u)-d̅|≤1/14d̅ for all u ∈ U, we have that (S) ∈ [(1-1/14)d̅ |S|, (1+1/14)d̅ |S|]. Let y∈ℝ^U be defined as y_u = 1/|S| if u ∈ S and y_u=-1/|U ∖ S| otherwise. By Courant-Fischer we then have
	
    λ_2 = min_x∈ℝ^U∖{0}:
    ⟨x, ⟩= 0 1/d̅·x^⊤ Lx/x^⊤x≤1/d̅·y^⊤ Ly/y^⊤y  = SU/d̅|S|·|U|/|U∖ S|≤(1+1/14)Φ_H ·|U|/|U∖ S|  .

	Again assuming |_H(u)-d̅|≤1/14d̅ for all u ∈ U, one can check that (S) ≤(U∖ S) implies |U∖ S| ≥ 6/7 · |S|. Thus, (<ref>) gives
	
    λ_2 ≤(1+1/14)·(1+7/6) Φ_H ≤27/10Φ_H   ,

	so Φ_H ≥ 1/3.




 §.§ A useful inequality


*

	Write x=y·^ρ-1 for some ρ≤ 1. Then (y/x)^x ≤^y/ if and only if (1-ρ)e^ρ-1≤ 1/. Define f(ρ)=(1-ρ)^ρ. We prove the claim by showing that f(ρ) ≤ 1 for all ρ∈ (-∞, 1].
	
	We begin by noting that f is continuous over (-∞, 1]. Then, we take the derivative of f, and we get f'(ρ)=-ρ^ρ. We observe that f'(ρ) > 0 for ρ <0, and f'(ρ) > 0 for ρ >0. We further observe that f(0) = 1, f(1)=0, and lim_ρ→ -∞ f(ρ) = 0. Hence, f(ρ) is upper-bounded by 1 for all ρ∈ (-∞, 1].




