otherwise, we set $D^{\leq L}_{\ell}(u,v)=\infty$. The dual of (LP-1) can now
be written as follows:

(LP-2) $\displaystyle\min\quad\quad\sum\limits_{e\in E}\ell(e)$ s.t.
$\displaystyle\displaystyle\sum\limits_{u,v\in V}D^{\leq L}_{\ell}(u,v)\geq 1$
$\displaystyle\ell(e)\geq 0$ $\displaystyle\forall e\in E$

Even though Linear Programs (LP-1) and (LP-2) are of exponential size, they
can be solved efficiently using standard techniques (that is, edge-based flow
formulation). Let $f^{*}_{\mathsf{OPT}}$ be the value of the optimal solution
to (LP-1). We let $W^{*}=\frac{d}{nL}=\frac{\alpha}{64n\log n}$. If
$f^{*}_{\mathsf{OPT}}\geq W^{*}$, then we return the flow $f$ corresponding to
the optimal solution of (LP-1); it is immediate to verify that it satisfies
all requirements. Therefore, we assume from now on that
$f^{*}_{\mathsf{OPT}}<W^{*}$. We will provide an efficient algorithm to
compute a cut $(S,S^{\prime})$ in $G$ of sparsity less than $\alpha$.

Given a length function $\ell:E\mapsto{\mathbb{R}}_{\geq 0}$, we denote by
$W(\ell)=\sum_{e\in E}\ell(e)$ the total ‘weight’ of $\ell$. We need the
following definition.

######  Definition..

Given an integer $r$ and a length function $\ell(e)$ on edges $e\in E$, the
$r$-hop bounded diameter of $G$ is $\max_{u,v\in V}\left\\{D^{\leq
r}_{\ell}(u,v)\right\\}$.

Consider the optimal solution
$\ell_{\mathsf{OPT}}:E\rightarrow{\mathbb{R}}^{+}$ to (LP-2). Observe that, by
the strong duality, the value of the solution
$W(\ell_{\mathsf{OPT}})=f^{*}_{\mathsf{OPT}}$, and so
$W(\ell_{\mathsf{OPT}})<W^{*}$ holds.

We define a new solution $\ell$ to (LP-2) as follows: for each edge $e$, we
let $\ell(e)=\ell_{\mathsf{OPT}}(e)\cdot\frac{W^{*}}{W(\ell_{\mathsf{OPT}})}$.
Since $W^{*}>W(\ell_{\mathsf{OPT}})$, it immediate to verify that we obtain a
valid solution to (LP-2), of value $W(\ell)=W^{*}$. Moreover, the constraint
governing the sum of pairwise $L$-hop bounded distances is now satisfied with
strict inequality:

$\sum_{u,v}D^{\leq L}_{\ell}(u,v)>1.$ (B.1)

The lengths $\ell(e)$ on edges are fixed from now on, and we denote $D^{\leq
L}_{\ell}$ by $D^{\leq L}$ from now on. We will also use the distance function
$D^{\leq L/4}_{\ell}$, that we denote by $D^{\leq L/4}$ from now on.

We use the following lemma.

######  Lemma B.2.5 (Adaptation of Corollary 20 from [LR99]).

There is an efficient algorithm, that, given a graph $G=(V,E)$, a parameter
$0<\alpha<1$ and any edge length function $\ell:E\mapsto{\mathbb{R}}_{\geq 0}$
of total weight $W(\ell)=\sum_{e\in E}\ell(e)\leq\frac{\alpha}{64n\log n}$,
returns one of the following:

  * •

either a subset $T\subseteq V$ of at least
$\left\lceil\frac{2|V|}{3}\right\rceil$ vertices, such that, for
$r=\frac{|E|}{2n^{2}W(\ell)}$, the $r$-hop bounded diameter of $G[T]$ is at
most $\frac{1}{2n^{2}}$; or

  * •

a cut $(S,S^{\prime})$ in $G$ of sparsity less than $\alpha$.

We complete the proof of Lemma B.2.5 later, after we complete the proof of
Theorem B.2.3 using it. Recall that $W(\ell)=W^{*}=\frac{\alpha}{64n\log n}$.
We apply the algorithm from Lemma B.2.5 to graph $G$, with parameter $\alpha$
and distance function $\ell$.

If the algorithm returns a cut $(S,S^{\prime})$ of sparsity less than
$\alpha$, we terminate the algorithm and return this cut. Therefore, we assume
from now on that the algorithm from Lemma B.2.5 returns a subset $T\subseteq
V$ of at least $2|V|/3$ vertices such that $G[T]$ has $r$-hop bounded diameter
at most $\frac{1}{2n^{2}}$, where $r=\frac{|E|}{2n^{2}W(\ell)}$. Observe that
for all $r^{\prime}>r$, for every pair $u,v$ of vertices, $D^{\leq
r^{\prime}}(u,v)\leq D^{\leq r}(u,v)$. Observe also that:

$r=\frac{|E|}{2n^{2}W(\ell)}\leq\frac{\frac{dn}{2}}{2n^{2}\frac{d}{nL}}=\frac{L}{4}.$

Therefore, the $L/4$-hop bounded diameter of $G[T]$ is at most
$\frac{1}{2n^{2}}$.

For convenience, for a subset $S\subseteq V$ of vertices and a vertex $u\in
V$, we denote by $D^{\leq L/4}(u,S):=\min_{v\in S}D^{\leq L/4}(u,v)$. We use
the following lemma.

######  Lemma B.2.6 (Adaptation of Lemma 21 from [LR99]).

There is an efficient algorithm, that, given a graph $G=(V,E)$, a parameter
$0<\alpha<1$, any edge length function $\ell:E\mapsto{\mathbb{R}}_{\geq 0}$, a
length parameter $L\geq\frac{2d\ln n}{\alpha}$ and a subset $T\subseteq V$ of
at least $\left\lceil 2|V|/3\right\rceil$ vertices, such that $\sum_{v\in
V}D^{\leq L}(v,T)>\frac{4W(\ell)}{\alpha}$, returns a cut $(S,S^{\prime})$ of
$V$ with sparsity less than $\alpha$.

We prove Lemma B.2.6 later, after we complete the proof of Theorem B.2.3 using
it.

First, we claim that $\sum_{v\in V}D^{\leq L/4}(v,T)>\frac{4W^{*}}{\alpha}$.
Indeed, assume for contradiction otherwise, that is:

$\sum_{v\in V}D^{\leq
L/4}(v,T)\leq\frac{4W^{*}}{\alpha}=\frac{4}{\alpha}\cdot\frac{\alpha}{64n\log
n}=\frac{1}{16n\log n}.$

Recall that the $L/4$-hop bounded diameter of $G[T]$ is at most
$\frac{1}{2n^{2}}$. From the triangle inequality, for any pair $u,v\in V$ of
vertices:

$D^{\leq L}(u,v)\leq D^{\leq L/4}(u,T)+D^{\leq L/4}(v,T)+\frac{1}{2n^{2}}.$

Hence,

$\sum_{u,v\in V}D^{\leq L}(u,v)\leq\sum_{u,v\in V}\left(D^{\leq
L/4}(u,T)+D^{\leq L/4}(v,T)+\frac{1}{2n^{2}}\right)$
$\indent\leq\frac{1}{2}+2n\sum_{u\in V}D^{\leq L/4}(u,T)$
$\indent\leq\frac{1}{2}+2n\frac{1}{16n\log n}=\frac{1}{2}+\frac{1}{8\log
n}<1,$

contradicting the fact that $\ell$ is a valid solution to (LP-2). Therefore,
$\sum_{u\in V}D^{L/4}(v,T)>\frac{4W^{*}}{\alpha}$ must hold. Moreover, notice
that $\frac{L}{4}=\frac{16d\log n}{\alpha}\geq\frac{2d\ln n}{\alpha}$ holds.
We now apply the algorithm from Lemma B.2.6 to $G$, with parameters $\alpha$
and $L/4$, edge length function $\ell$ and the subset $T$ of vertices, to
obtain a cut $(S,S^{\prime})$ of $V$ with sparsity less than $\alpha$. This
completes the proof of Theorem B.2.3, except for the proofs of Lemma B.2.5 and
Lemma B.2.6 that we provide in the next subsection.

####  B.2.8 Proof of Lemma B.2.5

We start with the following definition:

######  Definition..

Given a graph $G=(V,E)$, a partition of $G$ into components is a collection
${\mathcal{G}}=\left\\{G[V_{1}],\ldots,G[V_{z}]\right\\}$ of vertex-induced
subgraphs such that $\bigcup_{i\in[z]}V_{i}=V$ and for every $i\neq j$,
$V_{i}\cap V_{j}=\emptyset$.

We use the following lemma, that we prove later for completeness after
completing the proof of Lemma B.2.5 using it.

######  Lemma B.2.7 (Adaptation of Lemma 19 from [LR99]).

There is an efficient algorithm, that, given a graph $G=(V,E)$, a parameter
$\Delta>0$, and any edge length function $\ell:E\mapsto{\mathbb{R}}_{\geq 0}$,
partitions $G$ into components
${\mathcal{G}}=\left\\{G[V_{1}],\ldots,G[V_{z}]\right\\}$ such that the
following holds:

  * •

For each $G[V_{i}]\in{\mathcal{G}}$, the $r^{\prime}$-hop bounded diameter of
$G[V_{i}]$ is at most $\Delta$, for $r^{\prime}=\Delta|E|/W(\ell)$; and

  * •

$\sum_{i<j}|E(V_{i},V_{j})|<8W(\ell)\log n/\Delta$.

We use Lemma B.2.7 with $\Delta=\frac{1}{2n^{2}}$ and edge length function
$\ell$ to obtain a collection
${\mathcal{G}}=\left\\{G[V_{1}],\ldots,G[V_{z}]\right\\}$ of components.
Notice that
$r^{\prime}=\frac{\Delta|E|}{W(\ell)}=\frac{|E|}{2n^{2}W(\ell)}=r$, so the
$r$-hop bounded diameter of each subgrpaph $G[V_{i}]$ is at most $1/n^{2}$.

If, for some subgraph $G[V_{i^{*}}]\in{\mathcal{G}}$,
$|V_{i^{*}}|\geq\frac{2|V|}{3}$, then we return $V_{i^{*}}$. Otherwise, we use
Observation 3.2.1, to obtain a partition of the graphs in ${\mathcal{G}}$ into
two subsets, ${\mathcal{G}}^{\prime}$ and ${\mathcal{G}}^{\prime\prime}$, such
that, if we let $S=\bigcup_{G_{i}\in{\mathcal{G}}^{\prime}}V(G_{i})$, and
$S^{\prime}=\bigcup_{G_{i}\in{\mathcal{G}}^{\prime}}V(G_{i})$, then
$|S|,|S^{\prime}|\geq|V|/4$ and $|E(S,S^{\prime})|<\frac{8W(\ell)\log
n}{\Delta}=16W(\ell)n^{2}\log n$. Therefore, the sparsity of the cut
$(S,S^{\prime})$ is less than:

$\frac{16W(\ell)n^{2}\log n}{n/4}=64W(\ell)n\log n\leq 64n\log
n\cdot\frac{\alpha}{64n\log n}=\alpha.$

This completes the proof of Lemma B.2.5 except for the proof of Lemma B.2.7
that we provide next.

Proof of Lemma B.2.7. If $\Delta<\frac{8W(\ell)\log n}{|E|}$, we output
${\mathcal{G}}=\left\\{G[\left\\{v\right\\}]\>|\>v\in V\right\\}$. Notice that
for each $G[V_{i}]$, we have $G[V_{i}]=G[\left\\{v_{i}\right\\}]$ for some
$v_{i}\in V$. Hence, the $r^{\prime}$-hop bounded diameter of $G[V_{i}]$ is
$0$, and we have $\sum_{i<j}|E(V_{i},V_{j})|=|E|<\frac{8W(\ell)\log
n}{\Delta}$ as required. Therefore, we assume from now on that
$\Delta\geq\frac{8W(\ell)\log n}{|E|}>\frac{8W(\ell)\ln n}{|E|}$ holds. For
convenience, we denote $\epsilon:=\frac{2W(\ell)\ln n}{\Delta|E|}$. Notice
that $\epsilon\leq 1/4$ holds.

Consider an auxiliary graph $G^{+}=(V^{+},E^{+})$ obtained from $G$ by
replacing each edge $e$ with a path consisting of
$\left\lceil|E|\ell(e)/W(\ell)\right\rceil$ edges. Notice that $|E^{+}|\leq
2|E|$. For simplicity, we identify the common vertices of $G$ and $G^{+}$. The
following observation is now immediate:

######  Observation B.2.8.

For any path of length $\gamma$ in $G^{+}$, the corresponding path in $G$ has
length at most $\frac{W(\ell)\gamma}{|E|}$.

Next, we iteratively partition vertices of $G^{+}$ into
$V_{0}^{+},V_{1}^{+},\ldots,$ and the required partition of $G$ into
components will be given by $G[V_{1}]=G[V_{1}^{+}\cap
V],G[V_{2}]=G[V_{2}^{+}\cap V],\ldots,$. We start with $V^{+}_{0}=\emptyset$
and then iterate. We now show how to compute $V_{i+1}^{+}$ given
$V_{0}^{+},\ldots,V_{i}^{+}$.

We denote $V_{i}^{*}:=V^{+}\backslash\bigcup_{j\leq i}V_{j}^{+}$. If $V\cap
V_{i}^{*}=\emptyset$, we have computed the desired partition and the algorithm
terminates. Thus, we assume from now on that there is a vertex $v_{i+1}\in
V_{i}^{*}$. For every integer $j\geq 0$, we denote by $B^{i+1}_{j}$ the subset
of vertices $u\in V_{i}^{*}$, such that there is some path of length at most
$j$ connecting $v_{i+1}$ and $u$ in $G^{+}[V^{*}_{i}]$.

We let $C_{j}:=\frac{2|E|}{n}+|E_{G}[B^{i+1}_{j}]|$ for every integer $j\geq
0$. Let $j^{*}_{i+1}$ be the smallest $j\geq 0$ such that
$C_{j+1}<(1+\epsilon)C_{j}$. Notice that some such $j^{*}_{i+1}$ must exist,
since $\epsilon>0$ and $C_{j+1}=C_{j}$ for $j\rightarrow\infty$. We set
$V_{i+1}^{+}=B^{i+1}_{j^{*}_{i+1}}$ and proceed to the next iteration. The
following observation is now immediate:

######  Observation B.2.9.

For every index $i>0$, $V_{i}^{+}\cap V\neq\emptyset$ and
$|E(V_{i}^{+},V_{i}^{*})|<\epsilon\left(\frac{2|E|}{n}+\left|E[V_{i}^{+}]\right|\right)$.

###### Proof.

Notice that for every index $i>0$ and $j\geq 0$, we have $v_{i}\in B_{j}^{i}$.
Thus, $v_{i}\in V_{i}^{+}\cap V$, and hence $V_{i}^{+}\cap V\neq\emptyset$.
From our construction, we have

$\frac{2|E|}{n}+\left|E[B_{j_{i}^{*}+1}^{i}]\right|<(1+\epsilon)\left(\frac{2|E|}{n}+\left|E[B_{j_{i}^{*}}^{i}]\right|\right).$

Equivalently:

$\left|E[B_{j_{i}^{*}+1}^{i}]\right|-\left|E[B_{j_{i}^{*}}^{i}]\right|<\epsilon\left(\frac{2|E|}{n}+\left|E[B_{j_{i}^{*}}^{i}]\right|\right).$

Therefore,

$|E(V_{i}^{+},V_{i}^{*})|\leq\left|E[B_{j_{i}^{*}+1}^{i}]\right|-\left|E[B_{j_{i}^{*}}^{i}]\right|<\epsilon\left(\frac{2|E|}{n}+\left|E[B_{j_{i}^{*}}^{i}]\right|\right)=\epsilon\left(\frac{2|E|}{n}+\left|E[V_{i}^{+}]\right|\right).$

The following two claims will complete the proof of Lemma B.2.7.

######  Claim B.2.10.

$\sum_{i<j}|E(V_{i},V_{j})|<\frac{8W(\ell)\log n}{\Delta}$.

###### Proof.

$\sum_{i<j}|E(V_{i},V_{j})|=\sum_{i>0}\left|E\left(V_{i},\bigcup_{j>i}V_{j}\right)\right|\leq\sum_{i>0}|E(V_{i}^{+},V_{i}^{*})|<\sum_{i>0}\epsilon\left(\frac{2|E|}{n}+|E(|V_{i}^{+}|)|\right)$
$\indent\leq\epsilon\left(2|E|+|E^{+}|\right)\leq
4|E|\epsilon=\frac{8W(\ell)\ln n}{\Delta}<\frac{8W(\ell)\log n}{\Delta}.$

Here, the second inequality follows from Observation B.2.9 and the penultimate
inequality follows from the fact that $|E^{+}|\leq 2|E|$.

######  Claim B.2.11.

For each $G[V_{i}]$, the $r^{\prime}$-hop bounded diameter of $G[V_{i}]$ is at
most $\Delta$, for $r^{\prime}=\frac{\Delta|E|}{W(\ell)}$.

###### Proof.

We claim that it suffices to show that, for each $G[V_{i}]$, the diameter of
$G^{+}[V^{+}_{i}]$ is at most $r^{\prime}=\frac{\Delta|E|}{W(\ell)}$. Indeed,
if this is the case, Observation B.2.8 implies that the $r^{\prime}$-hop
bounded diameter of $G[V_{i}]$ is at most
$\frac{W(\ell)r^{\prime}}{|E|}=\Delta$. Notice that, in order to show that the
diameter of $G^{+}[V_{i}^{+}]$ is at most $r^{\prime}$, it suffices to show
that $j^{*}_{i}\leq\frac{r^{\prime}}{2}=\frac{\Delta|E|}{2W(\ell)}$. Fix any
index $i$ and the corresponding graph $G^{+}[V_{i}^{+}]$. If $j_{i}^{*}\neq
0$, we must have:

$2|E|\geq|E^{+}|\geq|E(V_{i}^{+})|>(1+\epsilon)^{j^{*}_{i}}\frac{2|E|}{n}.$

Therefore, $(1+\epsilon)^{j^{*}_{i}}<n$ must hold, and so:

$j^{*}_{i}<\frac{\ln n}{\epsilon}=\frac{\Delta|E|}{2W(\ell)}.$

(We have used the fact that $\epsilon<1/4$).

$\Box$

####  B.2.9 Proof of Lemma B.2.6

Similarly to the proof of Lemma B.2.6, consider an auxiliary graph
$G^{+}=(V^{+},E^{+})$ obtained from $G$ by replacing each edge $e$ with a path
consisting of $\left\lceil|E|\ell(e)/W(\ell)\right\rceil$ edges. Notice that
$|E^{+}|\leq 2|E|$. For simplicity, we identify the common vertices of $G$ and
$G^{+}$. Given a subset $S\subseteq V(G^{+})$ of vertices, we denote by $N(S)$
the set of all vertices $v\in V(G^{+})$ such that $v\not\in S$, but $v$ has a
neighbor in $S$.

Next, we iteratively partition the vertices of $G^{+}$ into layers,
$V^{+}_{0},V^{+}_{1},\ldots$, and for each $i\geq 0$, we define the
corresponding graph $G^{+}_{i}=G^{+}[V^{+}_{i}]$, as follows. We start with
$V^{+}_{0}=T$, $G^{+}_{0}=G^{+}[T]$ and then iterate. We now show how to
compute $V^{+}_{i+1}$ and $G^{+}_{i+1}$, given $V^{+}_{i}$ and $G^{+}_{i}$,
assuming that $V^{+}_{i}\neq V^{+}$ (otherwise, the algorithm terminates).

Let $E_{i}:=\delta_{G^{+}}(V^{+}_{i})$ and $C_{i}:=|E_{i}|$. We partition
$E_{i}$ into two subsets: set $E^{\prime}_{i}$ containing all edges $(u,v)$
with $u\in V^{+}_{i}$, such that $v$ is a vertex of the original graph $G$;
and set $E^{\prime\prime}_{i}$ containing all remaining edges. Let
$C^{\prime}_{i}=|E_{i}^{\prime}|$, and let
$C^{\prime\prime}_{i}=|E^{\prime\prime}_{i}|$. We distinguish between the
following two cases:

  * •

Case 1: $C^{\prime}_{i}\geq C_{i}/2$. In this case, we let $V^{+}_{i+1}$
contain all vertices of $V^{+}_{i}\cup N(V^{+}_{i})$. We also set
$G^{+}_{i+1}=G^{+}[V^{+}_{i+1}]$. Notice that in this case,
$|E[G^{+}_{i+1}]\setminus E[G^{+}_{i}]|\geq C_{i}$.

  * •

Case 2: $C^{\prime\prime}_{i}>C_{i}/2$. In this case, we let $V^{+}_{i+1}$
only contain the vertices of $V^{+}_{i}$, and those vertices of $N(V^{+}_{i})$
that do not lie in the original graph $G$, that is:

$V^{+}_{i+1}=V^{+}_{i}\cup(N(V^{+}_{i})\setminus V(G)).$

As before, we set $G^{+}_{i+1}=G^{+}[V^{+}_{i+1}]$. Notice that in this case,
$E[G^{+}_{i+1}]\setminus E[G^{+}_{i}]$ contains all edges of
$E^{\prime\prime}_{i}$, and so $|E[G^{+}_{i+1}]\setminus E[G^{+}_{i}]|\geq
C^{\prime\prime}_{i}>C_{i}/2$.

From the above discussion we obtain the following observation:

######  Observation B.2.12.

For each level $i$, $|E(G^{+}_{i+1})\setminus
E(G^{+}_{i})|\geq\frac{C_{i}}{2}$, and in particular $\sum_{i}C_{i}\leq
2|E^{+}|$.

For each level $i$, let $n_{i}=|V(G)\backslash V^{+}_{i}|$ – the number of
vertices of the original graph $G$ that do not lie in $V^{+}_{i}$. Recall that
$|T|\geq\left\lceil 2|V|/3\right\rceil$, and so for all $i$,
$n_{i}\leq|V|/3\leq|V|/2$. Moreover,
$C_{i}=|\delta_{G^{+}}(V^{+}_{i})|\geq|\delta_{G}(V\cap V^{+}_{i})|$.

If, for any level $i$, $C_{i}<\alpha n_{i}$, then we return the cut $(V\cap
V^{+}_{i},V\backslash V^{+}_{i})$; it is immediate to see that its sparsity is
less than $\alpha$. Therefore, we assume from now on, that for all $i$,
$C_{i}\geq\alpha n_{i}$. We will reach a contradiction by showing that
$\sum_{v\in V}D^{\leq L}(v,T)\leq\frac{4W(\ell)}{\alpha}$ must hold. In order
to do so, we use the following two claims.

######  Claim B.2.13.

The number of indices $i$ for which Case $1$ is invoked is at most $L$.

###### Proof.

Let $i$ be an index for which Case $1$ is invoked, so $C^{\prime}_{i}\geq
C_{i}/2$. Recall that we have assumed that $C_{i}\geq\alpha n_{i}$. Since the
maximum vertex-degree of $G$ is bounded by $d$, the number of new vertices of
$V$ that are added to $V^{+}_{i+1}$ is at least
$\frac{C^{\prime}_{i}}{d}\geq\frac{\alpha n_{i}}{2d}$. Therefore, $n_{i+1}\leq
n_{i}(1-\frac{\alpha}{2d})$, and the total number of indices $i$ in which Case
1 is invoked must be bounded by $\frac{2d\ln n}{\alpha}\leq L$.

######  Claim B.2.14.

$\sum_{i}n_{i}\leq\frac{4|E|}{\alpha}$.

###### Proof.

Recall that we have assumed $C_{i}\geq\alpha n_{i}$ for all $i$. Thus,

$\sum_{i}n_{i}\leq\sum_{i}\frac{C_{i}}{\alpha}=\frac{\sum_{i}C_{i}}{\alpha}\leq\frac{2|E^{+}|}{\alpha}\leq\frac{4|E|}{\alpha}.$

Here, the second-last inequality follows from Observation B.2.12 and the last
inequality follows from the fact that $|E^{+}|\leq 2|E|$.

For each vertex $v\in V\backslash T$, let $i_{v}$ be the unique index, such
that $v\in V(G^{+}_{i})$ and $v\not\in V(G^{+}_{i-1})$. For the remaining
vertices $v\in T$, we set $i_{v}=0$. Notice that $v$ must be connected by an
edge to a vertex $u$ with $i_{u}<i_{v}$. Therefore, we can construct a path
$P^{+}_{v}=(v_{0},v_{1},\ldots,v_{r})$ in $G^{+}$, where $v_{0}\in T$,
$v_{r}=v$, and for all $1\leq j\leq r$, $i_{v_{j-1}}<i_{v_{j}}$.

Let $P_{v}$ be the path corresponding to $P^{+}_{v}$ in the original graph
$G$. Since we invoke Case $1$ at most $L$ times, it is easy to verify that
$P_{v}$ contains at most $L$ edges. Moreover:

$D^{\leq L}(v,T)\leq\sum_{e\in P_{v}}\ell(e)\leq\sum_{e\in
P_{v}}\frac{W(\ell)}{|E|}\left\lceil\frac{|E|\ell(e)}{W(\ell)}\right\rceil=\frac{W(\ell)}{|E|}|E(P^{+}_{v})|\leq
i_{v}\frac{W(\ell)}{|E|}.$

Altogether:

$\sum_{v}D^{\leq
L}(v,T)\leq\frac{W(\ell)}{|E|}\sum_{v}i_{v}=\frac{W(\ell)}{|E|}\sum_{i}n_{i}\leq\frac{4W(\ell)}{\alpha},$

where the last inequality follows from Claim B.2.14. This contradicts the
assumption that $\sum_{v}D^{\leq L}(v,T)>\frac{4W(\ell)}{\alpha}$,

completing the proof of Lemma B.2.6.

###  B.3 Proofs Omitted from Section 3.5

####  B.3.1 Proof of Claim 3.5.3.

We start with an arbitrary balanced cut $(U^{\prime},U^{\prime\prime})$ in $G$
with $|U^{\prime}|\geq|U^{\prime\prime}|$, and perform a number of iterations.
In every iteration, we will either establish that $G[U^{\prime}]$ is an
$\Omega(\frac{\beta^{2}}{d})$-expander, or compute the desired partition
$(S,T)$ of $V$, or find a new balanced cut $(J^{\prime},J^{\prime\prime})$ in
$G$ with $|E(J^{\prime},J^{\prime\prime})|<|E(U^{\prime},U^{\prime\prime})|$.
In the first two cases, we terminate the algorithm and return either
$V^{\prime}=U^{\prime}$ (in the first case), or the cut $(S,T)$ (in the second
case). In the last case, we replace $(U^{\prime},U^{\prime\prime})$ with
$(J^{\prime},J^{\prime\prime})$, and continue to the next iteration.

We now describe the execution of an iteration. Recall that we are given a
balanced cut $(U^{\prime},U^{\prime\prime})$ of $G$ with
$|U^{\prime}|\geq|U^{\prime\prime}|$. If
$|E(U^{\prime},U^{\prime\prime})|<\beta\cdot\min\left\\{|U^{\prime}|,|U^{\prime\prime}|\right\\}$,
then we return the cut $(S,T)=(U^{\prime},U^{\prime\prime})$ and terminate the
algorithm. Therefore, we assume that
$|E(U^{\prime},U^{\prime\prime})|\geq\beta\cdot\min\left\\{|U^{\prime}|,|U^{\prime\prime}|\right\\}$.
We apply the algorithm from Theorem 3.2.2 to graph $G[U^{\prime}]$, and
consider the cut $(S,T)$ of $G[U^{\prime}]$ computed by the algorithm. We then
consider two cases. First, if
$|E(S,T)|\geq\frac{\beta}{4}\min\left\\{|S|,|T|\right\\}$, then from Theorem
3.2.2, we are guaranteed that $G[U^{\prime}]$ is an
$\Omega(\frac{\beta^{2}}{d})$-expander. We terminate the algorithm and return
$V^{\prime}=U^{\prime}$.

We assume that $|E(S,T)|<\frac{\beta}{4}\min\left\\{|S|,|T|\right\\}$ from now
on, and we assume w.l.o.g. that $|T|\leq|S|$. We consider again two cases.
First, if $|E(T,U^{\prime\prime})|\leq\frac{\beta}{2}|T|$, we define a new cut
$(S^{\prime},T)$ in $G$, where $S^{\prime}=S\cup U^{\prime\prime}$. We then
get that $|T|\leq|S^{\prime}|$, and moreover,
$|E_{G}(S^{\prime},T)|=|E_{G}(S,T)|+|E_{G}(U^{\prime\prime},T)|<\beta|T|$. We
return the cut $(S^{\prime},T)$ and terminate the algorithm.

The final case is when $|E(T,U^{\prime\prime})|>\frac{\beta}{2}|T|$. In this
case, we are guaranteed that $|E(T,U^{\prime\prime})|>|E(S,T)|$. Therefore, if
we consider the cut $(J^{\prime},J^{\prime\prime})$, where $J^{\prime}=S$ and
$J^{\prime\prime}=T\cup U^{\prime\prime}$, then
$(J^{\prime},J^{\prime\prime})$ is a balanced cut in $G$, and moreover:

$|E(J^{\prime},J^{\prime\prime})|=|E(S,U^{\prime\prime})|+|E(S,T)|<|E(S,U^{\prime\prime})|+|E(T,U^{\prime\prime})|=|E(U^{\prime},U^{\prime\prime})|.$

We then replace $(U^{\prime},U^{\prime\prime})$ with the new cut
$(J^{\prime},J^{\prime\prime})$, and continue to the next iteration. It is
easy to verify that every iteration can be executed in time
$\operatorname{poly}(n)$. Since the number of the edges in the set
$E(U^{\prime},U^{\prime\prime})$ decreases in every iteration, the number of
iterations is also bounded by $\operatorname{poly}(n)$. This completes the
proof of Claim 3.5.3.

####  B.3.2 Corollary 3.5.4

Throughout the algorithm, we maintain a set $E^{\prime}$ of edges of $G$ that
we remove from the graph, starting with $E^{\prime}=\emptyset$, and a
collection ${\mathcal{G}}$ of disjoint induced subgraphs of $G\setminus
E^{\prime}$, starting with ${\mathcal{G}}=\left\\{G\right\\}$. The algorithm
continues as long as there is some graph $H\in{\mathcal{G}}$, with
$|V(H)|>3|V(G)|/4$. In every iteration, we select the unique graph
$H\in{\mathcal{G}}$ with $|V(H)|>3|V(G)|/4$, and apply Claim 3.5.3 to it, with
the parameter $\beta/4$. If the outcome is a subset $V^{\prime}\subseteq V(H)$
of vertices, such that $|V(H)|/2\leq|V^{\prime}|\leq 3|V(H)|/4$, and
$H[V^{\prime}]$ is an $\Omega(\frac{\beta^{2}}{d})$-expander, then we return
$V^{\prime}$: it is easy to verify that $n/4\leq|V^{\prime}|\leq 3n/4$, so
$V^{\prime}$ is a valid output. Otherwise, we obtain a partition
$(S^{\prime},T^{\prime})$ of $V(H)$ with
$|E(S^{\prime},T^{\prime})|<\frac{\beta}{4}\cdot\min\left\\{|S^{\prime}|,|T^{\prime}|\right\\}$.
We add the edges of $E(S^{\prime},T^{\prime})$ to $E^{\prime}$, remove $H$
from ${\mathcal{G}}$, and add $H[S^{\prime}]$ and $H[T^{\prime}]$ to
${\mathcal{G}}$ instead. If $|S^{\prime}|<|T^{\prime}|$, then our algorithm
will never attempt to process the graph $H[S^{\prime}]$ again, so we _charge_
the edges of $E(S^{\prime},T^{\prime})$ to the vertices of $S^{\prime}$, where
every vertex of $S^{\prime}$ is charged fewer than $\beta/4$ units. The
algorithm terminates when every graph $H\in{\mathcal{G}}$ has $|V(H)|\leq
3n/4$ (unless it terminates earlier with an expander). Notice that from our
charging scheme, at the end of the algorithm, $|E^{\prime}|<n\beta/4$.
Moreover, using Observation 3.2.1, we can partition the final collection
${\mathcal{H}}$ of graphs into two subsets,
${\mathcal{H}}^{\prime},{\mathcal{H}}^{\prime\prime}$, such that
$\sum_{H\in{\mathcal{H}}^{\prime}}|V(H)|,\sum_{H\in{\mathcal{H}}^{\prime\prime}}|V(H)|\geq
n/4$. Letting $S=\bigcup_{H\in{\mathcal{H}}^{\prime}}V(H)$ and
$T=\bigcup_{H\in{\mathcal{H}}^{\prime\prime}}V(H)$, we obtain a balanced
partition $(S,T)$ of $V(G)$. Since $E(S,T)\subseteq E^{\prime}$, we get that
$|E(S,T)|<\frac{\beta n}{4}\leq\beta\cdot\min\left\\{|S|,|T|\right\\}$.

####  B.3.3 Proof of Claim 3.5.6.

The proof is very similar to the proof of Claim 3.2.3. The algorithm
iteratively removes edges from $G\setminus E^{\prime}$, until we obtain a
connected component of the resulting graph that is an
$\Omega\left(\frac{\alpha^{2}}{d}\right)$-expander. We start with
$G^{\prime}=G\setminus E^{\prime}$ (notice that $G^{\prime}$ is not
necessarily connected). We also maintain a set $E^{\prime\prime}$ of edges
that we remove from $G^{\prime}$, initialized to $E^{\prime\prime}=\emptyset$.
We then perform a number of iterations. In every iteration, we apply Theorem
3.2.2 to $G^{\prime}$, and obtain a cut $(X,Y)$ in $G^{\prime}$. If
$|E_{G^{\prime}}(X,Y)|\geq\alpha\cdot\min{(|X|,|Y|)}/4$, then, from Theorem
3.2.2, $G^{\prime}$ is an $\Omega\left(\frac{\alpha^{2}}{d}\right)$-expander.
We terminate the algorithm and return $G^{\prime}$. We later show that
$|V(G^{\prime})|\geq|V|-\frac{4|E^{\prime}|}{\alpha}$. Assume now that
$|E_{G^{\prime}}(X,Y)|<\alpha\cdot\min{(|X|,|Y|)}/4$, and assume w.l.o.g. that
$|X|\geq|Y|$. Update $G^{\prime}$ to be $G^{\prime}[X]$, add the edges of
$E(X,Y)$ to $E^{\prime\prime}$, and continue to the next iteration. Clearly,
at the end of the algorithm, we obtain a graph $G^{\prime}$ that is an
$\Omega\left(\frac{\alpha^{2}}{d}\right)$-expander. It only remains to show
that $|V(G^{\prime})|\geq|V|-\frac{4|E^{\prime}|}{\alpha}$. The remainder of
the analysis is identical to the analysis of Claim 3.2.3.

Assume that the algorithm performs $r$ iterations, and for each $1\leq i\leq
r$, let $(X_{i},Y_{i})$ be the cut computed by the algorithm in iteration $i$.
Since $|X_{i}|\geq|Y_{i}|$, $|Y_{i}|\leq|V(G)|/2$. At the same time, if we
denote $E_{i}=E^{\prime\prime}\cap E(X_{i},Y_{i})$, then
$|E_{i}|<\alpha|Y_{i}|/4$. Therefore:

$|E^{\prime\prime}|=\sum_{i=1}^{r}|E_{i}|<\alpha\sum_{i=1}^{r}|Y_{i}|/4.$

On the other hand, since $G$ is an $\alpha$-expander, the total number of
edges leaving each set $Y_{i}$ in $G$ is at least $\alpha|Y_{i}|$, and all
such edges lie in $E^{\prime}\cup E^{\prime\prime}$. Therefore:

$|E^{\prime}|+|E^{\prime\prime}|\geq\alpha\sum_{i=1}^{r}|Y_{i}|/2.$

Combining both bounds, we get that
$|E^{\prime}|\geq\alpha\sum_{i=1}^{r}|Y_{i}|/4$, and so
$\sum_{i=1}^{r}|Y_{i}|\leq\frac{4|E^{\prime}|}{\alpha}$. Therefore,
$|V(G^{\prime})|=|V|-\sum_{i=1}^{r}|Y_{i}|\geq|V|-\frac{4|E^{\prime}|}{\alpha}$.
$\Box$

####  B.3.4 Proof of Claim 3.5.9.

We can compute the largest-cardinality set of disjoint paths connecting
vertices of $A$ to vertices of $B$ in $G$ using standard maximum $s$–$t$ flow
computation and the integrality of flow. Therefore, it is sufficient to show
that there exists a set of $\left\lceil\alpha z/d\right\rceil$ disjoint paths
connecting $A$ to $B$ in $G$.

Assume otherwise. Then, from Menger’s theorem, there is a set $Z$ of fewer
than $\alpha z/d$ vertices in $G$, such that $G\setminus Z$ contains no path
from a vertex of $A\setminus Z$ to a vertex of $B\setminus Z$. Let
$E^{\prime}$ be the set of all edges of $G$ incident to the vertices of $Z$.
Since the maximum vertex degree in $G$ is at most $d$, $|E^{\prime}|<\alpha
z$. Therefore, graph $G\setminus E^{\prime}$ contains no path connecting a
vertex of $A$ to a vertex of $B$. Let $X$ be the union of all connected
components of $G\setminus E^{\prime}$ containing the vertices of $A$, and let
$Y=V(G)\setminus X$. Then $|E(X,Y)|\leq|E^{\prime}|<\alpha
z\leq\alpha\cdot\min\left\\{|X|,|Y|\right\\}$, contradicting the fact that $G$
is an $\alpha$-expander. $\Box$

####  B.3.5 Proof of Theorem 3.5.10.

The main tool that we use for the proof of Theorem 3.5.10 is the following
theorem, whose proof appeared in [CC16b]; we include the proof here for
completeness.

######  Theorem B.3.1 (Restatement of Theorem A.4 in [CC16b]).

There is an efficient algorithm, that, given a graph $G$ with maximum vertex
degree at most $d$, an integer $q\geq 1$, and a set ${\mathcal{P}}$ of at
least $16dq$ disjoint paths in $G$, computes a subset
${\mathcal{P}}^{\prime}\subseteq{\mathcal{P}}$ of at least $|{\mathcal{P}}|/2$
paths, and a collection ${\mathcal{C}}$ of disjoint connected subgraphs of
$G$, such that each path $P\in{\mathcal{P}}^{\prime}$ is completely contained
in some subgraph $C\in{\mathcal{C}}$, and each such subgraph contains at least
$q$ and at most $4dq$ paths in ${\mathcal{P}}$.

###### Proof.

Starting from $G$, we construct a new graph $H$, by contracting every path
$P\in{\mathcal{P}}$ into a super-node $u_{P}$. Let $U=\left\\{u_{P}\mid
P\in{\mathcal{P}}\right\\}$ be the resulting set of super-nodes. Let $\tau$ be
any spanning tree of $H$, rooted at an arbitrary vertex $r$. Given a vertex
$v\in V(\tau)$, let $\tau_{v}$ be the sub-tree of $\tau$ rooted at $v$. Let
$J^{\prime}_{v}\subseteq V(G)$ be the set of all vertices of $\tau_{v}$ that
belong to the original graph $G$ (that is, they are not super-nodes), and let
$J^{\prime\prime}_{v}$ be the set of all vertices of $G$ that lie on paths
$P\in{\mathcal{P}}$ with $u_{P}\in\tau_{v}$. We then let
$J_{v}=J^{\prime}_{v}\cup J^{\prime\prime}_{v}$. We also denote
$G_{v}=G[J_{v}]$; observe that it must be a connected graph. Over the course
of the algorithm, we will delete some vertices from $\tau$. The notation
$\tau_{v}$ and $G_{v}$ is always computed with respect to the most current
tree $\tau$. We start with
${\mathcal{C}}=\emptyset,{\mathcal{P}}^{\prime}=\emptyset$, and then iterate.

Each iteration is performed as follows. If $q\leq|V(\tau)\cap U|\leq 4dq$,
then we add the graph $G_{r}$ corresponding to the root $r$ of $\tau$ to
${\mathcal{C}}$, and terminate the algorithm. If $|V(\tau)\cap U|<q$, then we
also terminate the algorithm (we will show later that
$|{\mathcal{P}}^{\prime}|\geq|{\mathcal{P}}/2|$ at this point). Otherwise, let
$v$ be the lowest vertex of $\tau$ with $|\tau_{v}\cap U|\geq q$. If $v\not\in
U$, then, since the degree of every vertex in $G$ is at most $d$,
$|\tau_{v}\cap U|\leq dq$. We add $G_{v}$ to ${\mathcal{C}}$, and all paths in
$\left\\{P\mid u_{P}\in\tau_{v}\right\\}$ to ${\mathcal{P}}^{\prime}$. We then
delete all vertices of $\tau_{v}$ from $\tau$, and continue to the next
iteration.

Assume now that $v=u_{P}$ for some path $P\in{\mathcal{P}}$. If $|\tau_{v}\cap
U|\leq 4dq$, then we add $G_{v}$ to ${\mathcal{C}}$, and all paths in
$\left\\{P^{\prime}\mid u_{P^{\prime}}\in\tau_{v}\right\\}$ to
${\mathcal{P}}^{\prime}$ and continue to the next iteration. So we assume that
$|\tau_{v}\cap U|>4dq$.

Let $v_{1},\ldots,v_{z}$ be the children of $v$ in $\tau$. Build a new tree
$\tau^{\prime}$ as follows. Start with the path $P$, and add the vertices
$v_{1},\ldots,v_{z}$ to $\tau^{\prime}$. For each $1\leq i\leq z$, let
$(x_{i},y_{i})\in E(G)$ be any edge connecting some vertex $x_{i}\in V(P)$ to
some vertex $y_{i}\in V(G_{v_{i}})$; such an edge must exist from the
definition of $G_{v_{i}}$ and $\tau$. Add the edge $(v_{i},x_{i})$ to
$\tau^{\prime}$. Therefore, $\tau^{\prime}$ is the union of the path $P$, and
a number of disjoint stars whose centers lie on the path $P$, and whose leaves
are the vertices $v_{1},\ldots,v_{z}$. The degree of every vertex of $P$ is at
most $d$. We define the _weight_ of the vertex $v_{i}$ as the number of the
paths in ${\mathcal{P}}$ contained in $G_{v_{i}}$ (equivalently, it is
$|U\cap\tau_{v_{i}}|$). Recall that the weight of each vertex $v_{i}$ is at
most $q$, by the choice of $v$. For each vertex $x\in P$, the weight of $x$ is
the total weight of its children in $\tau^{\prime}$. Recall that the total
weight of all vertices of $P$ is at least $4dq$, and the weight of every
vertex is at most $dq$. We partition $P$ into a number of disjoint segments
$\Sigma=(\sigma_{1},\ldots,\sigma_{\ell})$ of weight at least $q$ and at most
$4dq$ each, as follows. Start with $\Sigma=\emptyset$, and then iterate. If
the total weight of the vertices of $P$ is at most $4dq$, we build a single
segment, containing the whole path. Otherwise, find the shortest segment
$\sigma$ starting from the first vertex of $P$, whose weight is at least $q$.
Since the weight of every vertex is at most $dq$, the weight of $\sigma$ is at
most $2dq$. We then add $\sigma$ to $\Sigma$, delete it from $P$ and continue.
Consider the final set $\Sigma$ of segments. For each segment $\sigma$, we add
a new graph $C_{\sigma}$ to ${\mathcal{C}}$. Graph $C_{\sigma}$ consists of
the union of $\sigma$, the graphs $G_{v_{i}}$ for each $v_{i}$ that is
connected to a vertex of $\sigma$ with an edge in $\tau^{\prime}$, and the
corresponding edge $(x_{i},y_{i})$. Clearly, $C_{\sigma}$ is a connected
subgraph of $G$, containing at least $q$ and at most $4dq$ paths of
${\mathcal{P}}$. We add all those paths to ${\mathcal{P}}^{\prime}$, delete
all vertices of $\tau_{v}$ from $\tau$, and continue to the next iteration. We
note that path $P$ itself is not added to ${\mathcal{P}}^{\prime}$, but all
paths $P^{\prime}$ with $u_{P^{\prime}}\in V(\tau_{v})$ are added to
${\mathcal{P}}^{\prime}$.

At the end of this procedure, we obtain a collection ${\mathcal{P}}^{\prime}$
of paths, and a collection ${\mathcal{C}}$ of disjoint connected subgraphs of
$G$, such that each path $P\in{\mathcal{P}}^{\prime}$ is contained in some
$C\in{\mathcal{C}}$, and each $C\in{\mathcal{C}}$ contains at least $q$ and at
most $4dq$ paths from ${\mathcal{P}}^{\prime}$. It now remains to show that
$|{\mathcal{P}}^{\prime}|\geq|{\mathcal{P}}|/2$. We discard at most $q$ paths
in the last iteration of the algorithm. Additionally, when $v=u_{P}$ is
processed, if $|\tau_{v}\cap U|>4dq$, then path $P$ is also discarded, but at
least $4dq$ paths are added to ${\mathcal{P}}^{\prime}$. Therefore, overall,
$|{\mathcal{P}}^{\prime}|\geq|{\mathcal{P}}|-\frac{|{\mathcal{P}}|}{4dq+1}-q\geq|{\mathcal{P}}|/2$,
since $|{\mathcal{P}}|\geq 16dq$.

We now turn to prove Theorem 3.5.10. Recall that we are given an
$\alpha$-Expanding Path-of-Sets System
$\Sigma=({\mathcal{S}},{\mathcal{M}},A_{1},B_{3})$ of width $w$ and length
$3$, where $0<\alpha<1$, and the corresponding graph $G_{\Sigma}$ has maximum
vertex degree at most $d$. Our goal is to compute subsets
$\hat{A}_{1}\subseteq A_{1},\hat{B}_{3}\subseteq B_{3}$ of
$\Omega(\alpha^{2}w/d^{3})$ vertices each, such that
$\hat{A}_{1}\cup\hat{B}_{3}$ is well-linked in $G_{\Sigma}$. Notice that we
can assume w.l.o.g. that $w\geq 256d^{3}/\alpha^{2}$, as otherwise it is
sufficient that each set $\hat{A}_{1},\hat{B}_{3}$ contains a single vertex,
which is trivial to ensure.

We apply Claim 3.5.9 to graph $S_{1}$, together with the sets $A_{1},B_{1}$ of
vertices, to compute a set ${\mathcal{P}}_{1}$ of $\left\lceil\alpha
w/d\right\rceil$ node-disjoint paths in $S_{1}$, connecting vertices of
$A_{1}$ to vertices of $B_{1}$. We then set $q=\left\lfloor
16d/\alpha\right\rfloor$, and use Theorem B.3.1, to compute a subset
${\mathcal{P}}^{\prime}_{1}\subseteq{\mathcal{P}}_{1}$ of at least
$|{\mathcal{P}}_{1}|/2\geq\alpha w/(2d)$ paths, and a collection
${\mathcal{C}}$ of disjoint connected subgraphs of $S_{1}$, such that each
path $P\in{\mathcal{P}}^{\prime}_{1}$ is completely contained in some subgraph
$C\in{\mathcal{C}}$, and each such subgraph contains at least $q$ and at most
$4dq$ paths of ${\mathcal{P}}^{\prime}_{1}$. (Note that from our assumption
that $w\geq 256d^{3}/\alpha^{2}$, $|{\mathcal{P}}_{1}|\geq 16dq$). Clearly,
$|{\mathcal{C}}|\geq\frac{|{\mathcal{P}}_{1}^{\prime}|}{4dq}\geq\frac{\alpha^{2}w}{256d^{3}}$.
We select one representative path $P\in{\mathcal{P}}^{\prime}_{1}$ from each
subgraph $C\in{\mathcal{C}}$, so that $P\subseteq C$, and we let
${\mathcal{P}}^{*}_{1}\subseteq{\mathcal{P}}^{\prime}_{1}$ be the resulting
set of paths. We are now ready to define the set $\hat{A}_{1}\subseteq A_{1}$
of vertices: set $\hat{A}_{1}$ contains, for every path
$P\in{\mathcal{P}}^{*}_{1}$, the endpoint of $P$ that lies in $A_{1}$. Note
that
$|\hat{A}_{1}|=|{\mathcal{P}}^{*}_{1}|=|{\mathcal{C}}|\geq\frac{\alpha^{2}w}{256d^{3}}$.
For convenience, for every vertex $a\in\hat{A}_{1}$, we denote by
$P_{a}\in{\mathcal{P}}^{*}_{1}$ the unique path originating at $a$, and we
denote by $C_{a}\in{\mathcal{C}}$ the unique subgraph of $S_{1}$ containing
$P_{a}$.

We select a subset $\hat{B}_{3}\subseteq B_{3}$ of at least
$\frac{\alpha^{2}w}{256d^{3}}$ vertices similarly, by running the same
algorithm in $S_{3}$. The set of paths obtained as the outcome of Theorem
B.3.1 is denoted by ${\mathcal{P}}_{3}^{\prime}$, and the set of connected
subgraphs of $S_{3}$ by ${\mathcal{C}}^{\prime}$. We also denote by
${\mathcal{P}}^{*}_{3}\subseteq{\mathcal{P}}^{\prime}_{3}$ the set of
representative paths that we select from each subgraph of
${\mathcal{C}}^{\prime}$. For every vertex $b\in\hat{B}_{3}$, we denote by
$P_{b}\in{\mathcal{P}}^{*}_{b}$ the unique path originating at $b$, and we
denote by $C_{b}\in{\mathcal{C}}^{\prime}$ the unique subgraph containing
$P_{b}$.

It remains to show that $\hat{A}_{1}\cup\hat{B}_{3}$ is well-linked in
$G_{\Sigma}$. We show this using the same arguments as in [CC16b]. Let
$X,Y\subseteq\hat{A}_{1}\cup\hat{B}_{3}$ be two equal-cardinality sets of
vertices. We need to show that there is a set ${\mathcal{Q}}$ of $|X|=|Y|$
disjoint paths connecting them in $G_{\Sigma}$, such that the paths in
${\mathcal{Q}}$ are internally disjoint from $\hat{A}_{1}\cup\hat{B}_{3}$. We
define a new subgraph $H\subseteq G_{\Sigma}$ as follows: graph $H$ is the
union of the graph $S_{2}$ and the matchings ${\mathcal{M}}_{1}$ and
${\mathcal{M}}_{2}$; additionally, for every vertex $v\in X\cup Y$, we add the
graph $C_{v}$ to $H$. It is now enough to show that there is a set
${\mathcal{Q}}$ of $|X|=|Y|$ disjoint paths connecting $X$ to $Y$ in $H$; such
paths are guaranteed to be internally disjoint from
$\hat{A}_{1}\cup\hat{B}_{3}$. From the integrality of flow, it is sufficient
to show a flow $F$ in $H$, where every vertex in $X$ sends one flow unit,
every vertex in $Y$ receives one flow unit, and every vertex of $H$ carries at
most one flow unit. We now construct such a flow. This flow will be a
concatenation of three flows, $F_{1},F_{2},F_{3}$.

We start by defining the flows $F_{1}$ and $F_{3}$. Consider some vertex $v\in
X\cup Y$, and assume w.l.o.g. that $v\in\hat{A}_{1}$. We select an arbitrary
subset $U_{v}\subseteq B_{1}$ of $q=\left\lfloor 16d/\alpha\right\rfloor$
vertices that serve as endpoints of paths $P\in{\mathcal{P}}_{1}^{\prime}$
that are contained in $C_{v}$. Since $C_{v}$ is a connected graph, vertex $v$
can send $1/q$ flow units to every vertex in $U_{v}$ simultaneously, inside
the graph $C_{v}$, so that the flow on every vertex is at most $1$. We denote
the resulting flow by $F^{v}$.

We obtain the flow $F_{1}$ by taking the union of all flows $F^{v}$ for $v\in
X$, and we obtain the flow $F_{3}$ by taking the union of all flows $F^{v}$
for $v\in Y$ (we reverse the direction of the flow $F^{v}$ in the latter
case).

Let $R_{1}=\bigcup_{v\in X}U_{v}$, and let $R_{2}=\bigcup_{v\in Y}U_{v}$. Note
that $R_{1}\cup R_{2}\subseteq B_{1}\cup A_{3}$. For every vertex $x\in
R_{1}\cup R_{2}$ that lies in $B_{1}$, we let $x^{\prime}$ be the vertex of
$A_{2}$, that is connected to $x$ by an edge of ${\mathcal{M}}_{1}$.
Similarly, for every vertex $x\in R_{1}\cup R_{2}$ that lies in $A_{3}$, we
let $x^{\prime}$ be the vertex of $B_{2}$, that connects to $x$ by an edge of
${\mathcal{M}}_{2}$. Let $R_{1}^{\prime}=\left\\{x^{\prime}\mid x\in
R_{1}\right\\}$ and $R_{2}^{\prime}=\left\\{x^{\prime}\mid x\in
R_{2}\right\\}$. Note that $R_{1}^{\prime},R_{2}^{\prime}$ are disjoint sets
of vertices in $S_{2}$. Since graph $S_{2}$ is an $\alpha$-expander, there is
a flow $F_{2}^{\prime}$ in $S_{2}$, where every vertex in $R_{1}^{\prime}$
sends one flow unit, every vertex in $R_{2}^{\prime}$ sends one flow unit, and
every edge carries at most $1/\alpha$ flow units. Scaling this flow down by
factor $q=\left\lfloor 16d/\alpha\right\rfloor$, we obtain a new flow $F_{2}$
in $S_{2}$, where every vertex of $R_{1}^{\prime}$ sends $1/{q}$ flow units,
every vertex of $R_{2}^{\prime}$ receives $1/{q}$ flow units, and every vertex
of $S_{2}$ carries at most one flow unit.

The final flow $F$ is obtained by concatenating the flows $F_{1},F_{2}$ and
$F_{3}$, and sending $1/{q}$ flow units on every edge of
${\mathcal{M}}_{1}\cup{\mathcal{M}}_{2}$ that is incident to a vertex of
$R_{1}\cup R_{2}$. The flow in $F$ guarantees that every vertex of $X$ sends
one flow unit, every vertex in $Y$ receives one flow unit, and every vertex of
$G_{\Sigma}$ carries at most one flow unit.

##  Appendix C Proofs Omitted from Chapter 4

###  C.1 Proofs Omitted from Section 4.4

#####  C.1.0.1 Proof of Lemma 4.4.1.

For each $0\leq i\leq\log N$, we consider the partition
${\mathcal{B}}^{i}:={\mathcal{B}}_{2^{i}}(S)$ of sequence $S$ into exactly
$2^{i}$ blocks, each of length exactly $N/2^{i}$. We associate a partition
tree $T$ with the partitions ${\mathcal{B}}^{0},\ldots,{\mathcal{B}}^{\log N}$
of $S$ into blocks, as follows. We start with the tree $T$ containing a single
vertex $v(S)$, representing the unique block $S\in{\mathcal{B}}^{0}$. We will
view vertex $v(S)$ as the root of the tree $T$, and we say that it lies at
level $0$ of $T$. For all $1\leq i\leq\log N$, the set of vertices at level
$i$ of the tree $T$ is $\left\\{v(B)\mid B\in{\mathcal{B}}^{i}\right\\}$, that
is, we have one vertex for every block in the partition ${\mathcal{B}}^{i}$.
For each such vertex $v(B)$ with $B\in{\mathcal{B}}^{i}$, we let $B^{\prime}$
be the unique block of ${\mathcal{B}}^{i-1}$ with $B\subseteq B^{\prime}$, and
we add an edge connecting $v(B^{\prime})$ to $v(B)$ to the tree $T$, so that
$v(B)$ becomes a child vertex of $v(B^{\prime})$. This completes the
construction of the partition tree $T$. Notice that each non-leaf vertex of
$T$ has exactly two children, and each leaf vertex of $T$ represents a block
of ${\mathcal{B}}^{\log N}$, which contains exactly one element of $S$.

We will say that block $B$ is a parent of block $B^{\prime}$ iff $v(B)$ is a
parent of $v(B^{\prime})$ in the tree $T$. Similarly, we will say that block
$B$ is an _ancestor_ of block $B^{\prime}$ iff vertex $v(B)$ is an ancestor of
$v(B^{\prime})$ (we assume that a vertex of $T$ may not be an ancestor of
itself).

For every block $B\in\bigcup_{i=0}^{\log N}{\mathcal{B}}^{i}$, we denote by
$n(B)$ the number of elements of $S^{\prime}$ lying in $B$. Note that, if $P$
is any leaf-to-root path in the tree $T$, then the values of $n(B)$ of the
blocks $B$ with $v(B)\in P$ are non-decreasing, as we traverse $P$ towards the
root of $T$. We will now _mark_ some vertices of the tree $T$. Specifically,
we mark a vertex $v(B)$ of $T$, iff (i) $n(B)\leq 2Z$; and (ii) for every
ancestor block $B^{\prime}$ of $B$, $n(B^{\prime})>2Z$. If vertex $v(B)$ is
marked, we will sometimes say that block $B$ is marked. Clearly, we never mark
both a vertex and its ancestor. Moreover, every leaf-to-root path $P$ in tree
$T$ has exactly one marked vertex: the last vertex $v(B)$ on$P$ with $n(B)\leq
2Z$.

Let ${\mathcal{B}}^{*}$ denote the set of all marked blocks
$B\in\bigcup_{i=0}^{\log N}{\mathcal{B}}^{i}$. Then the blocks in
${\mathcal{B}}^{*}$ define a partition of the sequence $S$. Moreover, since
each marked block contains at most $2Z$ elements of $S^{\prime}$, we get that
$|{\mathcal{B}}^{*}|\geq|S^{\prime}|/(2Z)$. We let $x_{1},\ldots,x_{1+\log N}$
be such that for each $1\leq i\leq 1+\log N$, we have
$x_{i}=|{\mathcal{B}}^{*}\cap{\mathcal{B}}^{i-1}|$. Notice that
$\sum_{i}x_{i}=|{\mathcal{B}}^{*}|$ and from 4.2.5, there is an index $1\leq
j\leq\log N$ such that
$x_{j}\geq\sum_{i}x_{i}/(2j^{2})=|{\mathcal{B}}^{*}|/(2j^{2})$. We fix such
$j$ and let $\eta=2^{j-1}$ so that
${\mathcal{B}}^{j-1}={\mathcal{B}}_{\eta}(S)$. Let
${\mathcal{B}}^{**}={\mathcal{B}}^{*}\cap{\mathcal{B}}_{\eta}(S)$ and we have,

$|{\mathcal{B}}^{**}|=x_{j}\geq\frac{|{\mathcal{B}}^{*}|}{2j^{2}}=\frac{|{\mathcal{B}}^{*}|}{2(1+\log{\eta})^{2}}\geq\frac{|S^{\prime}|}{4Z\log^{2}{(2\eta)}}.$
(C.1)

We say that a block $B\in{\mathcal{B}}^{**}$ is a _bad block_ iff its parent
block $B^{\prime}$ has $n(B^{\prime})>16Z\log^{2}{(2\eta)}$. We need the
following observation.

######  Observation C.1.1.

The number of bad blocks in ${\mathcal{B}}^{**}$ is at most
$|{\mathcal{B}}^{**}|/2$.

###### Proof.

If $\eta=1$, there are no bad blocks and there is nothing to show. Assume for
contradiction that $\eta\geq 2$ and there are more than
$|{\mathcal{B}}^{**}|/2$ bad blocks in ${\mathcal{B}}^{**}$. If
$B\in{\mathcal{B}}^{**}$ is a bad block, and $B^{\prime}$ is its parent, then
$n(B^{\prime})>16Z\log^{2}{(2\eta)}$. As $B^{\prime}$ may be a parent of at
most two bad blocks in ${\mathcal{B}}^{**}$, we get that there is a set
$\tilde{\mathcal{B}}\subseteq{\mathcal{B}}_{\eta/2}(S)$ of blocks (that are
parent-blocks of bad blocks in ${\mathcal{B}}^{**})$, such that
$|\tilde{\mathcal{B}}|\geq|{\mathcal{B}}^{**}|/4$, and every block
$B^{\prime}\in\tilde{\mathcal{B}}$ has $n(B^{\prime})>16Z\log^{2}{(2\eta)}$.
Since all blocks in $\tilde{\mathcal{B}}$ are disjoint, from Equation C.1,
they collectively contain more than

$|\tilde{\mathcal{B}}|\cdot
16Z\log^{2}{(2\eta)}\geq\frac{|{\mathcal{B}}^{**}|}{4}\cdot
16Z\log^{2}{(2\eta)}\geq|S^{\prime}|$

elements of $S^{\prime}$, a contradiction.

We discard all bad blocks from ${\mathcal{B}}^{**}$. Notice that now
$|{\mathcal{B}}^{**}|\geq\frac{|S^{\prime}|}{8Z\log^{2}{2\eta}}$ holds. Next,
we construct a set $\hat{\mathcal{B}}\subseteq{\mathcal{B}}^{**}$ of blocks,
as follows. We start with $\hat{\mathcal{B}}=\emptyset$. We then iterate, as
long as ${\mathcal{B}}^{**}\neq\emptyset$. In every iteration, we consider
some arbitrary block $B\in{\mathcal{B}}^{**}$. We denote by $B^{\prime}$ its
sibling block and by $B^{\prime\prime}$ its parent block (that is, $v(B)$ and
$v(B^{\prime})$ are both child vertices of $v(B^{\prime\prime})$ in the tree
$T$). Since block $B$ was marked, $n(B^{\prime\prime})>2Z$ must hold.
Moreover, $B$ and $B^{\prime}$ form a partition of the block
$B^{\prime\prime}$, and hence, every element of $B^{\prime\prime}\cap
S^{\prime}$ must lie in either $B$ or $B^{\prime}$. Therefore, either
$n(B)\geq Z$ or $n(B^{\prime})\geq Z$ must hold. In the former case, we add
$B$ to $\hat{\mathcal{B}}$, and in the latter case, we add $B^{\prime}$ to
$\hat{\mathcal{B}}$. Observe that in either case, the block that was added to
$\hat{\mathcal{B}}$ contains at most $16Z\log^{2}{2\eta}$ elements of
$S^{\prime}$, since the block $B$ is not a bad block. We then delete $B$ from
${\mathcal{B}}^{**}$, and, if block $B^{\prime}$ lies in ${\mathcal{B}}^{**}$,
then we delete it from ${\mathcal{B}}^{**}$ as well. The algorithm terminates
once ${\mathcal{B}}^{**}=\emptyset$. It is immediate to verify that, at the
end of the algorithm, the number of blocks in set $\hat{\mathcal{B}}$ is at
least half the number of blocks that originally lied in ${\mathcal{B}}^{**}$.
Moreover, every block of $\hat{\mathcal{B}}$ contains at least $Z$ and at most
$16Z\log^{2}{2\eta}$ elements of $S^{\prime}$. Let
${\mathcal{B}}^{\prime}\subseteq{\mathcal{B}}_{\eta}(S)$ be the set of all
blocks $B_{i}\in{\mathcal{B}}_{\eta}$, for which $Z\leq|B\cap S^{\prime}|\leq
16Z\log^{2}{2\eta}$ holds. Since
$\hat{\mathcal{B}}\subseteq{\mathcal{B}}^{\prime}$,

$\sum_{B_{i}\in{\mathcal{B}}^{\prime}}|B_{i}\cap
S^{\prime}|\geq|\hat{\mathcal{B}}^{\prime}|\cdot
Z\geq\frac{|S^{\prime}|}{16\log^{2}{2\eta}}.$

We now let $S^{\prime\prime}:=\bigcup_{B\in{\mathcal{B}}^{\prime}}B\cap
S^{\prime}$ and the lemma follows. $\Box$

#####  C.1.0.2 Proof of Claim 4.4.5.

For the sake of readability, we let $\alpha:=\log^{2}{(2\psi_{i+1})}$. Let
${\mathcal{B}}^{(2)}_{i}\subseteq{\mathcal{B}}_{i}$ be the set of all stream-
blocks that contribute yes-pairs to ${\mathcal{Y}}^{(2)}_{i+1}$. We say that a
block $B\in{\mathcal{B}}^{(2)}_{i}$ is a _good block_ iff it contributes at
least $2^{j}/(32\alpha)$ pairs to ${\mathcal{Y}}^{(2)}_{i+1}$. Let
${\mathcal{B}}^{*}_{i}\subseteq{\mathcal{B}}^{(2)}_{i}$ be the set of all such
good blocks.

######  Claim C.1.2.

$|{\mathcal{B}}^{*}_{i}|\geq\frac{|{\mathcal{Y}}^{(2)}_{i+1}|}{2^{j+7}\alpha}$.

###### Proof.

Since ${\mathcal{Y}}^{(2)}_{i+1}\subseteq{\mathcal{Y}}^{(1)}_{i+1}$, if a
stream-block $B\in{\mathcal{B}}_{i}$ contributes pairs to
${\mathcal{Y}}^{(2)}_{i+1}$, it also contributes pairs to
${\mathcal{Y}}^{(1)}_{i+1}$. But from our construction, if a stream-block
contributes pairs to ${\mathcal{Y}}^{(1)}_{i+1}$, it contributes at least
$2^{j}$ of them. Thus,
$|{\mathcal{Y}}^{(1)}_{i+1}|\geq|{\mathcal{B}}^{(2)}_{i}|2^{j}$, or in other
words,

$|{\mathcal{B}}^{(2)}_{i}|\leq\frac{|{\mathcal{Y}}^{(1)}_{i+1}|}{2^{j}}\leq\frac{16\alpha|{\mathcal{Y}}^{(2)}_{i+1}|}{2^{j}}$
(C.2)

where the last inequality follows from Equation 4.6. Next we claim that
$|{\mathcal{B}}^{*}_{i}|\geq|{\mathcal{B}}^{(2)}_{i}|/(64\alpha)$. Indeed,
assume otherwise for contradiction. Since each stream-block in
${\mathcal{B}}_{i}$ contributes less than $2^{j+1}$ pairs to
${\mathcal{Y}}^{(1)}_{i+1}$, which in turn, is a superset of
${\mathcal{Y}}^{(2)}_{i+1}$, the total contribution to pairs of
${\mathcal{Y}}^{(2)}_{i+1}$ due to good stream-blocks is at most
$|{\mathcal{B}}^{*}_{i}|\cdot
2^{j+1}<\frac{|{\mathcal{B}}^{(2)}_{i}|}{64\alpha}\cdot
2^{j+1}=\frac{|{\mathcal{B}}^{(2)}_{i}|2^{j}}{32\alpha}$. On the other hand,
each stream-block in ${\mathcal{B}}^{(2)}_{i}\backslash{\mathcal{B}}^{*}_{i}$
contributes less than $2^{j}/(32\alpha)$ pairs to ${\mathcal{Y}}^{(2)}_{i+1}$.
Thus,

$|{\mathcal{Y}}^{(2)}_{i+1}|<\frac{|{\mathcal{B}}^{(2)}_{i}|2^{j}}{32\alpha}+\frac{|{\mathcal{B}}^{(2)}_{i}|2^{j}}{32\alpha}=\frac{|{\mathcal{B}}^{(2)}_{i}|2^{j}}{16\alpha}\leq|{\mathcal{Y}}^{(2)}_{i+1}|,$

a contradiction. Here, the last inequality follows from Equation C.2. So far,
we have shown that
$|{\mathcal{B}}^{*}_{i}|\geq|{\mathcal{B}}^{(2)}_{i}|/(64\alpha)=|{\mathcal{B}}^{(2)}_{i}|/(2^{6}\alpha)$.

We now claim that
$|{\mathcal{B}}^{(2)}_{i}|>|{\mathcal{Y}}^{(2)}_{i+1}|/2^{j+1}$. Indeed,
consider some stream-block $B\in{\mathcal{B}}^{(2)}_{i}$. Recall that $B$
contributes less than $2^{j+1}$ pairs to ${\mathcal{Y}}^{(1)}_{i+1}$, which in
turn, is a superset of ${\mathcal{Y}}^{(2)}_{i+1}$. Thus,
$|{\mathcal{Y}}^{(2)}_{i+1}|<|{\mathcal{B}}^{(2)}_{i}|2^{j+1}$, or in other
words, $|{\mathcal{B}}^{(2)}_{i}|>|{\mathcal{Y}}^{(2)}_{i+1}|/2^{j+1}$. We can
now bound,

$|{\mathcal{B}}^{*}_{i}|\geq\frac{|{\mathcal{B}}^{(2)}_{i}|}{64\alpha}>\frac{|{\mathcal{Y}}^{(2)}_{i+1}|}{2^{j+1}\cdot
64\alpha}=\frac{|{\mathcal{Y}}^{(2)}_{i+1}|}{2^{j+7}\alpha}.$

This completes the proof of Claim C.1.2.

Consider some good stream-block $B\in{\mathcal{B}}^{*}_{i}$. We claim that
there are at most two range-blocks of $\tilde{\mathcal{B}}_{i}$ that
contribute to the pairs of ${\mathcal{Y}}^{(2)}_{i+1}$ belonging to $B$.
Indeed, assume otherwise for contradiction that there are $3$ such range-
blocks
$B^{\prime},B^{\prime\prime},B^{\prime\prime\prime}\in\tilde{\mathcal{B}}_{i}$
in the increasing order of their respective range-elements. Recall that if a
range-block contributes pairs to ${\mathcal{Y}}^{(2)}_{i+1}$, it contributes
at least $2^{j+1}$ of them. Moreover, all the pairs contributed by
$B^{\prime\prime}$ must have their respective stream-blocks contained in $B$.
Thus, $(B,B^{\prime\prime})$ must contribute at least $2^{j+1}$ pairs to
${\mathcal{Y}}^{(2)}_{i+1}$, a contradiction to the fact that $B$ contributes
less than $2^{j+1}$ pairs to ${\mathcal{Y}}^{(1)}_{i+1}$, which in turn, is a
superset of ${\mathcal{Y}}^{(2)}_{i+1}$.

We let
${\mathcal{P}}_{i}\subseteq{\mathcal{B}}^{*}_{i}\times\tilde{\mathcal{B}}_{i}$
be the set of exactly $|{\mathcal{B}}^{*}_{i}|$ pairs, obtained by choosing
for each good stream-block $B\in{\mathcal{B}}^{*}_{i}$, a unique range-block
$B^{\prime}\in\tilde{\mathcal{B}}_{i}$ such that $(B,B^{\prime})$ contribute
at least
$\left\lceil\frac{1}{2}\cdot\frac{2^{j}}{32\alpha}\right\rceil\geq\frac{2^{j-6}}{\alpha}$
pairs to ${\mathcal{Y}}^{(2)}_{i+1}$. Consider some range-block
$B^{\prime}\in\tilde{\mathcal{B}}_{i}$. Since it contributes at most
$2^{j+5}\alpha$ pairs to ${\mathcal{Y}}^{(2)}_{i+1}$, it may appear in at most
$\frac{2^{j+5}\alpha}{{2^{j-6}}/{\alpha}}=2^{11}\alpha^{2}$ pairs of
${\mathcal{P}}_{i}$. It is now immediate to see that there is a subset
${\mathcal{P}}^{\prime}_{i}\subseteq{\mathcal{P}}_{i}$ of at least
$\frac{|{\mathcal{P}}_{i}|}{2^{11}\alpha^{2}}$ pairs such that each range-
block $B^{\prime}\in\tilde{\mathcal{B}}_{i}$ appears in at most one pair. We
let ${\mathcal{Y}}^{(3)}_{i+1}\subseteq{\mathcal{Y}}^{(2)}_{i+1}$ be the set
of pairs obtained by choosing exactly $\left\lceil 2^{j-6}/\alpha\right\rceil$
pairs belonging to each pair $(B,B^{\prime})\in{\mathcal{P}}^{\prime}_{i}$.
From our construction and Claim C.1.2,

$\displaystyle|{\mathcal{Y}}^{(3)}_{i+1}|=|{\mathcal{P}}^{\prime}_{i}|\cdot\left\lceil\frac{2^{j-6}}{\alpha}\right\rceil$
$\displaystyle\geq|{\mathcal{P}}_{i}|\cdot\frac{2^{j-17}}{\alpha^{3}}$
$\displaystyle=|{\mathcal{B}}^{*}_{i}|\cdot\frac{2^{j-17}}{\alpha^{3}}$
$\displaystyle\geq\frac{|{\mathcal{Y}}^{(2)}_{i+1}|}{2^{j+7}\alpha}\cdot\frac{2^{j-17}}{\alpha^{3}}$
$\displaystyle=\frac{|{\mathcal{Y}}^{(2)}_{i+1}|}{2^{24}\alpha^{4}}.$

This completes the proof of Claim 4.4.5. $\Box$

#####  C.1.0.3 Proof of Claim 4.4.6.

Consider some pair $(\hat{B},\hat{B}^{\prime})\in{\mathcal{Y}}^{(3)}_{i+1}$
and its parent-pair
$(B,B^{\prime})\in{\mathcal{B}}_{i}\times\tilde{\mathcal{B}}_{i}$. Since
${(\hat{B},\hat{B}^{\prime})\in{\mathcal{Y}}_{i+1}}$, we have $|B\cap
B^{\prime}|\geq|\hat{B}\cap\hat{B}^{\prime}|\geq Z_{i+1}\Delta_{i+1}$. We now
partition pairs of ${\mathcal{Y}}^{(3)}_{i+1}$ into a number of classes, where
a pair $(\hat{B},\hat{B}^{\prime})$ belongs to the class
${\mathcal{C}}^{\prime}_{j^{\prime}}$ iff it is
$\left(2^{j^{\prime}-1}Z_{i+1}\Delta_{i+1}\right)$-friendly. For each positive
integer $j^{\prime}$, we let
$x_{j^{\prime}}:=|{\mathcal{C}}^{\prime}_{j^{\prime}}|$, the number of pairs
assigned to the class ${\mathcal{C}}^{\prime}_{j^{\prime}}$. Since
$\sum_{j^{\prime}}x_{j^{\prime}}=|{\mathcal{Y}}^{(3)}_{i+1}|$, from 4.2.5,
there is an index $j^{\prime\prime}$ such that
$x_{j^{\prime\prime}}\geq|{\mathcal{Y}}^{(3)}_{i+1}|/2(j^{\prime\prime})^{2}$.
We fix such an integer $j^{\prime\prime}$ and the corresponding class
${\mathcal{C}}^{\prime}_{j^{\prime\prime}}$ containing at least
$\frac{|{\mathcal{Y}}^{3}_{i+1}|}{2(j^{\prime\prime})^{2}}$ pairs of
${\mathcal{Y}}^{(3)}_{i}$. We choose
$\sigma_{i}:=2^{j^{\prime\prime}-1}Z_{i+1}\Delta_{i+1}$ and let
${\mathcal{Y}}^{(4)}_{i+1}$ be the set of all pairs of
${\mathcal{Y}}^{(3)}_{i}$ belonging to the class
${\mathcal{C}}^{\prime}_{j^{\prime\prime}}$. From our choice of these pairs,
each pair in ${\mathcal{Y}}^{(4)}_{i+1}$ is $\sigma_{i}$-friendly.
Furthermore, from our choice of $\sigma_{i}$ such that
$j^{\prime\prime}=\log{\left(\frac{2\sigma_{i}}{Z_{i+1}\Delta_{i+1}}\right)}$,
we have,

$|{\mathcal{Y}}^{(4)}_{i+1}|\geq\frac{|{\mathcal{Y}}^{3}_{i+1}|}{2(j^{\prime\prime})^{2}}=\frac{{\mathcal{Y}}^{(3)}_{i+1}}{2\log^{2}{\left(\frac{2\sigma_{i}}{Z_{i+1}\Delta_{i+1}}\right)}}.$

The claim now follows. $\Box$

#####  C.1.0.4 Proof of 4.4.7.

Consider some pair $(\hat{B},\hat{B}^{\prime})\in{\mathcal{Y}}^{(4)}_{i+1}$
and let $B^{\prime}$ be the parent-block of $\hat{B}^{\prime}$ in
$\tilde{\mathcal{B}}_{i}$. Since
${(\hat{B},\hat{B}^{\prime})\in{\mathcal{Y}}_{i+1}}$, we have $|\hat{B}\cap
B^{\prime}|\geq|\hat{B}\cap\hat{B}^{\prime}|\geq Z_{i+1}\Delta_{i+1}$. On the
other hand, since $(\hat{B},\hat{B}^{\prime})\in{\mathcal{Y}}^{(4)}_{i+1}$ and
$\hat{B}$ is contained in $B$, we have $|\hat{B}\cap B^{\prime}|\leq|B\cap
B^{\prime}|<2\sigma_{i}$. We now partition pairs of
${\mathcal{Y}}^{(4)}_{i+1}$ into
$\log{\left(\frac{2\sigma_{i}}{Z_{i+1}\Delta_{i+1}}\right)}$ classes, where a
pair $(\hat{B},\hat{B}^{\prime})$ belongs to class
${\mathcal{C}}^{\prime}_{j^{\prime}}$ iff
${2^{j^{\prime}}Z_{i+1}\Delta_{i+1}\leq|\hat{B}\cap
B^{\prime}|<2^{j^{\prime}+1}Z_{i+1}\Delta_{i+1}}$. Note that if a pair
$(\hat{B},\hat{B}^{\prime})$ belongs to class
${\mathcal{C}}^{\prime}_{j^{\prime}}$, it is
$(2^{j^{\prime}}Z_{i+1}\Delta_{i+1})$-heavy. From the pigeonhole principle,
there is a class ${\mathcal{C}}^{\prime}_{j^{\prime\prime}}$ containing at
least
$\frac{|{\mathcal{Y}}^{4}_{i+1}|}{\log{\left(\frac{2\sigma_{i}}{Z_{i+1}\Delta_{i+1}}\right)}}$
pairs of ${\mathcal{Y}}^{(4)}_{i+1}$. We let ${\mathcal{Y}}^{(5)}_{i+1}$ be
the set of such pairs. Note that all the pairs of ${\mathcal{Y}}^{(5)}_{i+1}$
are $\sigma^{\prime}_{i}$-heavy, where
$\sigma^{\prime}_{i}=2^{j^{\prime\prime}}Z_{i+1}\Delta_{i+1}$. This completes
the proof of LABEL:{clm:_ncm-sigma-prime-heavy}. $\Box$

#####  C.1.0.5 Proof of Observation 4.4.8.

We first consider the case where $j=i+1$. Let $(\hat{B},\hat{B}^{\prime})$ be
a level-$j$ descendant yes-pair of $(B,B^{\prime})$. Since $S^{*}$ is an
$\Upsilon$-canonical subsequence, $|\hat{B}\cap B^{\prime}|<2Z_{j}\mu_{i}$.
Thus, there are no level-$j$ descendant yes-pairs $(\hat{B},\hat{B}^{\prime})$
of $(B,B^{\prime})$ with $|\hat{B}\cap B^{\prime}|>8Z_{j}\mu_{i}$ and the
observation follows.

We now consider the case where $j>i+1$. Assume for contradiction that there
are at least $\frac{Z_{i}}{4Z_{j}}$ such level-$j$ descendant yes-pairs
$(\hat{B},\hat{B}^{\prime})$ of $(B,B^{\prime})$ with $|\hat{B}\cap
B^{\prime}|>8Z_{j}\mu_{i}$. We let ${\mathcal{P}}_{j}$ be the set of such yes-
pairs. We consider the intermediate level $j^{\prime}=i+1$. By pigeonhole
principle, there is some level-$j^{\prime}$ yes-pair
$(\tilde{B},\tilde{B}^{\prime})$ that has at least
$\frac{{Z_{i}}/\left({4Z_{j}}\right)}{{Z_{i}}/{Z_{j^{\prime}}}}=\frac{Z_{i+1}}{4Z_{j}}$
pairs of ${\mathcal{P}}_{j}$ as its descendants. Since the stream-blocks of
${\mathcal{P}}_{j}$ are disjoint, $|\tilde{B}\cap
B^{\prime}|>\frac{Z_{i+1}}{4Z_{j}}\cdot 8Z_{j}\mu_{i}=2Z_{i+1}\mu_{i}$, a
contradiction to the fact that $(\tilde{B},\tilde{B}^{\prime})$ is a
level-$(i+1)$ yes-pair. $\Box$

#####  C.1.0.6 Proof of Observation 4.4.9.

Notice that the observation is trivial when $Z_{i}=1$. Hence, assume from now
on that $Z_{i}>1$ and let $j>i$ be the lowest level with $Z_{j}<Z_{i}$. Recall
that each level-$j$ yes-block contributes exactly $Z_{j}$ elements to $S^{*}$.
Thus, $\frac{Z_{i}}{2Z_{j}}$ such level-$j$ yes-blocks must appear before the
$\left({\frac{Z_{i}}{2}}+1\right)^{th}$ element of $S^{*}$ in $B$. Moreover,
from Observation 4.4.8 each such yes-block shares at least $Z_{j}\mu_{i}$
elements with $B^{\prime}$. Thus, there are at least
$Z_{j}\mu_{i}\cdot\frac{Z_{i}}{2Z_{j}}=\frac{Z_{i}\mu_{i}}{2}$ elements of
$B\cap B^{\prime}$ appearing before the
$\left({\frac{Z_{i}}{2}}+1\right)^{th}$ element of $S^{*}$ in $B$. $\Box$

###  C.2 Proofs Omitted from Section 4.5

####  C.2.1 Proof Omitted from Section 4.5.1

Proof of Claim 4.5.4. We assume that the block size $|B|$ is known to us in
advance. We first analyze the trivial case when $Z\leq 100\log N$. In this
case, we store all the elements of $B$ and naively compute the desired
collection ${\mathcal{B}}^{*}$ of the range-blocks offline after $B$
terminates. Note that we can perform the offline computation using only
$O(|B|)=\tilde{O}(|B|/Z)$ additional space and there is nothing to show. If
$|B|<Z$, we report the empty collection ${\mathcal{B}}^{*}=\emptyset$. Thus,
assume from now on that $|B|\geq Z>100\log N$.

We will process elements of $B$ as they arrive while maintaining a collection
${\mathcal{B}}^{\prime\prime}$ of the indices of the range-blocks that we call
_suspicious blocks_. Initially, ${\mathcal{B}}^{\prime\prime}=\emptyset$.
Whenever a new element $a_{t}$ of the stream $S$ arrives, we ignore it with
probability $1-\frac{10\log N}{Z}$ and select it with the remaining
probability. If $a_{i}$ is selected, we consider the range-block
$B^{\prime}_{j}\in{\mathcal{B}}^{\prime}$ in which the value of $a_{t}$ lies.
If $B^{\prime}_{j}$ is not already marked suspicious, we mark it thus and add
its index $j$ to ${\mathcal{B}}^{\prime\prime}$. Whenever an range-block
$B^{\prime}_{j}$ is marked suspicious (by adding the index $j$ to the set
${\mathcal{B}}^{\prime\prime}$), we initialize a new algorithm
$\mathsf{AlgCheckBlock}(B^{\prime}_{j})$, that proceeds as follows. Let
$a_{t}\in B\cap B^{\prime}_{j}$ be the element that caused the range-block
$B^{\prime}_{j}$ to marked suspicious. We run the algorithm $\mathsf{Alg}_{2}$
from Lemma 4.2.2 on the subsequent elements of $B\cap B^{\prime}_{j}$ with
parameter $Z$. At the end of processing the last element of $B$, if
$\mathsf{Alg}_{2}$ determines returns yes, we add the index $j$ to
${\mathcal{B}}^{*}$. This completes the description of
$\mathsf{AlgCheckBlock}(B^{\prime})$. If at any point in the execution
$|{\mathcal{B}}^{\prime\prime}|$ exceeds $\frac{20|B|\log N}{Z}$, we
immediately terminate our block-processing algorithm and report
${\mathcal{B}}^{*}=\emptyset$. Otherwise, at the end of stream, we report
${\mathcal{B}}^{*}$. This completes the description of our block-processing
algorithm. We now analyze its properties, starting with its space complexity.

Consider the execution of $\mathsf{Alg}_{2}$ from Lemma 4.2.2 on a subblock
$\hat{B}$ of the stream-block $B$ along with the parameter $Z$. The space
complexity of this run is at most
${\tilde{O}\left(\left\lceil\frac{|\hat{B}|}{Z}\right\rceil\right)=\left\lceil\frac{|\hat{B}|}{Z}\right\rceil\cdot\log^{O(1)}N}$.
It is now immediate to see that the space complexity of our block-processing
algorithm is,

$\displaystyle
O(|{\mathcal{B}}^{\prime\prime}|)+\sum_{B^{\prime}\in{\mathcal{B}}^{\prime\prime}}\left(\left\lceil\frac{|B\cap
B^{\prime}|}{Z}\right\rceil\cdot\log^{O(1)}N\right)$
$\displaystyle\leq\left(|{\mathcal{B}}^{\prime\prime}|\cdot\log^{O(1)}N\right)+\sum_{B^{\prime}\in{\mathcal{B}}^{\prime\prime}}\left({\frac{|B\cap
B^{\prime}|}{Z}}\cdot\log^{O(1)}N\right)$
$\displaystyle\leq\left(|{\mathcal{B}}^{\prime\prime}|\cdot\log^{O(1)}N\right)+\left({\frac{|B|}{Z}}\cdot\log^{O(1)}N\right)$
$\displaystyle\leq{\frac{|B|}{Z}}\cdot\log^{O(1)}N.$

Here, the first inequality follows since for each
$B^{\prime}\in{\mathcal{B}}^{\prime\prime}$, $\left\lceil\frac{|B\cap
B^{\prime}|}{Z}\right\rceil\leq 1+\frac{|B\cap B^{\prime}|}{Z}$ and the last
inequality follows since we ensure that $|{\mathcal{B}}^{\prime\prime}|\leq
O\left(\frac{|B|\log N}{Z}\right)$ throughout our algorithm.

Consider a range-block $B^{\prime}\in{\mathcal{B}}^{\prime}$ with
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(B\cap B^{\prime})<Z/2$. From the
correctness guarantee of Lemma 4.2.2, $\text{\bf
Pr}\left[B^{\prime}\in{\mathcal{B}}^{*}\right]\leq 1/N^{2}$, where the
probability is over the randomness used by $\mathsf{Alg}_{2}$. Since there are
only $|{\mathcal{B}}^{\prime}|\leq N$ such range-blocks, with probability
$1-1/N$, _every_ range-block $B^{\prime}\in{\mathcal{B}}^{*}$ has
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(B\cap B^{\prime})\geq Z/2$.

We now show that each range-block $B^{\prime}\in{\mathcal{B}}^{\prime}$ that
is $(Z,1)$-perfect for $B$ is present in ${\mathcal{B}}^{\prime\prime}$ with
probability at least $3/4$. We denote by ${\mathcal{E}}^{*}_{\mathsf{bad}}$
the event that $|{\mathcal{B}}^{\prime\prime}|>\frac{20|B|\log N}{Z}$ at some
point in our algorithm. For each range-block
$B^{\prime}\in{\mathcal{B}}^{\prime}$ that is $(Z,1)$-perfect for $B$, we
denote by ${\mathcal{E}}_{\mathsf{bad}}(B^{\prime})$ be the event that its
index is not added to ${\mathcal{B}}^{\prime\prime}$ before processing the
$(Z+1)^{th}$ element of $B\cap B^{\prime}$. It now suffices to show that (i)
$\text{\bf Pr}\left[{\mathcal{E}}^{*}_{\mathsf{bad}}\right]\leq 1/N$; and (ii)
for each range-block $B^{\prime}\in{\mathcal{B}}^{\prime}$ that is
$(Z,1)$-perfect for $B$, $\text{\bf
Pr}\left[{\mathcal{E}}_{\mathsf{bad}}(B^{\prime})\right]\leq 0.1$.

To bound $\text{\bf Pr}\left[{\mathcal{E}}^{*}_{\mathsf{bad}}\right]$, it
suffices to bound the probability of sampling more than $\frac{20|B|\log
N}{Z}$ elements. Since we sample each element independently at random with
probability $\frac{10\log N}{Z}$, the expected number of sampled elements is
$\frac{10|B|\log N}{Z}$. From Chernoff bound (see, 4.2.4), the probability
that we sample more than $\frac{20|B|\log N}{Z}$ elements is at most
$e^{-\frac{20|B|\log N}{6Z}}\leq e^{-3\log N}\leq\frac{1}{N^{3}}$. We assume
from now on that the event ${\mathcal{E}}^{*}_{\mathsf{bad}}$ does not occur.
Consider now a range-block $B^{\prime}\in{\mathcal{B}}^{\prime}$ that is
$(Z,1)$-perfect for $B$. We have,

$\text{\bf
Pr}\left[{\mathcal{E}}_{\mathsf{bad}}(B^{\prime})\>|\>\neg\>{\mathcal{E}}^{*}_{\mathsf{bad}}\right]\leq\left(1-\frac{10\log
N}{Z}\right)^{Z}\leq\frac{1}{N},$

and we conclude, $\text{\bf
Pr}\left[{\mathcal{E}}_{\mathsf{bad}}(B^{\prime})\right]\leq\text{\bf
Pr}\left[{\mathcal{E}}^{*}_{\mathsf{bad}}\right]+\text{\bf
Pr}\left[{\mathcal{E}}_{\mathsf{bad}}(B^{\prime})\>|\>\neg\>{\mathcal{E}}^{*}_{\mathsf{bad}}\right]\leq
2/N<0.1$ as claimed. This completes the proof of correctness of our algorithm
and Claim 4.5.4 now follows.

####  C.2.2 Proofs Omitted from Section 4.5.2

#####  C.2.2.1 Proof of Claim 4.5.6.

We start by claiming that there is a level $j\geq i-3\epsilon r$ such that
$Z_{j}>Z_{i}$. Indeed, assume for contradiction that the claim is false. Then
for the level $k=\left\lceil i-3\epsilon r\right\rceil=i-\left\lfloor
3\epsilon r\right\rfloor\geq 0$, $Z_{k}=Z_{i}$. Here, the inequality follows
since $i\geq 3\epsilon r$. But then

$\frac{X_{i}}{Z_{i}}=\frac{X_{k}/\eta^{i-k}}{Z_{k}}=\frac{X_{k}/Z_{k}}{\eta^{\left\lfloor
3\epsilon r\right\rfloor}}\leq\frac{N^{1/2+\epsilon+o(1)}}{\eta^{\left\lfloor
3\epsilon r\right\rfloor}}<N^{1/2-\epsilon},$

where the first inequality follows from Observation 4.5.1. The last inequality
follows since $\eta^{r}~{}\geq~{}N/\eta$ and $\epsilon$ is a small enough
constant. But this is a contradiction to Assumption 4.5.5 that
$\frac{X_{i}}{Z_{i}}>N^{1/2-\epsilon}$. We now fix the largest level
$i-3\epsilon r\leq j<i$ such that $Z_{j}>Z_{i}$. Notice that $X_{j}=\eta
X_{j+1}$ and from our choice of level $j$, we have $Z_{j+1}=Z_{i}$. From
Observation 4.5.1, we now conclude that
$\frac{X_{j}}{Z_{j}}\geq\frac{X_{j+1}}{Z_{j+1}}$, or in other words,
$Z_{j}\leq\eta Z_{i}$. Claim 4.5.6 now follows by noting that both $Z_{i}$ and
$Z_{j}$ are integral powers of $2$. $\Box$

#####  C.2.2.2 Proof of Claim 4.5.7.

We are given a level-$j$ stream-block $B$ and a partition
${\mathcal{B}}^{\prime}={\mathcal{B}}^{j}_{\Psi^{\prime}}(H^{*})$ of the range
$H^{*}$ into range-blocks. Our goal is to achieve
$(Z_{j}/2,\Delta_{i}/8,1)$-approximation in space $N^{1/2-\epsilon+o(1)}$. We
proceed exactly as in the proof of Claim 4.5.4.

We will maintain a collection
${\mathcal{B}}^{\prime\prime}\subseteq{\mathcal{B}}^{\prime}$ of range-blocks
that we call _suspicious blocks_. Initially,
${\mathcal{B}}^{\prime\prime}=\emptyset$. We are given access to the elements
of the stream-block $B$ as they arrive as a part of the original input stream
$S$. Whenever a new element $a_{k}$ of $B$ arrives, we ignore it with
probability $1-\frac{2^{5}}{Z_{i}\Delta_{i}}$ and select it with remaining
probability. If an element $a_{k}$ is selected, we consider the range-block
$B^{\prime}\in{\mathcal{B}}^{\prime}$ in which the value of $a_{k}$ lies. If
$B^{\prime}$ is not already marked suspicious, we mark it thus and add it to
${\mathcal{B}}^{\prime\prime}$. We also run the algorithm $\mathsf{Alg}_{1}$
from Lemma 4.2.1 on the subsequent elements of $B\cap B^{\prime}$ with
parameter $Z=Z_{j}/2$. If at any point in the processing,
$|{\mathcal{B}}^{\prime\prime}|$ exceeds
$2^{10}\frac{X_{j}}{Z_{i}\Delta_{i}}$, we immediately stop and report
${\mathcal{B}}^{*}=\emptyset$. At the end of the processing last element of
$B$, we are ready to report our output. We let
${\mathcal{B}}^{*}\subseteq{\mathcal{B}}^{\prime\prime}$ be the set of all
range-blocks for which the respective execution of $\mathsf{Alg}_{1}$ reported
yes. We report the indices of all range-blocks of ${\mathcal{B}}^{*}$. This
completes the description of our algorithm. We now analyze its properties.

###### Space complexity.

Consider an element $a_{t}\in B$ and the set ${\mathcal{B}}^{\prime\prime}$ of
suspicious blocks just after processing $a_{t}$. Since we ensure that
$|{\mathcal{B}}^{\prime\prime}|\leq 2^{10}\frac{X_{j}}{Z_{i}\Delta_{i}}$
throughout the execution of our algorithm, the space used by our algorithm at
the end of processing the element $a_{t}$ is at most,

$\displaystyle
O\left(|{\mathcal{B}}^{\prime\prime}|\right)+\sum_{B^{\prime}\in{\mathcal{B}}^{\prime\prime}}O(Z_{j})=O\left(|{\mathcal{B}}^{\prime\prime}|\cdot
Z_{j}\right)$ $\displaystyle\leq O\left(\frac{X_{j}}{Z_{i}\Delta_{i}}\cdot
Z_{j}\right)$ $\displaystyle\leq
O\left(\frac{X_{j}Z_{j}}{Z_{i}^{2}N^{5\epsilon}}\right)$ $\displaystyle\leq
O\left(\frac{\eta^{3\epsilon
r+1}}{N^{5\epsilon}}\cdot\frac{X_{i}}{Z_{i}}\right)\leq\frac{N^{o(1)}}{N^{2\epsilon}}\cdot\frac{X_{i}}{Z_{i}}$
$\displaystyle\leq N^{1/2-\epsilon+o(1)}$

The second inequality follows from the assumption in this special case, that,
$\Delta_{i}\geq Z_{i}N^{5\epsilon}$. The third inequality follows from Claim
4.5.6 and the fourth from our choices $r=\left\lfloor\frac{\log
N}{\log\eta}\right\rfloor$ and $\eta=O(\log\log N)$. Finally, the last
inequality follows from Observation 4.5.1 since ${\frac{X_{i}}{Z_{i}}\leq
N^{1/2-\epsilon}}$. Thus, the space used by our algorithm throughout its
execution is indeed bounded by ${N^{1/2-\epsilon+o(1)}}$.

###### Soundness guarantee.

We will show that each block $B^{\prime}\in{\mathcal{B}}^{*}$ has
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(B\cap B^{\prime})\geq Z_{j}/2$.
Indeed, a range-block $B^{\prime}$ is present in ${\mathcal{B}}^{*}$ iff the
respective execution of algorithm $\mathsf{Alg}_{1}$ from Lemma 4.2.2 with
parameter $Z=Z_{j}/2$ reported yes. But $\mathsf{Alg}_{1}$ is a deterministic
algorithm and if it reports yes,
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(B\cap B^{\prime})\geq Z_{j}/2$ must
hold.

###### Correctness guarantee.

Our goal is to show that each $(Z_{j}/2,\Delta_{i}/8)$-perfect range-block
$B^{\prime}$ of ${\mathcal{B}}^{\prime}$ is present in ${\mathcal{B}}^{*}$
with probability at least $3/4$. Consider a range-block
$B^{\prime}\in{\mathcal{B}}^{\prime}$ that is $(Z_{j}/2,\Delta_{i}/8)$-perfect
for $B$. Since $B^{\prime}$ is
$\left(\frac{Z_{j}}{2},\frac{\Delta_{i}}{8}\right)$-perfect for $B$, there is
an increasing subsequence of $B\cap B^{\prime}$ with size $\frac{Z_{j}}{2}\geq
Z_{i}$ that does not use the first
$\frac{Z_{j}}{2}\cdot\frac{\Delta_{i}}{8}=\frac{Z_{j}\Delta_{i}}{16}$ elements
of $B\cap B^{\prime}$. We denote by the event
${\mathcal{E}}^{*}_{\mathsf{bad}}$ the event that we do not sample at least
one element out of the first $Z_{j}\Delta_{i}/16$ elements of $B\cap
B^{\prime}$. We denote by ${\mathcal{E}}^{**}_{\mathsf{bad}}$ the event that
we terminate our algorithm because $|{\mathcal{B}}^{\prime\prime}|$ exceeded
$2^{10}\frac{X_{j}}{Z_{i}\Delta_{i}}$ during the execution of our algorithm.
From the correctness guarantee of Lemma 4.2.2, if the events
${\mathcal{E}}^{*}_{\mathsf{bad}}$ and ${\mathcal{E}}^{**}_{\mathsf{bad}}$
does not occur, the index of $B^{\prime}$ is present in ${\mathcal{B}}^{*}$.
We can now bound,

$\displaystyle\text{\bf
Pr}\left[{\mathcal{E}}^{*}_{\mathsf{bad}}\right]=\left(1-\frac{2^{5}}{Z_{i}\Delta_{i}}\right)^{\frac{Z_{j}\Delta_{i}}{2^{4}}}$
$\displaystyle\leq e^{-\frac{Z_{j}}{Z_{i}}}\leq\frac{1}{8}.$

Here, the last inequality follows from Item P4 of our ensemble $\Upsilon$. We
now upper bound the probability of the event
${\mathcal{E}}^{**}_{\mathsf{bad}}$. Recall that $|B|=X_{j}$ and we sample
each element independently at random with probability
$\frac{2^{5}}{Z_{i}\Delta_{i}}$. Moreover, for the event
${\mathcal{E}}^{**}_{\mathsf{bad}}$ to occur, a necessary condition is that we
sample at least $2^{10}\frac{X_{j}}{Z_{i}\Delta_{i}}$ elements of $B$. From
Chernoff bound (see, 4.2.4), this probability is at most $1/8$. We now
conclude that $\text{\bf
Pr}\left[{\mathcal{E}}^{**}_{\mathsf{bad}}\cup{\mathcal{E}}^{**}_{\mathsf{bad}}\right]\leq
1/4$ and the soundness guarantee follows. This completes the proof of
correctness of our block processing algorithm and Claim 4.5.7 now follows.
$\Box$

####  C.2.3 Proof Omitted from Section 4.5.3

#####  C.2.3.1 Proof of Claim 4.5.10.

Consider some integer $0\leq k<k^{*}$ and the corresponding pair of levels
$i_{k}$ and $i_{k+1}$. From our choice of the set ${\mathcal{I}}^{*}$ of
levels, we have $Z_{i^{\prime}}=Z_{i_{k+1}}$ for all levels
$i_{k}<i^{\prime}\leq i_{k+1}$. It is also easy to see that
$Z_{i^{\prime}}=Z_{i_{0}}$ for all levels $0\leq i^{\prime}\leq i_{0}$ and
$Z_{i^{\prime\prime}}=Z_{r^{*}}$ for all levels
$i_{k^{*}}<i^{\prime\prime}\leq r^{*}$. We also claim that
$\eta^{r^{*}}\leq\frac{N^{1/2-4\epsilon}}{\eta^{2}}$. Indeed, since
$r^{*}=\left\lfloor(1/2-4\epsilon)r\right\rfloor$ and
$r=r(N,\eta)=\left\lfloor\frac{\log N}{\log\eta}\right\rfloor$, we obtain,

$\eta^{r^{*}}=\eta^{\left\lfloor(1/2-4\epsilon)r\right\rfloor}>\frac{\eta^{\left(1/2-4\epsilon\right)r}}{\eta}>\frac{\eta^{\left(1/2-4\epsilon\right)\cdot\left(\frac{\log
N}{\log\eta}\right)}}{\eta^{2}}=\frac{N^{1/2-4\epsilon}}{\eta^{2}}.$

We now show that $Z_{r^{*}}$ is small and $Z_{0}$ is large. Combined with the
above two claims, we will be able to argue that the number of special levels
$|{\mathcal{I}}^{*}|=1+k^{*}$ is large enough. We start by showing that
$Z_{r^{*}}$ is small. From Assumption 4.5.5, for each level $0\leq
i<(1/2-\epsilon)r$, we have $\frac{X_{i}}{Z_{i}}>N^{1/2-\epsilon}$. In
particular, for the level $r^{*}$, we have
$\frac{X_{r^{*}}}{Z_{r^{*}}}>N^{1/2-\epsilon}$. In other words,

$\displaystyle
Z_{r^{*}}<\frac{X_{r^{*}}}{N^{1/2-\epsilon}}=\frac{N/\eta^{r^{*}}}{N^{1/2-\epsilon}}$
$\displaystyle=\frac{N^{1/2+\epsilon}}{\eta^{r^{*}}}<\frac{N^{1/2+\epsilon}}{N^{1/2-4\epsilon}/\eta^{2}}=\eta^{2}N^{5\epsilon}<N^{6\epsilon}.$

Here, last inequality follows since $\eta=O(\log\log N)$. Next, we show that
$Z_{0}$ is large. From Observation 4.5.1, $Z_{0}\geq N^{1/2-\epsilon}$ and for
each level $0\leq i<r$, we have $Z_{i+1}\leq Z_{i}\leq\eta Z_{i+1}$. It is now
immediate to verify that,

$\begin{split}k^{*}\geq\log_{\eta}{\left(\frac{Z_{0}}{Z_{r^{*}}}\right)}&\geq\log_{\eta}{\left(\frac{N^{1/2-\epsilon}}{N^{6\epsilon}}\right)}=\log_{\eta}{\left(N^{1/2-7\epsilon}\right)}\geq\left(\frac{1}{2}-7\epsilon\right)r.\end{split}$

Since $\epsilon\leq 1/100$, from the above inequality, we immediately obtain
that $k^{*}\geq r/3$. $\Box$

#####  C.2.3.2 Proof of Claim 4.5.14.

We proceed by induction. The base case is when $k=0$ and the claim is trivial
since $\mathsf{load}(0)=1$. Consider now some $0<k\leq k^{*}$ and the
corresponding level $i_{k}\in{\mathcal{I}}^{*}$. We assume that the induction
hypothesis holds for the level-$i_{k-1}$, or in other words,

$\mathsf{load}(i_{k-1})\leq
2^{10(k-1)}\frac{\mu_{i_{0}}}{\mu_{i_{k-1}}}\cdot\zeta(i_{0},i_{1})\cdot\ldots\cdot\zeta(i_{k-2},i_{k-1}).$

It is immediate to verify that each execution to
${\mathsf{Alg}}\mathsf{Level}{(i_{k})}$ in which $B$ participates is called by
a run of the level-$i_{k-1}$ algorithm
${\mathsf{Alg}}\mathsf{Level}{(i_{k-1})}$ in which $B(i_{k-1})$ participates.
By our induction hypothesis, there are at most $\mathsf{load}(i_{k-1})$
concurrent calls to ${\mathsf{Alg}}\mathsf{Level}{(i_{k-1})}$ in which $B^{*}$
participates. Furthermore, from Lemma 4.5.12, each such execution of
${\mathsf{Alg}}\mathsf{Level}{(i_{k-1})}$ performs at most
$2^{10}\zeta(i_{k-1},i_{k})\frac{\mu_{i_{k-1}}}{\mu_{i_{k}}}$ concurrent calls
to ${\mathsf{Alg}}\mathsf{Level}{(i_{k})}$. Thus, the maximum number of
concurrent calls to the level-$i$ algorithm
${\mathsf{Alg}}\mathsf{Level}{(i)}$ in which $B$ participates is,

$\displaystyle\mathsf{load}(B)$
$\displaystyle\leq\mathsf{load}(B(i_{k-1}))\cdot
2^{10}\zeta(i_{k-1},i_{k})\frac{\mu_{i_{k-1}}}{\mu_{i_{k}}}$
$\displaystyle\leq 2^{10(k-1)}\frac{\mu_{i_{0}}}{\mu_{i_{k-1}}}\cdot
2^{10}\frac{\mu_{i_{k-1}}}{\mu_{i_{k}}}\cdot\zeta(i_{0},i_{1})\cdot\ldots\cdot\zeta(i_{k-1},i_{k})$
$\displaystyle=2^{10k}\frac{\mu_{i_{0}}}{\mu_{i_{k}}}\cdot\zeta(i_{0},i_{1})\cdot\ldots\cdot\zeta(i_{k-1},i_{k}).$

$\Box$

#####  C.2.3.3 Proof of Claim 4.5.15.

For convenience, for each $0\leq k<k^{*}$, we let
$x_{k}:=e^{\zeta(i_{k},i_{k+1})}=\eta^{2\left(i_{k+1}-i_{k}\right)}\cdot\psi_{i_{k+1}}$.
Thus, for each $0\leq k<k^{*}$ we have $\zeta(i_{k},i_{k+1})=\ln{x_{k}}$. From
4.2.6, we can now bound,

$\displaystyle\left(\zeta(i_{0},i_{1})\cdot\ldots\cdot\zeta(i_{k^{*}-1},i_{k^{*}})\right)^{1/k^{*}}$
$\displaystyle=\left(\Pi_{0\leq k<k^{*}}\ln{x_{k}}\right)^{1/k^{*}}$
$\displaystyle\leq\ln{\left(\left(\Pi_{0\leq
k<k^{*}}x_{k}\right)^{1/k^{*}}\right)}$
$\displaystyle\leq\ln{\left(\eta^{\frac{2\left(i_{k^{*}}-i_{0}\right)}{k^{*}}}\cdot
N^{\frac{1}{k^{*}}}\right)}$
$\displaystyle\leq\ln{\left(\eta^{\frac{2r}{k^{*}}}\cdot
N^{\frac{1}{k^{*}}}\right)}\leq\ln{\left(N^{\frac{3}{k^{*}}}\right)}$
$\displaystyle\leq\frac{3}{k^{*}}\log N\leq 9\log\eta.$

Here, the second inequality holds since $\Pi_{1\leq i<r}\Psi_{i}\leq N$ and
the last inequality follows from Claim 4.5.10 and fact that
$r=\left\lfloor\frac{\log N}{\log\eta}\right\rfloor$. We now conclude that,

$\displaystyle\zeta(i_{0},i_{1})\cdot\ldots\cdot\zeta(i_{k^{*}-1},i_{k^{*}})\leq\left(9\log\eta\right)^{k^{*}}$
$\displaystyle\leq\left(9\log\eta\right)^{r}\leq
N^{\frac{\log{(9\log\eta)}}{\log\eta}}\leq N^{o(1)}.$

$\Box$

#####  C.2.3.4 Proof of Observation 4.5.16.

Since $Z_{0}=\ldots=Z_{i_{0}}$, it is immediate to verify that
${\mathcal{B}}^{i_{0}}_{\Psi^{\prime}}(H^{*})=\left\\{H^{*}\right\\}$, or in
other words, there is a unique level-$i_{0}$ range-block $H^{*}$. For each
level-$i_{0}$ stream-block $B\in{\mathcal{B}}^{i_{0}}_{\Psi}(S)$, we run
$2^{6}\left(\zeta(0,i_{0})+1\right)$ parallel executions of the algorithm
${\mathsf{Alg}}\mathsf{Level}{(i_{0})}$ with input level-$i_{0}$ pair
$(B,H^{*})$ and the subblock $B$ of $B$. We report yes iff at least
$2^{5}\left(\zeta(0,i_{0})+1\right)$ of these executions report yes. This
completes the description of $\mathsf{Alg}_{\mathsf{simp}}$. It is immediate
to verify that the space complexity of $\mathsf{Alg}_{\mathsf{simp}}$,
excluding the space required by the calls to
${\mathsf{Alg}}\mathsf{Level}{(i_{0})}$, is at most
$O\left(1+\zeta(0,i_{0})\right)=N^{o(1)}$. We now analyze its correctness.

###### Completeness.

Assume that $S$ is a Yes-Instance. Then, there is the level-$i_{0}$ yes-block
$B\in{\mathcal{B}}^{i_{0}}_{\Psi}(S)$, for which each corresponding execution
of ${\mathsf{Alg}}\mathsf{Level}{(i_{0})}$ returns yes with probability at
least $3/4$. From Chernoff bound, the probability that more than
$2^{5}\left(\zeta(0,i_{0})+1\right)$ executions of
${\mathsf{Alg}}\mathsf{Level}{(i_{0})}$ report no is at most
$e^{2(\zeta(0,i_{0})+1)}\leq\frac{1}{e^{2}}$. We now conclude that we report
yes with probability at least $1-\frac{1}{e^{2}}\geq\frac{3}{4}$.

###### Soundness.

Assume that
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)<Z_{0}/\alpha^{\prime}_{0}$.
Consider a level-$i_{0}$ stream-block $B\in{\mathcal{B}}^{i_{0}}_{\Psi}(S)$.
Since
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(B)\leq\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)<Z_{0}/\alpha^{\prime}_{0}$,
each run of ${\mathsf{Alg}}\mathsf{Level}{(i_{0})}$ in which $B$ participates
returns no with probability at least $3/4$. The probability that at least
$2^{5}\left(\zeta(0,i_{0})+1\right)$ executions of
${\mathsf{Alg}}\mathsf{Level}{(i_{0})}$ report yes is at most
$e^{-2-\zeta(0,i_{0})}\leq\frac{e^{-2}}{\eta^{i_{0}}}$. The soundness now
follows by union bound over at most $\eta^{i_{0}}$ level-$i_{0}$ stream
blocks. $\Box$

#####  C.2.3.5 Proof of Claim 4.5.18.

Recall that for each element $e\in{\mathcal{S}}$, we have a level-$j$ pair
$(\hat{B}(e),\hat{B}^{\prime}(e))$ with the following guarantees: (i)
$(\hat{B}(e),\hat{B}^{\prime}(e))$ is a level-$j$ descendant-pair of
$(B^{*},B^{*^{\prime}})$; (ii) out of $\left\lfloor 32\zeta(i,j)\right\rfloor$
calls to ${\mathsf{Alg}}\mathsf{Level}{(j)}$ in which the pair
$(\hat{B}(e),\hat{B}^{\prime}(e))$ participates, at least $16\zeta(i,j)$ of
them returned yes.

######  Claim C.2.1.

Consider an element $e\in{\mathcal{E}}$ and the corresponding level-$j$ pair
$(\hat{B}(e),\hat{B}^{\prime}(e))$. Then with probability at least
$1-\frac{1}{10|{\mathcal{B}}||{\mathcal{B}}^{\prime}|}$,
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(\hat{B}(e)\cap\hat{B}^{\prime}(e))\geq\frac{Z_{j}}{\alpha^{\prime}_{j}}$.

###### Proof.

Recall that we perform $\left\lfloor 32\zeta(i,j)\right\rfloor$ calls to
${\mathsf{Alg}}\mathsf{Level}{(j)}$, in which the level-$j$ pair
$(\hat{B}(e),\hat{B}^{\prime}(e))$ participates. Consider one such execution
of ${\mathsf{Alg}}\mathsf{Level}{(j)}$. From the correctness guarantee of
${\mathsf{Alg}}\mathsf{Level}{(j)}$, if it returns yes, with probability at
least $3/4$, we have
${\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(\hat{B}(e)\cap\hat{B}^{\prime}(e))\geq\frac{Z_{j}}{\alpha^{\prime}_{j}}}$.
From Chernoff bound, the probability that at least $16\zeta(i,j)$ such calls
return yes even though
${\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(\hat{B}(e)\cap\hat{B}^{\prime}(e))<\frac{Z_{j}}{\alpha^{\prime}_{j}}}$
is at most
$e^{-\zeta(i,j)}\leq\frac{1}{\eta^{2}|{\mathcal{B}}||{\mathcal{B}}^{\prime}|}\leq\frac{1}{10|{\mathcal{B}}||{\mathcal{B}}^{\prime}|}$.

Since there are only at most $|{\mathcal{B}}|\cdot|{\mathcal{B}}^{\prime}|$
elements in ${\mathcal{S}}$, with probability at least $0.9$, for each
$e\in{\mathcal{S}}$ the corresponding level-$j$ pair
$(\hat{B}(e),\hat{B}^{\prime}(e))$ has
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(\hat{B}(e)\cap\hat{B}^{\prime}(e))\geq\frac{Z_{j}}{\alpha^{\prime}_{j}}$.
Assume from now on that this indeed holds. We are now ready to complete the
proof of Claim 4.5.18.

Consider an increasing subsequence
${\mathcal{S}}^{\prime}=(e_{1},\ldots,e_{\ell})$ of ${\mathcal{S}}$ with
length $\ell$. It is immediate to verify that the corresponding level-$j$
stream-blocks $\hat{B}(e_{1}),\ldots,\hat{B}(e_{\ell})$ are unique and appear
in this order. Similarly, the corresponding level-$j$ stream-blocks
$\hat{B}(e_{1}),\ldots,\hat{B}(e_{\ell})$ are unique and appear in this order.
We now conclude that there is an increasing subsequence of $B^{*}\cap
B^{*^{\prime}}$ in which each such level-$j$ pair contributes at least
$\frac{Z_{j}}{\alpha^{\prime}_{j}}$ elements. Thus,
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(B^{*}\cap
B^{*^{\prime}})\geq\ell\cdot\frac{Z_{j}}{\alpha^{\prime}_{j}}$ and the claim
follows. $\Box$

#####  C.2.3.6 Proof of Claim 4.5.19.

Let ${\mathcal{P}}$ be the set of all level-$j$ descendant yes-pairs
$(B,B^{\prime})$ of $(B^{*},B^{*^{\prime}})$ such $B$ is a subblock of
$B^{**}$. We first show that $|{\mathcal{P}}|$ is large enough. We will then
show that each such pair $(B,B^{\prime})\in{\mathcal{P}}$ is a happy pair
independently with good probability, and then complete the proof of Claim
4.5.19 with a simple application of Chernoff bound.

######  Claim C.2.2.

$|{\mathcal{P}}|\geq\frac{Z_{i}}{2Z_{j}}$.

###### Proof.

From our assumption, $|B^{**}\cap S^{*}|\geq\frac{Z_{i}}{2}$. Since each
level-$j$ yes-block contributes exactly $Z_{j}$ elements to $S^{*}$, there are
at least $\frac{Z_{i}}{2Z_{j}}$ level-$j$ yes-blocks that are subblocks of
$B^{**}$.

######  Claim C.2.3.

Each pair $(B,B^{\prime})\in{\mathcal{P}}$ is a happy pair independently with
probability at least $0.9$.

###### Proof.

Fix some pair $(B,B^{\prime})\in{\mathcal{P}}$. Notice that we sample elements
of $B\cap B^{\prime}$ independently at random with probability
$p_{j}=\frac{2^{6}}{Z_{j}\mu_{j}}$ each. Consider the level $j^{\prime}=j+1$
of ${\mathcal{I}}^{*}$ and a level-$j^{\prime}$ descendant stream-block
$\hat{B}$ of $B$. Since $S^{*}$ is an $\Upsilon$-canonical subsequence, if
$\hat{B}$ is a yes-block, it must contribute at least $|\hat{B}\cap
B^{\prime}|\geq Z_{j^{\prime}}\mu_{j^{\prime}-1}=Z_{j^{\prime}}\mu_{j}$
elements to $B^{\prime}$. Moreover, a level-$j^{\prime}$ stream-block
contributes elements to $S^{*}$ only if it is a yes-block, and if it
contributes elements, it contributes exactly $Z_{j^{\prime}}$ of them. Thus,
before processing the $\left(\frac{Z_{j}}{2}+1\right)^{th}$ element of $S^{*}$
in $B$, we must have encountered at least $\frac{Z_{j}}{2Z_{j^{\prime}}}$
level-$j^{\prime}$ yes-blocks, which in turn, contain at least
$\frac{Z_{j}}{2Z_{j^{\prime}}}\cdot
Z_{j^{\prime}}\mu_{j}=\frac{Z_{j}\mu_{j}}{2}$ elements of $B\cap B^{\prime}$.
We denote by ${\mathcal{E}}_{1}$ the event that we sample some element of
$B\cap B^{\prime}$ before processing the $\left(\frac{Z_{j}}{2}+1\right)^{th}$
element of $S^{*}$ in $B$. From the above discussion,

$\text{\bf Pr}\left[{\mathcal{E}}_{1}\right]\geq
1-\left(1-\frac{2^{6}}{Z_{j}\mu_{j}}\right)^{\frac{1}{2}Z_{j}\mu_{j}}\geq
1-e^{-2^{4}}\geq 0.99.$

We assume from now on that this event ${\mathcal{E}}_{1}$ indeed occurs. Let
$a_{t^{\prime}}$ be the element such that we call $\left\lfloor
32\zeta(i,j)\right\rfloor$ parallel instances of the level-$j$ algorithm
${\mathsf{Alg}}\mathsf{Level}{(j)}$ with input level-$j$ pair $(B,B^{\prime})$
and the subblock $B_{>t^{\prime}}$ of $B$. We denote by ${\mathcal{E}}_{2}$
the event that at least $16\zeta(i,j)$ such executions of
${\mathsf{Alg}}\mathsf{Level}{(j)}$ return yes. Since the event
${\mathcal{E}}_{1}$ does occur, $B_{>t^{\prime}}\cap B^{\prime}$ contains at
least $Z_{j}/2$ elements of $S^{*}$. Furthermore, each such execution of
${\mathsf{Alg}}\mathsf{Level}{(j)}$ reports in affirmative with probability at
least $3/4$. From Chernoff bound, it is immediate to verify that $\text{\bf
Pr}\left[{\mathcal{E}}_{2}\>|\>{\mathcal{E}}_{1}\right]\geq 0.99$. We assume
from now on that the events ${\mathcal{E}}_{1}$ and ${\mathcal{E}}_{2}$ indeed
occur.

We denote by ${\mathcal{E}}_{3}$ the event that we sample at most
$\frac{2^{10}\mu_{i}}{\mu_{j}}$ elements of $B\cap B^{*}$. We first claim that
$B^{*^{\prime}}$ is in fact, the level-$(j-1)$ ancestor block of $B^{\prime}$.
Indeed, for each level $i<i^{\prime}<j$, we have $\psi_{i^{\prime}}=1$ and
hence, the partitions
${\mathcal{B}}^{i}_{\Psi^{\prime}}(H^{*})=\ldots={\mathcal{B}}^{j-1}_{\Psi^{\prime}}(H^{*})$
of the range $H^{*}$ are identical. Thus, $B^{*^{\prime}}$ is the
level-$(j-1)$ ancestor block of $B^{\prime}$. Since $S^{*}$ is an
$\Upsilon$-canonical sequence, and $B$ is a level-$j$ yes-block,
$Z_{j}\mu_{j-1}\leq|B\cap B^{*^{\prime}}|<2Z_{j}\mu_{j-1}$. Recall that we
sample the elements of $B\cap B^{*^{\prime}}$ independently with probability
$\frac{2^{6}}{Z_{j}\mu_{j}}$ each. Using Chernoff bound, it is now immediate
to verify that $\text{\bf
Pr}\left[{\mathcal{E}}_{3}\>|\>{\mathcal{E}}_{1}\text{ and
}{\mathcal{E}}_{2}\right]>0.99$. From union bound, $\text{\bf
Pr}\left[{\mathcal{E}}_{1}\text{ and }{\mathcal{E}}_{2}\text{ and
}{\mathcal{E}}_{3}\right]\geq 0.97$, and we conclude that $(B,B^{\prime})$ is
a happy pair with probability at least $0.97$.

Using Claims C.2.2 and C.2.3 and applying Chernoff bound, with probability at
least $0.9$, there are at least $\frac{Z_{i}}{8Z_{j}}$ happy pairs. This
completes the proof of Claim 4.5.19. $\Box$

####  C.2.4 Proofs Omitted from Section 4.5.4

#####  C.2.4.1 Proof of Claim 4.5.21.

We first consider the case where $w_{i_{k^{\prime}}}<100$. In this case, we
must have $k^{\prime}=k^{*}$ and from Claim 4.5.10, $k^{*}\geq r/3$. Assume
from now on that $k^{\prime}<k^{*}$ and $w_{i_{k^{\prime}}}\geq 100$. We
consider the execution of our algorithm on level $i_{k^{\prime}}$. Since it is
the last level that we process, we must have had
$\mathsf{land}(k^{\prime})=\mathsf{cover}(k^{\prime},\mathsf{jump}(k^{\prime}))=k^{*}$
and hence, $\mathsf{jump}(k^{\prime})+\left\lfloor
0.3\log_{\eta}{\left(\frac{\mu_{i_{k^{\prime}}}}{\mu_{i_{\mathsf{jump}(k^{\prime})}}}\right)}\right\rfloor\geq
k^{*}$. But $\mu_{i_{\mathsf{jump}(k^{\prime})}}\geq 1$ and we obtain

$\mathsf{jump}(k^{\prime})\geq
k^{*}-0.3\log_{\eta}{\left(\mu_{i_{k^{\prime}}}\right)}$ (C.3)

We will use the following claim that we prove after completing the proof of
Claim 4.5.21 assuming it.

######  Claim C.2.4.

$\mathsf{jump}(k^{\prime})\leq
k^{\prime}+\frac{31}{100}\cdot\log_{\eta}{\left(\mu_{i_{k^{\prime}}}\right)}$.

From Equations C.3 and C.2.4,
$k^{\prime}+\frac{31}{100}\cdot\log_{\eta}{\left(\mu_{i_{k^{\prime}}}\right)}\geq
k^{*}-\frac{3}{10}\log_{\eta}{\left(\mu_{i_{k^{\prime}}}\right)}$, or
equivalently,

$\displaystyle k^{\prime}$ $\displaystyle\geq
k^{*}-\frac{61}{100}\log_{\eta}{\left(\mu_{i_{k^{\prime}}}\right)}$
$\displaystyle\geq\left(\frac{1}{2}-7\epsilon\right)r-\frac{61}{100}\left(\frac{1}{2}+\epsilon\right)r$
$\displaystyle>\left(\frac{39}{200}-8\epsilon\right)r>\frac{r}{6}.$

Here, the second inequality follows from Claim 4.5.10 and the fact that
$\mu_{i_{k^{\prime}}}\leq\mu_{0}\leq\Delta_{0}\leq N^{1/2+\epsilon}$ (see,
Observation 4.5.1). The last inequality holds for all $\epsilon<1/1000$. This
completes the proof of LABEL:{clm:_ncm-i-star-sep} assuming LABEL:{clm:_ncm-k-
jump-start-small-new-new} that we prove next.

Proof of Claim C.2.4. Recall that $k^{\prime}<\mathsf{jump}(k^{\prime})\leq
k^{*}$ is the smallest index such that
$\log_{\eta}{\left(\frac{\mu_{i_{k^{\prime}}}}{\mu_{\ell}}\right)}\leq
100\log_{\eta}{\left(\frac{\mu_{i_{k^{\prime}}}}{\mu_{j}}\right)}$, where
$j=i_{\mathsf{jump}(k^{\prime})}$, $\ell=i_{\mathsf{land}(k^{\prime})}$, and
$\mathsf{land}(k^{\prime})=\mathsf{cover}(k^{\prime},\mathsf{jump}(k^{\prime}))$.
We consider a sequence $\left(p(0),\ldots,\right)$ of integers with values in
the range $\left\\{k^{\prime}+1,\ldots,k^{*}\right\\}$ that is obtained as
follows. We set $p(0)=1+k^{\prime}$ and for each subsequent $u>0$, we let
$p({u})=\min{\left(\mathsf{cover}(k^{\prime},p(u-1)),\mathsf{jump}(k^{\prime})\right)}$.
It is immediate to verify that this sequence is non-decreasing. This sequence
naturally corresponds to a sequence $\left(q(0),\ldots,\right)$ of levels of
${\mathcal{I}}^{*}$, where for each $u\geq 0$, we let $q(u):=i_{p(u)}$.

######  Observation C.2.5.

For each $u\geq 0$ such that $p(u+1)<\mathsf{jump}(k^{\prime})$,
$\log_{\eta}{\left(\frac{\mu_{i_{k^{\prime}}}}{\mu_{q(u+1)}}\right)}>100\log_{\eta}{\left(\frac{\mu_{i_{k^{\prime}}}}{\mu_{q(u)}}\right)}$.

###### Proof.

Fix an integer $u\geq 0$ such that
$p(u+1)=\min{\left(\mathsf{cover}(k^{\prime},p(u)),\mathsf{jump}(k^{\prime})\right)}<\mathsf{jump}(k^{\prime})$,
and hence, $p(u+1)=\mathsf{cover}(k^{\prime},p(u))$. But $p(u)\leq
p(u+1)<\mathsf{jump}(k^{\prime})$, and we must have had
$\log_{\eta}{\left(\frac{\mu_{i_{k^{\prime}}}}{\mu_{\ell}}\right)}>100\log_{\eta}{\left(\frac{\mu_{i_{k^{\prime}}}}{\mu_{q(u)}}\right)}$,
where $\ell=i_{\mathsf{cover}(k^{\prime},p(u))}=i_{p(u+1)}=q(u+1)$.

Let $v\geq 0$ be the smallest integer such that
$p(v)=\mathsf{jump}(k^{\prime})$. We first claim that such an integer $v$
exists. Indeed, assume for contradiction that for all $u\geq 0$ we have
$p(u)<\mathsf{jump}(k^{\prime})\leq k^{*}$. But then,

$\displaystyle p(u+1)$
$\displaystyle=\min{\left(\mathsf{cover}(k^{\prime},p(u)),\mathsf{jump}(k^{\prime})\right)}=\mathsf{cover}(k^{\prime},p(u))$
$\displaystyle=\min{\left(p(u)+\left\lfloor
0.3\log_{\eta}{\left(\frac{\mu_{i_{k^{\prime}}}}{\mu_{q(u)}}\right)}\right\rfloor,k^{*}\right)}$
$\displaystyle=p(u)+\left\lfloor
0.3\log_{\eta}{\left(\frac{\mu_{i_{k^{\prime}}}}{\mu_{q(u)}}\right)}\right\rfloor$
$\displaystyle\geq p(u)+\left\lfloor 0.3w_{i_{k^{\prime}}}\right\rfloor$
$\displaystyle>p(u).$

Here, the equalities follow from that fact that $p(u)\leq
p(u+1)<\mathsf{jump}(k^{\prime})\leq k^{*}$. The first inequality follows
since $p(u)\geq 1+k^{\prime}$ and the last inequality follows from the fact
that $w_{i_{k^{\prime}}}\geq 100$. Thus, the sequence $(p(0),\ldots,)$ is
simultaneously strictly increasing in perpetuity and also bounded by
$\mathsf{jump}(k^{\prime})$, a contradiction. We fix the smallest integer $v$
such that ${p(v)=\mathsf{jump}(k^{\prime})}$.

######  Observation C.2.6.

For each $0\leq u<v$, $p(u)\leq
k^{\prime}+\frac{1}{100}\cdot\log_{\eta}{\left(\frac{\mu_{i_{k^{\prime}}}}{\mu_{q(u)}}\right)}$.

###### Proof.

We proceed by induction. The base case is when $u=0$. In this case,
$p(0)=k^{\prime}+1$ and $q(0)=i_{p(0)}=i_{k^{\prime}+1}$, implying,

$p(0)=k^{\prime}+1\leq k^{\prime}+\frac{1}{100}\cdot
w_{i_{k^{\prime}}}=k^{\prime}+\frac{1}{100}\cdot\log_{\eta}{\left(\frac{\mu_{i_{k^{\prime}}}}{\mu_{q(0)}}\right)},$

and the assertion follows. Here, the inequality follows since
$w_{i_{k^{\prime}}}\geq 100$. Assume now that the induction hypothesis holds
for $0\leq u<v-1$, and we show it for $u+1$. Recall that $v$ is the smallest
integer such that ${p(v)=\mathsf{jump}(k^{\prime})}$. Thus,
$p(u+1)<\mathsf{jump}(k^{\prime})$ and hence,

$\displaystyle p(u+1)$ $\displaystyle=\mathsf{cover}(k^{\prime},p(u))$
$\displaystyle\leq
p(u)+{\frac{3}{10}\cdot\log_{\eta}{\left(\frac{\mu_{i_{k^{\prime}}}}{\mu_{q(u)}}\right)}}$
$\displaystyle\leq
k^{\prime}+\frac{1}{100}\cdot\log_{\eta}{\left(\frac{\mu_{i_{k^{\prime}}}}{\mu_{q(u)}}\right)}+{\frac{3}{10}\cdot\log_{\eta}{\left(\frac{\mu_{i_{k^{\prime}}}}{\mu_{q(u)}}\right)}}$
$\displaystyle=k^{\prime}+\frac{31}{100}\cdot\log_{\eta}{\left(\frac{\mu_{i_{k^{\prime}}}}{\mu_{q(u)}}\right)}$
$\displaystyle\leq
k^{\prime}+\frac{31}{10000}\cdot\log_{\eta}{\left(\frac{\mu_{i_{k^{\prime}}}}{\mu_{q(u+1)}}\right)}<k^{\prime}+\frac{1}{100}\cdot\log_{\eta}{\left(\frac{\mu_{i_{k^{\prime}}}}{\mu_{q(u+1)}}\right)}.$

Here, the second inequality follows from the induction hypothesis and the
second-last inequality follows from Observation C.2.5.

If $v=0$, we have
$\mathsf{jump}(k^{\prime})=p(0)=k^{\prime}+1<k^{\prime}+\frac{31}{100}\cdot\log_{\eta}{\left(\mu_{i_{k^{\prime}}}\right)}$
and there is nothing to show. Thus, assume from now on that $v>0$. Recall that
$p(v)=\mathsf{jump}(k^{\prime})$ and hence,
$\mathsf{cover}(k^{\prime},p(v-1))\geq\mathsf{jump}(k^{\prime})$. In other
words,

$\displaystyle\mathsf{jump}(k^{\prime})\leq\mathsf{cover}(k^{\prime},p(v-1))$
$\displaystyle\leq p(v-1)+\left\lfloor
0.3\log_{\eta}{\left(\frac{\mu_{i_{k^{\prime}}}}{\mu_{q(v-1)}}\right)}\right\rfloor$
$\displaystyle\leq
k^{\prime}+\frac{1}{100}\log_{\eta}{\left(\frac{\mu_{i_{k^{\prime}}}}{\mu_{q(v-1)}}\right)}+\frac{3}{10}\log_{\eta}{\left(\frac{\mu_{i_{k^{\prime}}}}{\mu_{q(v-1)}}\right)}$
$\displaystyle=k^{\prime}+\frac{31}{100}\log_{\eta}{\left(\frac{\mu_{i_{k^{\prime}}}}{\mu_{q(v-1)}}\right)}\leq
k^{\prime}+\frac{31}{100}\log_{\eta}{\left(\mu_{i_{k^{\prime}}}\right)}.$

Here, the second inequality follows from Observation C.2.6. This completes the
proof of Claim C.2.4. $\Box$

This also completes the proof of LABEL:{clm:_ncm-i-star-sep}. $\Box$

#####  C.2.4.2 Proof of Claim 4.5.22.

For convenience, we let $i^{\prime}:=i_{k^{\prime}}$. Notice that,

$\displaystyle
w_{{\mathcal{I}}^{\prime}}=w_{\left\\{i_{0},\ldots,i_{k^{\prime}-1}\right\\}}=\sum_{0\leq
k<k^{\prime}}w_{i_{k}}$ $\displaystyle=\sum_{0\leq
k<k^{\prime}}\log_{\eta}{\left(\frac{\mu_{i_{k}}}{\mu_{i_{k+1}}}\right)}=\log_{\eta}{\left(\frac{\mu_{i_{0}}}{\mu_{i^{\prime}}}\right)}.$

First, we claim that $\mu_{i_{0}}\geq N^{1/2-\epsilon}$. Recall that $i_{0}$
is the smallest level $i$ such that $Z_{i}>Z_{i+1}$, and hence,
$Z_{i_{0}}=Z_{0}$. But then $\mu_{i_{0}}=\frac{X_{i_{0}+1}}{Z_{i_{0}+1}}\geq
N^{1/2-\epsilon}$. Here, the equality follows since
$\psi_{0}=\ldots=\psi_{i_{0}}=1$ and the inequality follows from Assumption
4.5.5.

Next, we claim that $3\epsilon r\leq i^{\prime}<(1/2-\epsilon)r$. Indeed,
$i^{\prime}\leq i_{k^{*}}\leq{r^{*}}<(1/2-\epsilon)r$. On the other hand, from
Claim 4.5.21, $i^{\prime}\geq r/6\geq 3\epsilon r$, for all $\epsilon\leq
1/100$.

We now claim that
$\mu_{i^{\prime}}<\frac{N^{1/2+6\epsilon}}{\eta^{i^{\prime}}}$. Indeed, from
Assumption 4.5.5 we get,
$Z_{i^{\prime}}<\frac{X_{i^{\prime}}}{N^{1/2-\epsilon}}=\frac{N^{1/2+\epsilon}}{\eta^{i^{\prime}}}$.
On the other hand, from Assumption 4.5.9,
$Z_{i^{\prime}}>\Delta_{i^{\prime}}/N^{5\epsilon}$, implying
$\Delta_{i^{\prime}}<Z_{i^{\prime}}N^{5\epsilon}<\frac{N^{1/2+6\epsilon}}{\eta^{i^{\prime}}}$.
From Observation 4.5.1, we now obtain
$\mu_{i^{\prime}}\leq\Delta_{i^{\prime}}<\frac{N^{1/2+6\epsilon}}{\eta^{i^{\prime}}}$
as claimed. We now conclude,

$\displaystyle
w_{{\mathcal{I}}^{\prime}}=\log_{\eta}{\left(\frac{\mu_{i_{0}}}{\mu_{i^{\prime}}}\right)}\geq\log_{\eta}{\left(\frac{{\eta^{i^{\prime}}}}{N^{7\epsilon}}\right)}=i^{\prime}-\log_{\eta}{\left(N^{7\epsilon}\right)}$
$\displaystyle>i^{\prime}-8\epsilon r$ $\displaystyle\geq k^{\prime}-8\epsilon
r>k^{\prime}-\frac{r}{1000},$

for all $\epsilon<1/10^{4}$. Here, the second inequality follows since
$r=\left\lfloor\frac{\log N}{\log\eta}\right\rfloor$ and $\eta=o(\log N)$ is
small enough while the third inequality follows from Claim 4.5.21. This
completes the proof of Claim 4.5.22. $\Box$

#####  C.2.4.3 Proof of Observation 4.5.27.

Consider some bad jumpable tuple $\tau(k)\in{\mathcal{J}}^{\prime}$ and let
$\tau(k)=(i_{k},j,\ell)$, where $j=i_{\mathsf{jump}}(k)$ and
$\ell=i_{\mathsf{land}(k)}$, and
$\mathsf{land}(k)={\mathsf{cover}(k,\mathsf{jump}(k))}$. We let
$\hat{\mathcal{I}}(\tau(k)):=\left\\{i_{\mathsf{jump}(k)},\ldots,i_{\mathsf{land}(k)-1}\right\\}$
and think of $\tau(k)$ as being responsible for $\hat{\mathcal{I}}(\tau)$.
Note that,

$\begin{split}|\hat{\mathcal{I}}(\tau(k))|=\mathsf{land}(k)-\mathsf{jump}(k)&=\mathsf{cover}(k,\mathsf{jump}(k))-\mathsf{jump}(k)\\\
&=\left\lfloor 0.3w_{{\mathcal{I}}(\tau(k))}\right\rfloor\geq
0.29w_{{\mathcal{I}}(\tau(k))}.\end{split}$ (C.4)

Here, the last equality follows since we chose to add the jumpable tuple
$\tau(k)$ to ${\mathcal{J}}$, we must have had
$\mathsf{cover}(k,\mathsf{jump}(k))<k^{*}$ implying that
$\mathsf{cover}(k,\mathsf{jump}(k))=\mathsf{jump}(k)+\left\lfloor
0.3w_{{\mathcal{I}}(\tau(k))}\right\rfloor$. The last inequality follows since
$w_{{\mathcal{I}}(\tau(k))}\geq 100$. We let
$\hat{\mathcal{I}}({\mathcal{J}}^{\prime})=\bigcup_{\tau\in{\mathcal{J}}^{\prime}}\hat{\mathcal{I}}(\tau)$
be the set of all levels for which the jumpable tuples of
${\mathcal{J}}^{\prime}$ are responsible. Since the respective sets
$\hat{\mathcal{I}}(\tau)$ are disjoint for distinct jumpable tuples of
${\mathcal{J}}$, we have

$\begin{split}|\hat{\mathcal{I}}({\mathcal{J}}^{\prime})|=\sum_{\tau\in{\mathcal{J}}^{\prime}}|\hat{\mathcal{I}}(\tau)|\geq\sum_{\tau\in{\mathcal{J}}^{\prime}}0.29w_{{\mathcal{I}}(\tau)}&=0.29w_{{\mathcal{I}}({\mathcal{J}}^{\prime})}.\end{split}$
(C.5)

Consider now a bad jumpable tuple $\tau(k)=(i_{k},j,\ell)$ of
${\mathcal{J}}^{\prime}$. Since it is a bad jumpable tuple, we have
$\frac{Z_{j}}{Z_{\ell}}<\eta^{0.2w_{{\mathcal{I}}(\tau(k))}}$, and hence,
$\prod_{i^{\prime}\in\hat{\mathcal{I}}(\tau(k))}\frac{Z_{i^{\prime}}}{Z_{i^{\prime}+1}}=\frac{Z_{j}}{Z_{\ell}}<\eta^{0.2w_{{\mathcal{I}}(\tau(k))}}$.
Next, recall that for each level $i_{k}\in{\mathcal{I}}^{*}$ with $0\leq
k<k^{*}$, we have $\frac{Z_{i_{k}}}{Z_{i_{k+1}}}\leq\eta$. Using these two
facts, we bound $\frac{Z_{0}}{Z_{i_{k^{*}}}}$ by writing it as a telescopic
product:

$\displaystyle\frac{Z_{0}}{Z_{i_{k^{*}}}}=\frac{Z_{i_{0}}}{Z_{i_{k^{*}}}}=\prod_{0\leq
k<k^{*}}\frac{Z_{i_{k}}}{Z_{i_{k+1}}}$
$\displaystyle=\left(\prod_{\begin{subarray}{c}0\leq k<k^{*}\\\ \text{ and
}\\\
i_{k}\not\in\hat{\mathcal{I}}({\mathcal{J}}^{\prime})\end{subarray}}\frac{Z_{i_{k}}}{Z_{i_{k+1}}}\right)\cdot\left(\prod_{\tau\in{\mathcal{J}}^{\prime}}\left(\prod_{i\in\hat{\mathcal{I}}(\tau)}\frac{Z_{i}}{Z_{i+1}}\right)\right)$
$\displaystyle<\left(\eta^{k^{*}-|\hat{\mathcal{I}}({\mathcal{J}}^{\prime})|}\right)\cdot\left(\prod_{\tau\in{\mathcal{J}}^{\prime}}\eta^{0.2w_{{\mathcal{I}}(\tau)}}\right)$
$\displaystyle\leq\eta^{k^{*}-0.29w_{{\mathcal{I}}({\mathcal{J}}^{\prime})}}\cdot\eta^{0.2w_{{\mathcal{I}}({\mathcal{J}}^{\prime})}}=\eta^{k^{*}-0.09w_{{\mathcal{I}}({\mathcal{J}}^{\prime})}}.$

Here, the inequalities follow from Equations C.4 and C.5. This completes the
proof of Observation 4.5.27. $\Box$

####  C.2.5 Proofs Omitted from Sections 4.5.5, 4.5.6, and 4.5.7

#####  C.2.5.1 Proof of Claim 4.5.32.

We will first show that $\zeta(i_{k_{1}},i_{k_{2}})=\sum_{k_{1}\leq
k^{\prime}<k_{2}}\zeta(i_{k^{\prime}},i_{k^{\prime}+1})$. Indeed,

$\displaystyle e^{\zeta(i_{k_{1}},i_{k_{2}})}$
$\displaystyle=\eta^{2(i_{k_{2}}-i_{k_{1}})}\cdot\psi_{i_{k_{1}+1}}\cdot\ldots\cdot\psi_{i_{k_{2}}}$
$\displaystyle=\prod_{k_{1}\leq
k^{\prime}<k_{2}}\eta^{2(i_{k^{\prime}+1}-i_{k^{\prime}})}\cdot\psi_{i_{k^{\prime}+1}}$
$\displaystyle=\prod_{k_{1}\leq
k^{\prime}<k_{2}}e^{\zeta(i_{k^{\prime}},i_{k^{\prime}+1})}$
$\displaystyle=e^{\sum_{k_{1}\leq
k^{\prime}<k_{2}}\left(\zeta(i_{k^{\prime}},i_{k^{\prime}+1})\right)}.$

The claim now follows by noting that for each $0\leq k<k^{*}$, we have
$\zeta(i_{k},i_{k+1})\geq\ln{\eta}>2$. $\Box$

#####  C.2.5.2 Proof of Claim 4.5.33.

We proceed by induction. The base case is when $k=0$ and the assertion is
trivial since we execute level-$i_{0}$ algorithm
${\mathsf{Alg}}\mathsf{Jump}{(i_{0})}$ only once. Consider now some integer
$0<k\leq k^{*}$ and the corresponding level $i_{k}\in{\mathcal{I}}^{*}$. We
assume that the induction hypothesis holds for level $i_{k-1}$. We fix a
level-$i_{k}$ stream-block $B$ and analyze $\mathsf{load}(B)$.

We first consider the case where there is no jumpable tuple
$\tau=(i_{k^{\prime}},i_{k^{\prime\prime}},i_{k^{\prime\prime\prime}})$ in
${\mathcal{J}}^{*}$ with
$k\in\left\\{k^{\prime\prime},k^{\prime\prime\prime}\right\\}$. Let $B^{*}$ be
the unique level-$(i_{k-1})$ ancestor-block of $B$. It is immediate to verify
that each execution to ${\mathsf{Alg}}\mathsf{Jump}{(i_{k})}$ in which $B$
participates is called by a run of the level-$(i_{k-1})$ algorithm
${\mathsf{Alg}}\mathsf{Jump}{(i_{k-1})}$ in which $B^{*}$ participates.
Moreover, from Observation 4.5.28, each such execution of
${\mathsf{Alg}}\mathsf{Jump}{(i_{k-1})}$ performs at most
$\zeta^{2}(i_{k-1},i_{k})\cdot\frac{\mu_{i_{k-1}}}{\mu_{i_{k}}}\leq\frac{q_{3}(i_{k})}{q_{3}(i_{k-1})}\cdot\frac{\mu_{i_{k-1}}}{\mu_{i_{k}}}$
concurrent calls to ${\mathsf{Alg}}\mathsf{Jump}{(i_{k})}$. Thus, from
induction hypothesis, the maximum number of concurrent calls to the level-$i$
algorithm ${\mathsf{Alg}}\mathsf{Jump}{(i)}$ in which $B$ participates is
indeed,

$\displaystyle\mathsf{load}(B)$
$\displaystyle\leq\mathsf{load}(B^{*})\cdot\frac{q_{3}(i_{k})}{q_{3}(i_{k-1})}\cdot\frac{\mu_{i_{k-1}}}{\mu_{i_{k}}}$
$\displaystyle\leq\frac{q_{1}(i_{k-1})\cdot
q_{3}(i_{k-1})}{q_{2}(i_{k-1})}\cdot\frac{\mu_{i_{0}}}{\mu_{i_{k-1}}}\cdot\frac{q_{3}(i_{k})}{q_{3}(i_{k-1})}\cdot\frac{\mu_{i_{k-1}}}{\mu_{i_{k}}}$
$\displaystyle=\frac{q_{1}(i_{k})\cdot
q_{3}(i_{k})}{q_{2}(i_{k})}\cdot\frac{\mu_{i_{0}}}{\mu_{i_{k}}}.$

Next, we consider the second case where there is a perfect jumpable tuple
$\tau=(i_{k^{\prime}},i_{k^{\prime\prime}},i_{k^{\prime\prime\prime}})$ in
${\mathcal{J}}^{*}$ such that
$k\in\left\\{k^{\prime\prime},k^{\prime\prime\prime}\right\\}$. We analyze the
subcases $k=k^{\prime\prime}$ and $k=k^{\prime\prime\prime}$ separately.

###### Subcase 1: $k=k^{\prime\prime}$.

In this case, the jumpable tuple is
$\tau=(i_{k^{\prime}},i_{k^{\prime\prime}},i_{k^{\prime\prime\prime}})=(i_{k^{\prime}},i_{k},i_{k^{\prime\prime\prime}})$.
Let $B^{*}$ be the level-$i_{k^{\prime}}$ ancestor block of $B$. It is
immediate to verify that each execution to
${\mathsf{Alg}}\mathsf{Jump}{(i_{k})}$ in which $B$ participates is called by
a run of the level-$i_{k^{\prime}}$ algorithm
${\mathsf{Alg}}\mathsf{Jump}{(i_{k}^{\prime})}$ in which $B^{*}$ participates.
From Lemma 4.5.29 each such execution of
${\mathsf{Alg}}\mathsf{Jump}{(i_{k^{\prime}})}$ performs at most
$O\left(\zeta(i_{k^{\prime}},i_{k})\cdot\frac{Z_{i_{k^{\prime}}}}{Z_{i_{k}}}\cdot\eta^{i_{k^{\prime\prime\prime}}-i_{k}}\right)$
concurrent calls to ${\mathsf{Alg}}\mathsf{Jump}{(i_{k})}$. From Claim 4.5.32
and using the fact that $\eta$ is large enough, we can bound this by
$\frac{q_{3}(i_{k})}{q_{3}(i_{k^{\prime}})}\cdot\frac{Z_{i_{k^{\prime}}}}{Z_{i_{k}}}\cdot\eta^{i_{k^{\prime\prime\prime}}-i_{k}}$.
The number of concurrent calls to ${\mathsf{Alg}}\mathsf{Jump}{(j)}$ in which
$B$ participates can now be bounded by,

$\begin{split}\mathsf{load}(B)&\leq\mathsf{load}(B^{*})\cdot\frac{q_{3}(i_{k})}{q_{3}(i_{k^{\prime}})}\cdot\frac{Z_{i_{k^{\prime}}}}{Z_{i_{k}}}\cdot\eta^{i_{k^{\prime\prime\prime}}-i_{k}}\\\
&=\frac{q_{1}(i_{k^{\prime}})\cdot
q_{3}(i_{k})}{q_{2}(i_{k^{\prime}})}\cdot\frac{\mu_{i_{0}}}{\mu_{i_{k^{\prime}}}}\cdot\frac{Z_{i_{k^{\prime}}}}{Z_{i_{k}}}\cdot\eta^{i_{k^{\prime\prime\prime}}-i_{k}}\\\
&=\frac{q_{1}(i_{k^{\prime}})\cdot
q_{3}(i_{k})}{q_{2}(i_{k^{\prime}})}\cdot\frac{\mu_{i_{0}}}{\mu_{i_{k}}}\cdot\left(\frac{\mu_{i_{k}}}{\mu_{i_{k^{\prime}}}}\cdot\frac{Z_{i_{k^{\prime}}}}{Z_{i_{k}}}\cdot\eta^{i_{k^{\prime\prime\prime}}-i_{k}}\right).\end{split}$
(C.6)

But,

$\begin{split}\frac{\mu_{i_{k}}}{\mu_{i_{k^{\prime}}}}\cdot\frac{Z_{i_{k^{\prime}}}}{Z_{i_{k}}}\cdot\eta^{i_{k^{\prime\prime\prime}}-i_{k}}&\leq\eta^{-0.99w_{{\mathcal{I}}(\tau)}+i_{k^{\prime\prime\prime}}-i_{k}}\\\
&\leq\eta^{-0.69w_{{\mathcal{I}}(\tau)}+\mathsf{eq}(i_{k},i_{k^{\prime\prime\prime}})}\\\
&=\frac{q_{1}(i_{k})}{q_{1}(i_{k^{\prime}})}\cdot\frac{q_{2}(i_{k^{\prime}})}{q_{2}(i_{k})}.\end{split}$
(C.7)

Here, the first inequality follows since the level-weight of the jumpable
tuple $\tau$ is
${w_{{\mathcal{I}}(\tau)}=\log_{\eta}{\left(\frac{\mu_{i_{k^{\prime}}}}{\mu_{i_{k}}}\right)}}$
and from the fact that
$\frac{Z_{i_{k^{\prime}}}}{Z_{i_{k}}}\leq\eta^{k-k^{\prime\prime}}\leq\eta^{0.01w_{{\mathcal{I}}(\tau)}}$,
as $\tau$ is a perfect jumpable tuple. The second inequality follows since
$i_{k^{\prime\prime\prime}}-i_{k}=k^{\prime\prime\prime}-k+\mathsf{eq}(i_{k},i_{k^{\prime\prime\prime}})=\left\lfloor
0.3w_{{\mathcal{I}}(\tau)}\right\rfloor+\mathsf{eq}(i_{k},i_{k^{\prime\prime\prime}})$.
The last inequality follows since
$q_{1}(i_{k})=q_{1}(i_{k^{\prime}})\cdot\eta^{\mathsf{eq}(i,i_{k^{\prime\prime\prime}})}$
and
$q_{2}(i_{k})=q_{2}(i_{k^{\prime}})\cdot\eta^{0.39w_{{\mathcal{I}}(\tau)}}$.
Plugging Equation C.7 in Equation C.6, we obtain,

$\mathsf{load}(B)\leq\frac{q_{1}(i_{k^{\prime}})\cdot
q_{3}(i_{k})}{q_{2}(i_{k^{\prime}})}\cdot\frac{\mu_{i_{0}}}{\mu_{i_{k}}}\cdot\left(\frac{q_{1}(i_{k})}{q_{1}(i_{k^{\prime}})}\cdot\frac{q_{2}(i_{k^{\prime}})}{q_{2}(i_{k})}\right)=\frac{q_{1}(i_{k})\cdot
q_{3}(i_{k})}{q_{2}(i_{k})}\cdot\frac{\mu_{i_{0}}}{\mu_{i_{k}}},$

as claimed. This completes the analysis of subcase $1$.

###### Subcase 2: $k=k^{\prime\prime\prime}$.

In this subcase, the jumpable tuple is
$\tau=(i_{k^{\prime}},i_{k^{\prime\prime}},i_{k^{\prime\prime\prime}})=(i_{k^{\prime}},i_{k^{\prime\prime}},i_{k})$.
As before, let $B^{*}$ be the level-$i_{k^{\prime}}$ ancestor block of $B$. We
also consider the level-$(i_{k-1})$ ancestor $\tilde{B}$ of $B$. It is
immediate to verify that each execution to
${\mathsf{Alg}}\mathsf{Jump}{(i_{k})}$ in which $B$ participates is either
called by a run of the level-$i_{k^{\prime}}$ algorithm
${\mathsf{Alg}}\mathsf{Jump}{(i_{k^{\prime}})}$ in which $B^{*}$ participates
or by a run of the level-$(i_{k-1})$ algorithm
${\mathsf{Alg}}\mathsf{Jump}{(i_{k-1})}$ in which $\tilde{B}$ participates.

We first analyze the contribution of the executions of
${\mathsf{Alg}}\mathsf{Jump}{(i_{k^{\prime}})}$ to $\mathsf{load}(B)$.
Consider a run of ${\mathsf{Alg}}\mathsf{Jump}{(i_{k^{\prime}})}$ in which
$B^{*}$ participates. From Lemma 4.5.29 each such execution of
${\mathsf{Alg}}\mathsf{Jump}{(i_{k^{\prime}})}$ performs at most
$O\left(\zeta^{2}(i_{k^{\prime}},i_{k})\cdot\frac{Z_{i_{k^{\prime}}}\cdot
Z_{i_{k}}^{2}}{Z_{i_{k^{\prime\prime}}}^{3}}\cdot\frac{\mu_{i_{k^{\prime}}}}{\mu_{i_{k}}}\right)$
concurrent calls to ${\mathsf{Alg}}\mathsf{Jump}{(i_{k})}$. As before, we can
bound this number by
$\frac{q_{3}(i_{k})}{2q_{3}(i_{k^{\prime}})}\cdot\frac{Z_{i_{k^{\prime}}}\cdot
Z_{i_{k}}^{2}}{Z_{i_{k^{\prime\prime}}}^{3}}\cdot\frac{\mu_{i_{k^{\prime}}}}{\mu_{i_{k}}}$.
Thus, the number of concurrent calls to ${\mathsf{Alg}}\mathsf{Jump}{(i_{k})}$
in which $B$ participates due to all the executions of
${\mathsf{Alg}}\mathsf{Jump}{(i_{k^{\prime}})}$ in which $B^{*}$ participates
is at most,

$\begin{split}\mathsf{load}(B^{*})\cdot\frac{q_{3}(i_{k})}{2q_{3}(i_{k^{\prime}})}\cdot\frac{Z_{i_{k^{\prime}}}\cdot
Z_{i_{k}}^{2}}{Z_{i_{k^{\prime\prime}}}^{3}}\cdot\frac{\mu_{i_{k^{\prime}}}}{\mu_{i_{k}}}&\leq\mathsf{load}(i_{k^{\prime}})\cdot\frac{q_{3}(i_{k})}{2q_{3}(i_{k^{\prime}})}\cdot\frac{Z_{i_{k^{\prime}}}\cdot
Z_{i_{k}}^{2}}{Z_{i_{k^{\prime\prime}}}^{3}}\cdot\frac{\mu_{i_{k^{\prime}}}}{\mu_{i_{k}}}\\\
&\leq\frac{q_{1}(i_{k^{\prime}})q_{3}(i_{k})}{2q_{2}(i_{k^{\prime}})}\cdot\frac{\mu_{i_{0}}}{\mu_{i_{k}}}\cdot\left(\frac{Z_{i_{k^{\prime}}}\cdot
Z_{i_{k}}^{2}}{Z_{i_{k^{\prime\prime}}}^{3}}\right)\\\
&\leq\frac{q_{1}(i_{k^{\prime}})q_{3}(i_{k})}{2q_{2}(i_{k^{\prime}})}\cdot\frac{\mu_{i_{0}}}{\mu_{i_{k}}}\cdot\left(\eta^{-0.39w_{{\mathcal{I}}(\tau)}}\right)\\\
&\leq\frac{q_{1}(i_{k})q_{3}(i_{k})}{2q_{2}(i_{k})}\cdot\frac{\mu_{i_{0}}}{\mu_{i_{k}}}.\end{split}$
(C.8)

Here, the third inequality follows since
$\tau=(i_{k^{\prime}},i_{k^{\prime\prime}},i_{k})$ is a perfect jumpable tuple
implying
$\frac{Z_{i_{k}}}{Z_{i_{k^{\prime\prime}}}}\leq\eta^{-0.2w_{{\mathcal{I}}(\tau)}}$
and
$\frac{Z_{i_{k^{\prime}}}}{Z_{i_{k^{\prime\prime}}}}\leq\eta^{k^{\prime\prime}-k^{\prime}}\leq\eta^{0.01w_{{\mathcal{I}}(\tau)}}$.
The last inequality follows since $k>k^{\prime\prime}$ and
$q_{2}(i_{k})=q_{2}(i_{k^{\prime}})\cdot\eta^{0.39w_{{\mathcal{I}}(\tau)}}$.
This completes the analysis of the contribution of the executions of
${\mathsf{Alg}}\mathsf{Jump}{(i_{k^{\prime}})}$ to $\mathsf{load}(B)$.

We now analyze the contribution of the executions of
${\mathsf{Alg}}\mathsf{Jump}{(i_{k-1})}$ to $\mathsf{load}(B)$. From
Observation 4.5.28, each execution of ${\mathsf{Alg}}\mathsf{Jump}{(i_{k-1})}$
in which $\tilde{B}$ participates, performs at most
$O\left(\zeta(i_{k-1},i_{k})\cdot\frac{\mu_{i_{k-1}}}{\mu_{i_{k}}}\right)\leq\frac{q_{3}(i_{k})}{2q_{3}(i_{k-1})}\cdot\frac{\mu_{i_{k-1}}}{\mu_{i_{k}}}$
concurrent calls to ${\mathsf{Alg}}\mathsf{Jump}{(i_{k})}$. The number of
concurrent calls to ${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$ in which $B$
participates due to the execution of ${\mathsf{Alg}}\mathsf{Jump}{(i_{k-1})}$
in which $B^{\prime}$ participates can now be bounded by,

$\begin{split}\mathsf{load}(\tilde{B})\cdot\frac{q_{3}(i_{k})}{2q_{3}(i_{k-1})}\cdot\frac{\mu_{i_{k-1}}}{\mu_{i_{k}}}&\leq\mathsf{load}(i_{k-1})\cdot\frac{q_{3}(i_{k})}{2q_{3}(i_{k-1})}\cdot\frac{\mu_{i_{k-1}}}{\mu_{i_{k}}}\\\
&\leq\frac{q_{1}(i_{k-1})q_{3}(i_{k})}{2q_{2}(i_{k-1})}\cdot\frac{\mu_{i_{0}}}{\mu_{i_{k-1}}}\cdot\frac{\mu_{i_{k-1}}}{\mu_{i_{k}}}\\\
&=\frac{q_{1}(i_{k})q_{3}(i_{k})}{2q_{2}(i_{k})}\cdot\frac{\mu_{i_{0}}}{\mu_{i_{k}}}.\end{split}$
(C.9)

Here, the last inequality follows since $q_{1}(i)=q_{1}(i_{k-1})$ and
$q_{2}(i)=q_{2}(i_{k-1})$. We now conclude that $\mathsf{load}(B)$ is indeed
bounded by
$\frac{q_{1}(i)q_{3}(i)}{q_{2}(i)}\cdot\frac{\mu_{i_{0}}}{\mu_{i}}$. Thus,
$\mathsf{load}(i)\leq\frac{q_{1}(i)q_{3}(i)}{q_{2}(i)}\cdot\frac{\mu_{i_{0}}}{\mu_{i}}$
as claimed. This completes the analysis of the contribution of the executions
of ${\mathsf{Alg}}\mathsf{Jump}{(i_{k-1})}$ to $\mathsf{load}(B)$.

From LABEL:{{eqn:_ncm-algjump-subcase-2-1} and LABEL:{{eqn:_ncm-algjump-
subcase-2-2}}}, we now conclude that the number of concurrent calls to
${\mathsf{Alg}}\mathsf{Jump}{(i_{k})}$ in which $B$ participates is indeed
bounded by,

$\mathsf{load}(B)\leq
2\cdot\frac{q_{1}(i_{k})q_{3}(i_{k})}{2q_{2}(i_{k})}\cdot\frac{\mu_{i_{0}}}{\mu_{i_{k}}}=\frac{q_{1}(i_{k})q_{3}(i_{k})}{q_{2}(i_{k})}\cdot\frac{\mu_{i_{0}}}{\mu_{i_{k}}},$

as claimed. This completes the analysis of subcase $2$, and hence the
induction step. This also completes the proof of Claim 4.5.33. $\Box$

#####  C.2.5.3 Proof of Claim 4.5.34.

We claim that $\max_{i\in{\mathcal{I}}^{*}}L^{*}(i)=L^{*}(i_{k^{*}})$. To show
this, it suffices to show that for each jumpable tuple
$\tau=(i,j,\ell)\in{\mathcal{J}}^{*}$, $L^{*}(i)\leq L^{*}(j)$. Indeed,

$\displaystyle\frac{L^{*}(j)}{L^{*}(i)}$ $\displaystyle=\frac{q_{1}(j)\cdot
q_{3}(j)\cdot q_{2}(i)}{q_{2}(j)\cdot q_{1}(i)\cdot
q_{3}(i)}\cdot\frac{\mu_{i}}{\mu_{j}}$
$\displaystyle\geq\frac{q_{2}(i)}{q_{2}(j)}\cdot\eta^{w_{{\mathcal{I}}(\tau)}}$
$\displaystyle=\eta^{w_{{\mathcal{I}}(\tau)}-0.39w_{{\mathcal{I}}(\tau)}}=\eta^{0.61w_{{\mathcal{I}}(\tau)}}>1.$

It now remains to upper-bound $L^{*}(i_{k^{*}})=\frac{q_{1}(i_{k^{*}})\cdot
q_{3}(i_{k^{*}})}{q_{2}(i_{k^{*}})}\cdot\frac{\mu_{i_{0}}}{\mu_{i_{k^{*}}}}$.
Since $Z_{i_{0}}=Z_{0}\geq N^{1/2-\epsilon}$, we have,

$\mu_{i_{0}}=\frac{X_{i_{0}}}{Z_{i_{0}}}=\frac{N/\eta^{i_{0}}}{Z_{0}}\leq\frac{N^{1/2+\epsilon}}{\eta^{i_{0}}}\leq
N^{1/2+\epsilon}.$ (C.10)

On the other hand, from Claim 4.5.10 and the fact that
$r^{*}=\left\lfloor(1/2-4\epsilon)r\right\rfloor$, we obtain,

$q_{1}(k^{*})=\eta^{\mathsf{eq}(i_{0},i_{k^{*}})}\leq\eta^{r^{*}-k^{*}}\leq
N^{4\epsilon}.$ (C.11)

Moreover,

$\log_{\eta}{\left(q_{2}(i_{k^{*}})\right)}=\sum_{\tau\in{\mathcal{J}}^{*}}0.39w_{{\mathcal{I}}(\tau)}=0.39w_{{\mathcal{I}}({\mathcal{J}}^{*})}\geq\frac{39}{100}\cdot\frac{r}{10^{5}}\geq\frac{3r}{10^{6}},$

or in other words,

$q_{2}(i_{k}^{*})\geq\eta^{\frac{3r}{10^{6}}}\geq{N^{\frac{3}{10^{6}}}}/{\eta},$
(C.12)

as $r=\left\lfloor\frac{\log N}{\log\eta}\right\rfloor$. Finally, from
LABEL:{clm:_ncm-jump-load-induction} and LABEL:{clm:_ncm-lis-simple-pi-zeta-
bound}, we obtain,

$q_{3}(i_{k^{*}})\leq\prod_{0\leq
k^{\prime}<k^{*}}\zeta^{4}(i_{k^{\prime}},i_{k^{\prime}+1})=N^{o(1)}.$ (C.13)

We are now ready to provide an upper bound for
$L^{*}(i_{k^{*}})=\frac{q_{1}(i_{k^{*}})\cdot
q_{3}(i_{k^{*}})}{q_{2}(i_{k^{*}})}\cdot\frac{\mu_{i_{0}}}{\mu_{i_{k^{*}}}}$.
From LABEL:{eqn:_ncm-jump-loadi-small-1}, LABEL:{eqn:_ncm-jump-loadi-small-2},
LABEL:{eqn:_ncm-jump-loadi-small-3} and LABEL:{eqn:_ncm-jump-loadi-small-4},

$\displaystyle L^{*}(i_{k^{*}})$ $\displaystyle=\frac{q_{1}(i_{k^{*}})\cdot
q_{3}(i_{k^{*}})}{q_{2}(i_{k^{*}})}\cdot\frac{\mu_{i_{0}}}{\mu_{i_{k^{*}}}}$
$\displaystyle\leq\frac{N^{4\epsilon+o(1)}}{N^{\frac{3}{10^{6}}}}\cdot
N^{\frac{1}{2}+\epsilon}\leq N^{\frac{1}{2}+6\epsilon-\frac{3}{10^{6}}}\leq
N^{\frac{1}{2}-\frac{2}{10^{6}}},$

where the last inequality holds for all $\epsilon\leq 10^{-7}$. Here, the
second inequality follows from the facts that $r=\left\lfloor\frac{\log
N}{\log\eta}\right\rfloor$ and $\epsilon$ is an absolute constant. $\Box$

#####  C.2.5.4 Proof of Claim 4.5.36.

We claim that it suffices to show that $\text{\bf
Pr}\left[{\mathcal{E}}^{*}_{\mathsf{bad}}\right](\hat{B})\leq
e^{-3\zeta(i,\ell)}$ for each level-$\ell$ descendant-block $\hat{B}$ of
$B^{*}$. Indeed, if we could show this, then Claim 4.5.36 follows by union
bound over at most $e^{\zeta(i,\ell)}$ possible level-$\ell$ descendant
stream-blocks of $B^{*}$.

Consider now a level-$\ell$ descendant-block $\hat{B}$ of $B^{*}$ and let $B$
be the level-$j$ ancestor-block of $\hat{B}$. Notice that all the calls to the
level-$\ell$ algorithm ${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$ in which
$\hat{B}$ participates are performed through the calls to
$\mathsf{Alg}{\mathsf{Gen}}$ in which $B$ participates. Consider one such call
to $\mathsf{Alg}{\mathsf{Gen}}$. From Lemma 4.5.35, this execution of
$\mathsf{Alg}{\mathsf{Gen}}$ independently randomly marks $\hat{B}$ with
probability $O\left(\zeta(i,\ell)\cdot\frac{Z_{\ell}}{Z_{j}}\right)$. If
$\hat{B}$ is marked, it performs at most
$O\left(\zeta(i,\ell)\cdot\frac{Z_{\ell}\mu_{i}}{Z_{j}\mu_{\ell}}\right)$
calls to ${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$ in which $\hat{B}$
participates. Otherwise, if $\hat{B}$ is not marked, it does not perform any
call to ${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$ in which $\hat{B}$ participates.
111Note that we are excluding the calls to
${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$ performed by
${\mathsf{Alg}}\mathsf{Jump}{(j)}$. Since there are at most
$O\left(\frac{Z_{i}}{Z_{j}}\right)$ concurrent calls to
$\mathsf{Alg}{\mathsf{Gen}}$, the expected number of concurrent calls to
${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$ in which $\hat{B}$ participates is
bounded by,

$\displaystyle O\left(\frac{Z_{i}}{Z_{j}}\right)\cdot
O\left(\frac{\zeta(i,\ell)Z_{\ell}}{Z_{j}}\right)\cdot
O\left(\frac{\zeta(i,\ell)Z_{\ell}\mu_{i}}{Z_{j}\mu_{\ell}}\right)$
$\displaystyle=O\left(\zeta^{2}(i,\ell)\right)\frac{Z_{i}\cdot
Z_{\ell}^{2}}{Z_{j}^{3}}\cdot\frac{\mu_{i}}{\mu_{\ell}}$ $\displaystyle\leq
c^{\prime}\cdot\zeta^{2}(i,\ell)\cdot\frac{Z_{i}\cdot
Z_{\ell}^{2}}{Z_{j}^{3}}\cdot\frac{\mu_{i}}{\mu_{\ell}},$

for some absolute constant $c^{\prime}$. We now chose the constant
$c=18\max{(c^{\prime},1)}$ in the definition of $L^{*}$ so that this expected
number of concurrent calls to ${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$ is bounded
by $\frac{L^{*}}{6}$. But then,

$\displaystyle L^{*}$ $\displaystyle\geq
18\zeta^{2}(i,\ell)\cdot\frac{Z_{i}\cdot
Z_{\ell}^{2}}{Z_{j}^{3}}\cdot\frac{\mu_{i}}{\mu_{\ell}}$
$\displaystyle>18\zeta(i,\ell)\cdot\frac{Z_{\ell}^{2}}{Z_{j}^{2}}\cdot\frac{\mu_{i}}{\mu_{j}}$
$\displaystyle\geq 18\zeta(i,\ell).$

Here, the second inequality follows since $i<j<\ell$ and hence, $Z_{i}>Z_{j}$
and $\mu_{j}\geq\mu_{\ell}$. The last inequality follows from our assumption
that $\left(\frac{Z_{j}}{Z_{\ell}}\right)^{2}\leq\frac{\mu_{i}}{\mu_{j}}$.
From Chernoff bound (4.2.4), the probability that we perform more than $L^{*}$
calls to ${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$ in which $\hat{B}$ participates
is bounded by $e^{\left(-\frac{L^{*}}{6}\right)}<e^{-3\zeta(i,\ell)}$ as
claimed. $\Box$

#####  C.2.5.5 Proof of Claim 4.5.37.

Consider a level-$j$ yes-pair $(B,B^{\prime})$ with
$B\in{\mathcal{B}}_{\mathsf{yes}}$ and
$B^{\prime}\in{\mathcal{B}}^{\prime}_{\mathsf{yes}}$. Let
$\tilde{\mathcal{R}}$ be our collection of the regions of $B^{*^{\prime}}$
just before processing the first element of $B$. We also fix the special
region
$\mathsf{leftover}(\tilde{\mathcal{R}})={\mathcal{B}}^{\prime}\backslash\bigcup_{{\mathcal{R}}\in\tilde{\mathcal{R}}}{\mathcal{R}}$.
Since the non-empty regions of
$\tilde{\mathcal{R}}\cup\left\\{\mathsf{leftover}(\tilde{\mathcal{R}})\right\\}$
constitute a partition of ${\mathcal{B}}^{\prime}$, there is exactly one
region
${\mathcal{R}}\in\tilde{\mathcal{R}}\cup\left\\{\mathsf{leftover}(\tilde{\mathcal{R}})\right\\}$
such that $B^{\prime}\in{\mathcal{R}}$. We fix such a region ${\mathcal{R}}$
and consider the execution of $\mathsf{Alg}{\mathsf{Gen}}$ with input $B$ and
${\mathcal{R}}$. We let ${\mathcal{R}}^{\prime}$ be the output of this
execution. We let ${\mathcal{E}}_{\mathsf{bad}}(B)$ be the event that either
the output region ${\mathcal{R}}^{\prime}=\emptyset$ or
${\mathcal{R}}^{\prime}$ contains some range-block appearing after
$B^{\prime}$ in ${\mathcal{B}}^{\prime}$. From the correctness guarantee of
$\mathsf{Alg}{\mathsf{Gen}}$, the probability that
${\mathcal{E}}_{\mathsf{bad}}$ occurs is at most
$e^{-\zeta(i,\ell)}\leq\frac{1}{10|{\mathcal{B}}|}$. We let
${\mathcal{E}}_{\mathsf{bad}}$ be the bad event
${\mathcal{E}}_{\mathsf{bad}}(B)$ occurs for some level-$j$ yes-block
$B\in{\mathcal{B}}_{\mathsf{yes}}$. From union bound over at most
$|{\mathcal{B}}_{\mathsf{yes}}|\leq|{\mathcal{B}}|$ yes-blocks of
${\mathcal{B}}$, the probability that ${\mathcal{E}}_{\mathsf{bad}}$ occurs is
at most $0.1$. We assume from now on that the event
${\mathcal{E}}_{\mathsf{bad}}$ does not occur.

We will need the following simple observation. Consider some stream-block
$B\in{\mathcal{B}}$. Let $\tilde{\mathcal{R}}^{\mathsf{pre}}$ be the
collection of regions of ${\mathcal{B}}^{\prime}$ just before processing the
stream-block $B$. Similarly, let $\tilde{\mathcal{R}}^{\mathsf{post}}$ be the
collection of regions of ${\mathcal{B}}^{\prime}$ just after processing $B$.
Let
$\tilde{\mathcal{R}}^{\mathsf{pre}}=\left\\{{\mathcal{R}}^{\mathsf{pre}}_{1},\ldots,{\mathcal{R}}^{\mathsf{pre}}_{k^{\prime}}\right\\}$
and
$\tilde{\mathcal{R}}^{\mathsf{post}}=\left\\{{\mathcal{R}}^{\mathsf{post}}_{1},\ldots,{\mathcal{R}}^{\mathsf{post}}_{k^{\prime\prime}}\right\\}$
in their natural order. It is immediate to see that $k^{\prime\prime}\geq
k^{\prime}$ and for each $1\leq s\leq k^{\prime}$, the region
${\mathcal{R}}^{\mathsf{post}}_{s}$ does not contain any range-block that
appears after the region ${\mathcal{R}}^{\mathsf{pre}}_{s}$. We are now ready
to complete the proof of Claim 4.5.37 by induction.

The base case is when $s=1$, where we consider the first stream-block $B(1)$
of ${\mathcal{B}}_{\mathsf{yes}}$. Let $\tilde{\mathcal{R}}^{\mathsf{pre}}$ be
the collection of regions of ${\mathcal{B}}^{\prime}$ just before processing
$B^{(1)}$. We also let $\mathsf{leftover}(\tilde{\mathcal{R}}^{\mathsf{pre}})$
be the special region consisting of range-blocks not contained in the regions
of $\tilde{\mathcal{R}}^{\mathsf{pre}}$. For convenience, we let
$\tilde{\mathcal{R}}=\tilde{\mathcal{R}}^{\mathsf{pre}}\cup\left\\{\mathsf{leftover}(\tilde{\mathcal{R}}^{\mathsf{pre}})\right\\}$
and let
$\tilde{\mathcal{R}}=\left\\{{\mathcal{R}}_{1},\ldots,{\mathcal{R}}_{k}\right\\}$
be these regions in their natural order where $k=|\tilde{\mathcal{R}}|$. Since
the non-empty regions of $\tilde{\mathcal{R}}$ form a partition of the
level-$j$ blocks ${\mathcal{B}}^{\prime}$, there is a unique integer $1\leq
k^{\prime}\leq k$ such that $B^{\prime}(1)\in{\mathcal{R}}_{k^{\prime}}$.
Recall that $\tilde{\mathcal{R}}^{(1)}$ is the collection of regions of
${\mathcal{B}}^{\prime}$ just after processing $B^{(1)}$. We first consider
the case where $k^{\prime}>1$. In this case, all the range-blocks of
${\mathcal{R}}_{1}$ appear before $B^{\prime}(1)$. But then all the range-
blocks of the first region of ${\mathcal{R}}^{(1)}$ appear before
$B^{\prime}(1)$ and the assertion follows. Thus, assume from now on that
$k^{\prime}=1$, or in other words, $B^{\prime}\in{\mathcal{R}}_{1}$. Recall
that we call the subblock processing algorithm $\mathsf{Alg}{\mathsf{Gen}}$
with input $B^{(1)}$ and the region ${\mathcal{R}}_{1}$ and let
${\mathcal{R}}^{\prime}_{1}$ be the region it reports. Since the event
${\mathcal{E}}_{\mathsf{bad}}(B^{(1)})$ does not occur,
${\mathcal{R}}^{\prime}_{1}\neq\emptyset$, and it does not contain any range-
block appearing after $B^{\prime}(1)$. In this case, the first region of
${\mathcal{R}}^{(1)}$ is ${\mathcal{R}}^{\prime}_{1}$ and the assertion
follows for the base case where $s=1$.

We now fix some $1<s\leq\beta$. We assume that the assertion holds for $s-1$
and show it for $s$. Let $\tilde{\mathcal{R}}^{\mathsf{pre}}$ be the
collection of regions of ${\mathcal{B}}^{\prime}$ just before processing
$B^{(s)}$. We also let $\mathsf{leftover}(\tilde{\mathcal{R}}^{\mathsf{pre}})$
be the region consisting of range-blocks not contained in the regions of
$\tilde{\mathcal{R}}^{\mathsf{pre}}$. Recall that $\tilde{\mathcal{R}}^{(s)}$
is the collection of regions of ${\mathcal{B}}^{\prime}$ just after processing
$B^{(1)}$. As before, we let
$\tilde{\mathcal{R}}=\tilde{\mathcal{R}}^{\mathsf{pre}}\cup\left\\{\mathsf{leftover}(\tilde{\mathcal{R}}^{\mathsf{pre}})\right\\}$.
Let
$\tilde{\mathcal{R}}=\left\\{{\mathcal{R}}_{1},\ldots,{\mathcal{R}}_{k}\right\\}$
be these regions in their natural order where $k=|\tilde{\mathcal{R}}|$. Since
the non-empty regions of $\tilde{\mathcal{R}}$ form a partition of the
level-$j$ blocks ${\mathcal{B}}^{\prime}$, there is a unique integer $1\leq
k^{\prime}\leq k$ such that $B^{\prime}(s)\in{\mathcal{R}}_{k^{\prime}}$. If
$k^{\prime}>s$, there is nothing to show since all the range-blocks of
${\mathcal{R}}_{s}$ appear before $B^{\prime}(s)$. In this case, all the
range-blocks of the $s^{th}$ region of ${\mathcal{R}}^{(s)}$ appear before
$B^{\prime}(s)$ and the assertion follows. Thus, assume that $k^{\prime}\leq
s$. From our induction hypothesis, it is immediate to verify that the regions
$\left\\{{\mathcal{R}}_{1},\ldots,{\mathcal{R}}_{s-1}\right\\}$ does not
contain any range-block that appear after $B^{\prime}(s-1)$. Since the range-
block $B^{\prime}(s)$ appears after $B^{\prime}(s-1)$, we must have
$k^{\prime}=s$, or in other words, $B^{\prime}(s)\in{\mathcal{R}}_{s}$. Recall
that we execute the subblock processing algorithm $\mathsf{Alg}{\mathsf{Gen}}$
with input $B^{(1)}$ and the region ${\mathcal{R}}_{s}$. Let
${\mathcal{R}}^{\prime}_{s}$ be the region it reports. Since the event
${\mathcal{E}}_{\mathsf{bad}}(B^{(s)})$ does not occur,
${\mathcal{R}}^{\prime}_{s}\neq\emptyset$, and it does not contain any range-
block appearing after $B^{\prime}(s)$. In this case, the last range-block of
$s^{th}$ region of ${\mathcal{R}}^{(1)}$ is the last range-block of
${\mathcal{R}}^{\prime}_{s}$ and the assertion follows.

This completes the induction step and Claim 4.5.37 follows. $\Box$

#####  C.2.5.6 Proof of Claim 4.5.38.

We proceed by induction. The base case is when $s=1$. It is immediate to see
that $|\tilde{\mathcal{R}}^{(1)}|\leq 1$. If
$\tilde{\mathcal{R}}^{(1)}=\emptyset$, there is nothing to show. Thus, assume
that $|\tilde{\mathcal{R}}^{(1)}|=1$ and let ${\mathcal{R}}^{(1)}$ be the
single region of $\tilde{\mathcal{R}}^{(1)}$. Since the event
${\mathcal{E}}_{\mathsf{bad}}(B(1))$ does not occur, we conclude that there is
an increasing subsequence of $B(1)$ of length at least
$\frac{Z_{j}}{\alpha^{\prime}_{j}}$ with values in the range-blocks of
${\mathcal{R}}^{(1)}$. The assertion now follows.

We fix some $1<s\leq|{\mathcal{B}}|$ and assume that the induction hypothesis
holds for $s-1$. We consider the collection $\tilde{\mathcal{R}}^{(s-1)}$ of
regions just before processing elements of $B(s)$. For readability, we drop
the superscript and denote this collection by $\tilde{\mathcal{R}}$. Let
$\tilde{\mathcal{R}}=\left\\{{\mathcal{R}}(1),\ldots,{\mathcal{R}}(|\tilde{\mathcal{R}}|)\right\\}$
be these regions in their natural order. From our induction hypothesis, for
each $1\leq s^{\prime}\leq|\tilde{\mathcal{R}}|$, there is an increasing
subsequence of $B(1)\cup\ldots\cup B(s-1)$ of length at least
$\frac{s^{\prime}Z_{j}}{\alpha^{\prime}_{j}}$ with values in the range-blocks
of ${\mathcal{R}}(1)\cup\ldots\cup{\mathcal{R}}(s^{\prime})$. We are now ready
to show the assertion for $s$, starting with the case where $1\leq
s^{\prime}\leq|\tilde{\mathcal{R}}|$.

Consider the execution of $\mathsf{Alg}{\mathsf{Gen}}$ with the input stream-
block $B(s)$ and the $s^{\prime}{th}$ region
${{\mathcal{R}}(s^{\prime})\in\tilde{\mathcal{R}}}$. Let
${\mathcal{R}}^{\prime}(s^{\prime})$ be the region it reports. We first
consider the case where ${\mathcal{R}}^{\prime}(s^{\prime})\neq\emptyset$.
Since the event ${\mathcal{E}}_{\mathsf{bad}}(B(s),{\mathcal{R}}(s^{\prime}))$
did not occur, there must be an increasing subsequence of $B(s)$ of length at
least $\frac{Z_{j}}{\alpha^{\prime}_{j}}$ with values in the range-blocks of
${\mathcal{R}}^{\prime}(s^{\prime})$. Moreover,
${\mathcal{R}}^{\prime}(s^{\prime})$ does not contain any range-block of
${\mathcal{R}}(1)\cup\ldots{\mathcal{R}}(s^{\prime}-1)$. But from our
induction hypothesis, there is an increasing subsequence of
$B(1)\cup\ldots\cup B(s-1)$ of length at least
$\frac{(s^{\prime}-1)Z_{j}}{\alpha^{\prime}_{j}}$ with values in the range-
blocks of ${\mathcal{R}}(1)\cup\ldots\cup{\mathcal{R}}(s^{\prime}-1)$. Thus,
there is an increasing subsequence of $B(1)\cup\ldots\cup B(s)$ of length at