$B^{\prime}_{\min{}}$ be the lowest range-block for which at least
corresponding $2^{5}\zeta$ runs of ${\mathsf{Alg}}\mathsf{Jump}{(j)}$ returns
in affirmative. Recall that, if such $B^{\prime}_{\min}$ exists, we report the
region ${\mathcal{R}}^{\prime}=\left\\{B^{\prime}_{\min{}}\right\\}$. We claim
that such a range-block $B^{\prime}_{\min{}}$ exist, and it does not appear
after $B^{\prime}$. Indeed, $B^{\prime}$ is a candidate for being
$B^{\prime}_{\min{}}$ and the claim follows.

  * •

Case $2$: $B^{\prime}$ ceases to be an active pseudo-suspicious during the
processing of $B$. Since $B^{\prime}$ ceases to be an active pseudo-suspicious
block, we must have had at least $|\hat{\mathcal{B}}|$ active pseudo-
suspicious blocks. Moreover, each such active pseudo-suspicious block appear
before $B^{\prime\prime}$. Recall that in this case we report the smallest
region ${\mathcal{R}}^{\prime}\subseteq{\mathcal{R}}$ encompassing all active
pseudo-suspicious blocks. In particular, this non-empty region
${\mathcal{R}}^{\prime}$ does not contain any range-block appearing after
$B^{\prime}$.

Thus, with probability at least $1-e^{-\zeta}$, we report the region
${\mathcal{R}}^{\prime}$ with claimed properties. This completes the proof of
completeness of our generalized subblock processing algorithm.

###### Soundness.

We denote by the event ${\mathcal{E}}^{*}_{\mathsf{bad}}$ the event that the
reported region ${\mathcal{R}}^{\prime}$ satisfies the following two
properties: (i) ${\mathcal{R}}^{\prime}\neq\emptyset$; and (ii) the longest
increasing subsequence of $B$ with values in the range-blocks of
${\mathcal{R}}^{\prime}$ has size less than $Z_{j}/\alpha^{\prime}_{j}$. Our
goal is to show that $\text{\bf
Pr}\left[{\mathcal{E}}^{*}_{\mathsf{bad}}\right]\leq e^{-\zeta}$, where the
probability is over the randomness used by $\mathsf{Alg}{\mathsf{Gen}}$ and
the executions of ${\mathsf{Alg}}\mathsf{Jump}{(j)}$ and
${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$ that it performs.

We will need the following definition. Recall that we say that a level-$\ell$
pair $(\hat{B},\hat{B}^{\prime})$ is a promising pair iff
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(\hat{B}\cap\hat{B}^{\prime})\geq\frac{Z_{\ell}}{\alpha^{\prime}_{\ell}}$.
We say that a range-block $B^{\prime}\in{\mathcal{R}}$ is a _good block_ if
there are at least
$3\frac{Z_{j}\alpha^{\prime}_{\ell}}{Z_{\ell}\alpha^{\prime}_{j}}$ stream-
blocks of $\hat{\mathcal{B}}$ that participate in promising pairs with the
level-$\ell$ descendants of $B^{\prime}$. We say that it is a _bad block_
otherwise. We let $\hat{\mathcal{E}}$ be the event that _every_ block marked
pseudo-suspicious by our algorithm is also a good block.

######  Claim 4.5.42.

$\text{\bf Pr}\left[\hat{\mathcal{E}}\right]\geq 1-e^{-2\zeta}$.

###### Proof.

We will use the following claim whose proof is deferred to Section C.2.5.9.

######  Claim 4.5.43.

Fix a range-block $B^{\prime}\in{\mathcal{R}}$ that is a bad block. Then
$B^{\prime}$ is marked pseudo-suspicious with probability at most
$e^{-3\zeta}$.

Since there are most $|{\mathcal{R}}|\leq|{\mathcal{B}}^{\prime}|$ bad blocks,
from Claim 4.5.43, the expected number of bad blocks that are marked
suspicious is at most $|{\mathcal{B}}^{\prime}|e^{-3\zeta}<e^{-2\zeta}$. Here,
the last inequality follows size
$\zeta=\zeta(i,\ell)\geq\ln{\left(|{\mathcal{B}}^{\prime}|\right)}$. From
Markov’s inequality, the probability that there exists a bad block that is
marked pseudo-suspicious is at most $e^{-2\zeta}$. In other words, $\text{\bf
Pr}\left[\hat{\mathcal{E}}\right]\geq 1-e^{-2\zeta}$ and the claim follows.

To show that $\text{\bf Pr}\left[{\mathcal{E}}^{*}_{\mathsf{bad}}\right]\leq
e^{-\zeta}$, it now suffices to show that for each non-empty region
${\mathcal{R}}^{\prime}$ that is contained in ${\mathcal{R}}$ such that the
longest increasing subsequence of $B$ with values in the range-blocks of
${\mathcal{R}}^{\prime}$ has size less than $Z_{j}/\alpha^{\prime}_{j}$, the
probability that we report ${\mathcal{R}}^{\prime}$ is small. The claim will
then follow by a union bound over $|{\mathcal{R}}|+\binom{|{\mathcal{R}}|}{2}$
such possible regions. To this end, fix a region
${\mathcal{R}}^{\prime}\subseteq{\mathcal{R}}$. We let
${\mathcal{E}}^{*}_{\mathsf{bad}}({\mathcal{R}}^{\prime})$ be the event that
we report the region ${\mathcal{R}}^{\prime}$ and the event
${\mathcal{E}}^{*}_{\mathsf{bad}}$ occurs. Note that for us to potentially
report the region ${\mathcal{R}}^{\prime}$, either
$|{\mathcal{R}}^{\prime}|=1$ or
$|{\mathcal{R}}^{\prime}|\geq|\hat{\mathcal{B}}|$ must hold. We analyze both
these cases separately.

###### Case $1$: $|{\mathcal{R}}^{\prime}|=1$.

Let $B^{\prime}\in{\mathcal{R}}$ be the level-$j$ range-block such that
${\mathcal{R}}^{\prime}=\left\\{B^{\prime}\right\\}$. For us to report the
region ${\mathcal{R}}^{\prime}$, the range-block $B^{\prime}$ must remain an
active pseudo-suspicious block throughout the algorithm and at least
$2^{5}\zeta$ corresponding calls to ${\mathsf{Alg}}\mathsf{Jump}{(j)}$ must
have returned yes. Furthermore, for the event
${\mathcal{E}}^{*}_{\mathsf{bad}}({\mathcal{R}}^{\prime})$ to occur,
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(B\cap
B^{\prime})<Z_{j}/\alpha^{\prime}_{j}$ must hold. But then from the
correctness guarantee of ${\mathsf{Alg}}\mathsf{Jump}{(j)}$, each call to
${\mathsf{Alg}}\mathsf{Jump}{(j)}$ in which the level-$j$ pair
$(B,B^{\prime})$ participates, return yes with probability at most $1/4$. From
Chernoff bound (4.2.4), the probability that at least $2^{5}\zeta$ out of
$\left\lfloor 2^{6}\zeta\right\rfloor$ such calls return yes is at most
$e^{-3\zeta}$. We now conclude that $\text{\bf
Pr}\left[{\mathcal{E}}^{*}_{\mathsf{bad}}({\mathcal{R}}^{\prime})\>|\>|{\mathcal{R}}^{\prime}|=1\right]\leq
e^{-3\zeta}$.

###### Case $2$: $|{\mathcal{R}}^{\prime}|\geq|\hat{\mathcal{B}}|$.

We assume that the event $\hat{\mathcal{E}}$ indeed occurs. For the event
${\mathcal{E}}^{*}_{\mathsf{bad}}({\mathcal{R}}^{\prime})$ to occur in this
case, we must have found a set
${\mathcal{B}}^{\prime\prime\prime}\subseteq{\mathcal{R}}^{\prime}\subseteq{\mathcal{R}}$
of $|\hat{\mathcal{B}}|$ active pseudo-suspicious range-blocks. Fix such a set
${\mathcal{B}}^{\prime\prime\prime}$ of active pseudo-suspicious range-blocks,
each of which is also a good block. We will use the following observation,
whose proof follows that of Observation 4.5.39 and is deferred to Section
C.2.5.10.

######  Observation 4.5.44.

For every set ${\mathcal{B}}_{\mathsf{good}}\subseteq{\mathcal{R}}$ of
$|\hat{\mathcal{B}}|$ good blocks, there is an increasing subsequence of $B$
of length more than $\frac{Z_{j}}{\alpha^{\prime}_{j}}$ using values in range-
blocks of ${\mathcal{B}}_{\mathsf{good}}$.

We now conclude that $\text{\bf
Pr}\left[{\mathcal{E}}^{*}_{\mathsf{bad}}({\mathcal{R}}^{\prime})\>|\>\left(\hat{\mathcal{E}}\text{
and }|{\mathcal{R}}^{\prime}|\geq|\hat{\mathcal{B}}|\right)\right]=0$. We are
now ready to complete the proof of soundness of $\mathsf{Alg}{\mathsf{Gen}}$
by union bound over $|{\mathcal{R}}|+\binom{|{\mathcal{R}}|}{2}$ possible
regions ${\mathcal{R}}^{\prime}$ that are contained in ${\mathcal{R}}$. From
the above discussion,

$\displaystyle\text{\bf Pr}\left[{\mathcal{E}}^{*}_{\mathsf{bad}}\right]$
$\displaystyle=\text{\bf
Pr}\left[\bigcup_{\begin{subarray}{c}{\mathcal{R}}^{\prime}\text{ is a region
in
}{\mathcal{R}}\end{subarray}}{\mathcal{E}}^{*}_{\mathsf{bad}}({\mathcal{R}}^{\prime})\right]$
$\displaystyle\leq\left(\sum_{\begin{subarray}{c}{\mathcal{R}}^{\prime}\text{
is a region in }{\mathcal{R}}\\\
|{\mathcal{R}}^{\prime}|=1\end{subarray}}\text{\bf
Pr}\left[{\mathcal{E}}^{*}_{\mathsf{bad}}({\mathcal{R}}^{\prime})\right]\right)+\text{\bf
Pr}\left[\neg\hat{\mathcal{E}}\right]+\left(\sum_{\begin{subarray}{c}{\mathcal{R}}^{\prime}\text{
is a region in }{\mathcal{R}}\\\
|{\mathcal{R}}^{\prime}|\geq|\hat{\mathcal{B}}|\end{subarray}}\text{\bf
Pr}\left[{\mathcal{E}}^{*}_{\mathsf{bad}}({\mathcal{R}}^{\prime})\>|\>\hat{\mathcal{E}}\right]\right)$
$\displaystyle\leq|{\mathcal{R}}|\cdot
e^{-3\zeta}+e^{-2\zeta}+\binom{|{\mathcal{R}}|}{2}\cdot 0$ $\displaystyle\leq
e^{-2\zeta}+e^{-2\zeta}$ $\displaystyle\leq e^{-\zeta}.$

Here, the third inequality follows since
$|{\mathcal{R}}|\leq|{\mathcal{B}}^{\prime}|\leq e^{\zeta}$. This completes
the proof of soundness, and as a result, the proof of correctness of
$\mathsf{Alg}{\mathsf{Gen}}$. We now turn to analyze the space complexity of
$\mathsf{Alg}{\mathsf{Gen}}$, excluding the space used by the calls to
algorithms ${\mathsf{Alg}}\mathsf{Jump}{(j)}$ and
${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$.

###### Space Complexity.

Recall that our algorithm $\mathsf{Alg}{\mathsf{Gen}}$ is given as input a
level-$j$ stream-block $B\in{\mathcal{B}}$ and a region
${\mathcal{R}}\subseteq{\mathcal{B}}^{\prime}$. We assume that we are given
${\mathcal{R}}$ by providing us with the indices of the first and last range-
blocks in ${\mathcal{R}}$ in the level-$j$ partition $\tilde{\mathcal{B}}_{j}$
of the range $H^{*}$. Similarly, we are given the index of $B$ in the
level-$j$ partition ${\mathcal{B}}_{j}$ of the original input stream $S$.
Thus, we have stored the descriptions of $B$ and ${\mathcal{R}}$ in $O(1)$
units of space. We perform a number of calls to level-$j$ and level-$\ell$
algorithms ${\mathsf{Alg}}\mathsf{Jump}{(j)}$ and
${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$ respectively. Our goal is to analyze the
space complexity of $\mathsf{Alg}{\mathsf{Gen}}$, excluding the space used by
such calls to these algorithms.

Before processing the elements of $B$, we initialize the multiset
${\mathcal{B}}_{\mathsf{prom}}\leftarrow\emptyset$ of pseudo-promising range-
blocks and the set ${\mathcal{B}}_{\mathsf{susp}}\leftarrow\emptyset$ of
pseudo-suspicious range-blocks. As we process the elements of the stream-block
$B$, we mark certain range-blocks of ${\mathcal{R}}$ pseudo-promising by
appending them to the multiset ${\mathcal{B}}_{\mathsf{prom}}$. Similarly, we
also mark certain range-blocks of ${\mathcal{R}}$ pseudo-suspicious by
appending them to the set ${\mathcal{B}}_{\mathsf{susp}}$. As mentioned
earlier, the space used in maintaining ${\mathcal{B}}_{\mathsf{prom}}$ and
${\mathcal{B}}_{\mathsf{susp}}$ is trivially upper bounded by
$|{\mathcal{B}}_{\mathsf{prom}}|+|{\mathcal{B}}_{\mathsf{susp}}|$, which again
is bounded by the number of elements that we sample in $B$ with values in the
range-blocks of ${\mathcal{R}}$. Indeed, a range-block
$B^{\prime}\in{\mathcal{R}}$ may be marked pseudo-promising only if an element
in $B\cap B^{\prime}$ was sampled. Moreover, each entry of such a pseudo-
promising range-block in the multiset ${\mathcal{B}}_{\mathsf{prom}}$ can be
charged to a unique sampled element of $B\cap B^{\prime}$. Similarly, each
pseudo-suspicious range-block in ${\mathcal{B}}_{\mathsf{susp}}$ can also be
charged to a unique sampled element of $B\cap B^{\prime}$. Recall that at any
point, if we sample more $12\zeta p|\hat{\mathcal{B}}|$ stream-blocks of
$\hat{\mathcal{B}}$, we immediately terminate the algorithm
$\mathsf{Alg}{\mathsf{Gen}}$. Furthermore, for each sampled stream-block
$\hat{B}\in\hat{\mathcal{B}}$, we sample at most $E^{*}_{\ell}$ of its
elements. Thus, the space used in storing ${\mathcal{B}}_{\mathsf{prom}}$ and
${\mathcal{B}}_{\mathsf{susp}}$ is
$O(|{\mathcal{B}}_{\mathsf{prom}}|+|{\mathcal{B}}_{\mathsf{susp}}|)=O(\zeta
pE^{*}_{\ell}|\hat{\mathcal{B}}|)$.

We now turn to analyze the space used in updating
${\mathcal{B}}_{\mathsf{prom}}$ and ${\mathcal{B}}_{\mathsf{susp}}$ at the end
of each level-$\ell$ stream-block. Notice that the space used in maintaining
${\mathcal{B}}_{\mathsf{prom}}$ can be charged to the space freed after the
respective calls to level-$\ell$ algorithm
${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$ terminate. Thus, we do not need any
additional space for this step. It is also immediate to verify that we need
only $O(|{\mathcal{B}}_{\mathsf{prom}}|)$ additional space to maintain the set
${\mathcal{B}}_{\mathsf{susp}}$ of suspicious blocks. Finally, the space used
to compute the output region ${\mathcal{R}}^{\prime}$ can be charged to the
space freed after the respective calls to level-$j$ algorithm
${\mathsf{Alg}}\mathsf{Jump}{(j)}$ terminate. Thus, the total space used by
$\mathsf{Alg}{\mathsf{Gen}}$, excluding the space used by the calls to
${\mathsf{Alg}}\mathsf{Jump}{(j)}$ and ${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$
is at most

$\displaystyle O\left(\zeta pE^{*}_{\ell}|\hat{\mathcal{B}}|\right)$
$\displaystyle=O\left(\zeta|\hat{\mathcal{B}}|\cdot
2^{7}\zeta\cdot\frac{Z_{\ell}}{Z_{j}}\cdot
2^{6}p^{\prime}Z_{\ell}\mu_{i}\right)$ $\displaystyle\leq
O\left(\zeta^{3}\cdot\eta^{\ell-j}\cdot\frac{Z_{\ell}^{2}}{Z_{j}^{2}}\cdot\frac{\mu_{i}}{\mu_{\ell}}\right).$

Here, the last inequality follows since $|\hat{\mathcal{B}}|=\eta^{\ell-j}$.

###### Concurrent calls to level-$j$ algorithm
${\mathsf{Alg}}\mathsf{Jump}{(j)}$.

We claim that throughout the run of $\mathsf{Alg}{\mathsf{Gen}}$, the number
of active calls to the level-$j$ algorithm ${\mathsf{Alg}}\mathsf{Jump}{(j)}$
is at most $O\left(\zeta\cdot\eta^{\ell-j}\right)$. Indeed, consider some
element $a_{t}\in B$. Let ${\mathcal{B}}_{\mathsf{active}}$ be the set of at
most $|\hat{\mathcal{B}}|$ active pseudo-suspicious range-blocks just after
processing $a_{t}$. The number of active calls to
${\mathsf{Alg}}\mathsf{Jump}{(j)}$ is then at most
$|{\mathcal{B}}_{\mathsf{active}}|\cdot{2^{6}\zeta}\leq
2^{6}\zeta|\hat{\mathcal{B}}|=O\left(\zeta\cdot\eta^{\ell-j}\right)$, as
claimed.

###### Concurrent calls to level-$\ell$ algorithm
${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$.

Recall that we do not count the contribution due to the level-$j$ algorithm
${\mathsf{Alg}}\mathsf{Jump}{(j)}$ to the number of concurrent calls to the
level-$\ell$ algorithm ${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$. Consider a
level-$\ell$ stream-block $\hat{B}\in\hat{\mathcal{B}}$. If it is not marked,
we do not perform any calls to ${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$ in which
$\hat{B}$ participates. If it is marked, we process the elements of $\hat{B}$
with values in the range-blocks of ${\mathcal{R}}$, marking each such element
independently at random with probability $p^{\prime}$ each. If some element
$a_{t}$ of $\hat{B}$ with value in the level-$\ell$ range-block
$\hat{B}^{\prime}$ is marked, we perform a call to the level-$\ell$ algorithm
${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$ with input level-$\ell$ pair
$(\hat{B},\hat{B}^{\prime})$ and the subblock $\hat{B}_{>t}$ of $\hat{B}$.
Recall that if we end up marking more than $E^{*}_{\ell}$ elements of
$\hat{B}$, we terminate all such calls to
${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$ in which $\hat{B}$ participates and
discard their computation. Thus, we perform at most

$\displaystyle E^{*}_{\ell}=2^{6}p^{\prime}Z_{\ell}\mu_{i}$
$\displaystyle=O\left(Z_{\ell}\mu_{i}\right)\cdot{\frac{2^{16}\zeta}{Z_{j}\mu_{\ell}}}=O\left(\frac{\zeta
Z_{\ell}\mu_{i}}{Z_{j}\mu_{\ell}}\right)$

calls to ${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$ in which $\hat{B}$
participates. This completes the analysis of $\mathsf{Alg}{\mathsf{Gen}}$ and
Lemma 4.5.35 now follows.

####  4.5.8 Special Case 4: Savable Levels have Large Weight

Recall that we have fixed parameters $N$ and $\eta$, both integral powers of
$2$, such that $\eta$ grows sufficiently slowly with $N$. We are given an LIS
problem instance $S$ in the streaming model, where $S$ is a permutation of the
range $H^{*}=(1,\ldots,N)$. Additionally, we are given an ensemble
$\Upsilon=(\Psi,\Psi^{\prime},\bm{Z},\bm{\Delta},\bm{\mu})$ of length $1+r$
where $r=r(N,\eta)=\left\lfloor\frac{\log N}{\log\eta}\right\rfloor$,
$\Psi=\Psi^{*}(N,\eta)=(\eta,\ldots,\eta)$,
$\Psi^{\prime}=(\psi_{1},\ldots,\psi_{r})$, $\bm{Z}=(Z_{0},\ldots,Z_{r})$,
$\bm{\Delta}=(\Delta_{0},\ldots,\Delta_{r})$, and
$\bm{\mu}=(\mu_{0},\ldots,\mu_{r})$. We let
${\mathcal{I}}=\left\\{0,\ldots,r\right\\}$ be the set of the levels of the
underlying hierarchical partitions ${\mathcal{B}}_{\Psi}(S)$ of $S$ into
stream-blocks and ${\mathcal{B}}_{\Psi^{\prime}}(H^{*})$ of $H^{*}$ into
range-blocks. We have also fixed an optimal $\Upsilon$-canonical subsequence
$S^{*}$ of $S$. Note that we do not explicitly know $S^{*}$ before processing
the sequence $S$. If $S$ is indeed a Yes-Instance, then $|S^{*}|=Z_{0}$. On
the other hand, if $S$ is a No-Instance, then there is no $\Upsilon$-canonical
subsequence $S^{*}$ of $S$, and hence, $S^{*}=\emptyset$.

We have also assumed the existence of the algorithm
$\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ for the NCM problem in the hybrid
model with the following guarantees. Given an NCM instance
$G=(L,R,E_{\mathsf{advice}},E)$ in the hybrid model and a parameter $\gamma$
with $|L|=|R|$, $\gamma\geq\left(d(G)\right)^{10^{-3}}$, and
$d(G)\geq|G|^{10^{-9}}$, it solves
$(\gamma|L|,\gamma|L|/\alpha_{\mbox{{\scriptsize{NCM}}}}(|G|))$-gap NCM
problem with per-vertex query complexity $\left(d(G)\right)^{1-\delta}$, where
$\alpha_{\mbox{{\scriptsize{NCM}}}}(|G|)=|G|^{o(1)}$. In this subsection, we
will use this algorithm $\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ as a
subroutine on a number of carefully crafted NCM instances in the hybrid model.
We fix
${\alpha^{*}:=\alpha_{\mbox{{\scriptsize{NCM}}}}\left(\eta^{10^{10}}\right)=\eta^{o(1)}}$.
We will ensure that each such instance $G=(L,R,E_{\mathsf{advice}},E)$ has
$|L|,|R|,d(G)\leq\eta^{10^{9}}$. Hence, for each such instance $G$, we have
$\alpha_{\mbox{{\scriptsize{NCM}}}}(|G|)\leq\alpha^{*}$.

Recall that we have fixed $\epsilon=\delta/10^{12}$. From Assumptions 4.5.5
and 4.5.9, we assume w.l.o.g. that $X_{i}/Z_{i}>N^{1/2-\epsilon}$ for all
levels $0\leq i<(1/2-\epsilon)r$ and $\Delta_{i}<Z_{i}N^{5\epsilon}$ for all
levels $3\epsilon r\leq i<(1/2-\epsilon)r$. Recall that in Section 4.5.3 we
have fixed a threshold-level $r^{*}=\left\lfloor(1/2-4\epsilon)r\right\rfloor$
and the set
${\mathcal{I}}^{*}=\left\\{i_{0},\ldots,i_{k^{*}}\right\\}\subseteq{\mathcal{I}}$
of special levels. In the special case that we deal in this subsection, we are
given a set ${\mathcal{I}}_{\mathsf{savable}}\subseteq{\mathcal{I}}^{*}$ of
savable levels with weight $w_{{\mathcal{I}}_{\mathsf{savable}}}\geq
r/10^{5}$. Our goal is to obtain an $N^{o(1)}$-canonical distinguisher
algorithm ${\mathsf{AlgCase}}_{\mathsf{4}}$ with space complexity
$N^{1/2-\epsilon}$. This subsection is dedicated to the proof of the following
lemma.

######  Lemma 4.5.45.

Suppose we are given parameters $N$ and $\eta$, both integral powers of $2$,
along with an ensemble
$\Upsilon=(\Psi,\Psi^{\prime},\bm{Z},\bm{\Delta},\bm{\mu})$ of length $1+r$
along with a set ${\mathcal{I}}_{\mathsf{savable}}$ of its savable levels with
weight $w_{{\mathcal{I}}_{\mathsf{savable}}}\geq r/10^{5}$ as mentioned above.
Further assume that we are given an algorithm
$\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ that satisfies the guarantees of
Theorem 4.1.1. Then there is a $N^{o(1)}$-canonical distinguisher algorithm
${\mathsf{AlgCase}}_{\mathsf{4}}$ with space complexity $N^{1/2-\epsilon}$.

Similar to Section 4.5.3, we will create a collection of $1+k^{*}$ different
algorithms, where each algorithm corresponds to a level
$i_{k}\in{\mathcal{I}}^{*}$. These algorithms will be parameterized by the
relevant parameters of the respective levels, and hence, it will be convenient
to describe them based on the levels at which they operate. Consider some
level $i\in{\mathcal{I}}^{*}$, and we denote the corresponding level level-$i$
algorithm by $\mathsf{Alg}\mathsf{Savable}{(i)}$. As in Section 4.5.3,
$\mathsf{Alg}\mathsf{Savable}{(i)}$ takes as an input a level-$i$ pair
$(B^{*},B^{*^{\prime}})$ and a subblock $B^{**}$ of $B^{*}$. It is given the
description of $(B^{*},B^{*^{\prime}})$ by giving it the indices of these
blocks $B^{*}$ and $B^{*^{\prime}}$ in the level-$i$ partitions
${\mathcal{B}}^{i}_{\Psi}$ and ${\mathcal{B}}^{i}_{\Psi^{\prime}}$
respectively. Next, it has access to the elements of $B^{**}$ as they arrive
as a part of the original input sequence $S$. We will ensure that
$\mathsf{Alg}\mathsf{Savable}{(i)}$ is an
$(\alpha_{i},\alpha^{\prime}_{i})$-canonical distinguisher algorithm for
$\alpha_{i}=4$ and
$\alpha^{\prime}_{i}=\left(16\alpha^{*}\log\eta\right)^{(r^{*}-i)+1}$.
Additionally, we recall that for each pair $i_{k}<i_{k^{\prime}}$ of levels of
${\mathcal{I}}^{*}$, we have fixed a parameter
$\zeta(i_{k},i_{k^{\prime}})=\ln{\left(\eta^{2(i_{k^{\prime}}-i_{k})}\cdot\psi_{i_{k+1}}\ldots\psi_{i_{k^{\prime}}}\right)}$.
We introduce the following additional definition.

###### Perfectly savable levels.

We say that a savable level $i=i_{k}\in{\mathcal{I}}_{\mathsf{savable}}$ is
_perfectly savable_ iff it satisfies the following properties: (i) $k\leq
k^{*}-2$; (ii) $i_{k+1}=i+1$ and $i_{k+2}=i+2$; (iii)
$\frac{Z_{i}}{Z_{i+1}}\geq\eta^{3/4}$ and
$\frac{Z_{i+1}}{Z_{i+2}}\geq\eta^{3/4}$; and (iv)
$\psi_{i+1}\leq\eta^{10^{8}}$;

######  Claim 4.5.46.

There is a set ${\mathcal{I}}^{\prime}_{\mathsf{savable}}$ of perfectly
savable levels with weight
$w_{{\mathcal{I}}^{\prime}_{\mathsf{savable}}}>r/10^{6}$.

The proof of this claim follows from standard techniques is deferred to
Section C.2.6.1. Next, we discard from ${\mathcal{I}}_{\mathsf{savable}}$ all
levels that are not perfectly savable, but still refer to the resulting set as
${\mathcal{I}}_{\mathsf{savable}}$. We are now ready to provide the
description of our level-$i$ algorithm $\mathsf{Alg}\mathsf{Savable}{(i)}$.

######  $\mathsf{Alg}\mathsf{Savable}{(i)}$ for levels
$i\in{\mathcal{I}}^{*}\backslash{\mathcal{I}}_{\mathsf{savable}}$.

In this case, our algorithm $\mathsf{Alg}\mathsf{Savable}{(i)}$ is identical
to the algorithm ${\mathsf{Alg}}\mathsf{Level}{(i)}$ from LABEL:{lem:_ncm-
simple-lis-main} discussed in Section 4.5.3, with one exception. Recall that
if $k<k^{*}$, the algorithm ${\mathsf{Alg}}\mathsf{Level}{(i)}$ is allowed to
the level-$i_{k+1}$ algorithm ${\mathsf{Alg}}\mathsf{Level}{(i_{k+1})}$ as a
subroutine. In our updated algorithm $\mathsf{Alg}\mathsf{Savable}{(i)}$, we
substitute each of these calls with the corresponding calls to
$\mathsf{Alg}\mathsf{Savable}{(i_{k+1})}$. From LABEL:{lem:_ncm-simple-lis-
main}, we immediately deduce the following observation, that is similar to
Observation 4.5.28:

######  Observation 4.5.47.

Assume that $k<k^{*}$ and for the level $j:=i_{k+1}$ we are given a level-$j$
$(4,\alpha^{\prime}_{j})$-canonical distinguisher algorithm
$\mathsf{Alg}\mathsf{Savable}{(j)}$. Then, there is a level-$i$
$(\alpha_{i},\alpha^{\prime}_{i})$-canonical distinguisher algorithm
$\mathsf{Alg}\mathsf{Savable}{(i)}$ that achieves the following guarantees:

  * •

Calls to $\mathsf{Alg}\mathsf{Savable}{(j)}$: it performs at most
$\zeta^{2}(i,j)\frac{\mu_{i}}{\mu_{j}}$ concurrent calls to the level-$j$
algorithm $\mathsf{Alg}\mathsf{Savable}{(j)}$; and

  * •

Space complexity: its space complexity, excluding the space required by the
calls to $\mathsf{Alg}\mathsf{Savable}{(j)}$ is at most $N^{6\epsilon}$.

This completes the description of our algorithm
$\mathsf{Alg}\mathsf{Savable}{(i)}$ for the levels of ${\mathcal{I}}^{*}$ that
are not perfectly savable. We now focus on the perfectly savable levels.

######  $\mathsf{Alg}\mathsf{Savable}{(i)}$ for levels
$i\in{\mathcal{I}}_{\mathsf{savable}}$.

In this case, we show the following algorithm, whose analysis is present in
Section 4.5.9 after we complete the description of
${\mathsf{AlgCase}}_{\mathsf{4}}$ assuming it.

######  Lemma 4.5.48.

Fix a perfectly savable level $i:=i_{k}\in{\mathcal{I}}_{\mathsf{savable}}$
and $j:=i_{k+1}$. Assume that we are given a level-$j$
$(\alpha_{j},\alpha^{\prime}_{j})$-canonical distinguisher algorithm
$\mathsf{Alg}\mathsf{Savable}{(j)}$. Further assume that we are given an
algorithm $\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ that satisfies the
guarantees of Theorem 4.1.1. Then, there is a level-$i$
$(\alpha_{i},\alpha^{\prime}_{i})$-canonical distinguisher algorithm
$\mathsf{Alg}\mathsf{Savable}{(i)}$ that achieves the following guarantees:

  * •

Calls to $\mathsf{Alg}\mathsf{Savable}{(j)}$: it performs at most
$\frac{\zeta^{6}}{\eta^{0.9\delta}}\cdot\frac{\mu_{i}}{\mu_{j}}$ concurrent
calls to $\mathsf{Alg}\mathsf{Savable}{(j)}$; and

  * •

Space complexity: its space complexity, excluding the space required by the
calls to $\mathsf{Alg}\mathsf{Savable}{(j)}$, is at most $N^{o(1)}$.

We are now ready to describe our LIS algorithm for this subsection. Applying
Observation 4.5.47 and Lemma 4.5.48 for the levels of ${\mathcal{I}}^{*}$ in
their decreasing order, we obtain a level-$i_{0}$
$(\alpha_{0},\alpha^{\prime}_{0})$-canonical distinguisher algorithm
$\mathsf{Alg}\mathsf{Savable}{(i_{0})}$. We prove the following claim after
describing ${\mathsf{AlgCase}}_{\mathsf{4}}$ assuming it.

######  Claim 4.5.49.

The space complexity of ${\mathsf{Alg}}\mathsf{Level}{(i_{0})}$ is
$N^{1/2-\epsilon}$.

From LABEL:{obs:_ncm-alglevel-0-suffices}, there is a
$\alpha^{\prime}_{0}$-canonical distinguisher algorithm
${\mathsf{AlgCase}}_{\mathsf{4}}$ that performs at most $N^{o(1)}$ concurrent
calls to $\mathsf{Alg}\mathsf{Savable}{(i_{0})}$ and whose space complexity,
excluding the space required by the calls to
$\mathsf{Alg}\mathsf{Savable}{(i_{0})}$, is at most $N^{o(1)}$. Notice that

$\alpha^{\prime}_{0}=\left(16\alpha^{*}\log\eta\right)^{r^{*}+1}\leq\left(16\alpha^{*}\log\eta\right)^{\frac{\log
N}{\log\eta}}\leq N^{\frac{\log\alpha^{*}}{\log\eta}+o(1)}\leq N^{o(1)}.$

This completes the description of the algorithm
${\mathsf{AlgCase}}_{\mathsf{4}}$ for this special case and LABEL:{lem:_ncm-
ncm-lis-reduction-main} follows assuming LABEL:{lem:_ncm-savable-savable} and
LABEL:{clm:_ncm-savable-level-0-space}. This also completes the proof of
Theorem 4.1.1. In the remainder of this subsection, we prove Claim 4.5.49,
while the proof of Lemma 4.5.45 is deferred to Section 4.5.9.

Proof of Claim 4.5.49. We proceed as in LABEL:{subsec:_ncm-simpler-lis-stream}
and LABEL:{subsec:_ncm-jumpable}. Consider a level $i\in{\mathcal{I}}^{*}$ and
fix a level-$i$ stream-block $B$ in the level-$i$ partition
${\mathcal{B}}_{\Psi}^{i}$. While executing
$\mathsf{Alg}\mathsf{Savable}{(i_{0})}$, we also execute a number of calls to
the level-$i$ algorithm $\mathsf{Alg}\mathsf{Savable}{(i)}$ in which $B$
participates. We denote by $\mathsf{load}(B)$ the maximum number of such
concurrent calls to $\mathsf{Alg}\mathsf{Savable}{(i)}$ in which $B$
participates. We denote by
$\mathsf{load}(i):=\max_{B\in{\mathcal{B}}_{\Psi}^{i}}{\left(\mathsf{load}(B)\right)}$
the maximum ‘load’ across all level-$i$ stream-blocks. To analyze the load, we
need the following additional parameters.

For each level $i_{k}\in{\mathcal{I}}^{*}$, we have two parameters
$q_{1}(i_{k})$ and $q_{2}(i_{k})$, whose values are defined recursively as
follows. We let $q_{1}(i_{0})=1$ and $q_{2}(i_{0})=1$. Consider now a level
$i_{k}\in{\mathcal{I}}^{*}$ with $0<k\leq k^{*}$. We let
$q_{1}(i_{k})=q_{1}(i_{k-1})\cdot\zeta^{6}(i_{k-1},i_{k})$. If
$i_{k-1}\in{\mathcal{I}}_{\mathsf{savable}}$, we let
$q_{2}(i_{k})=\frac{q_{2}(i_{k-1})}{\eta^{0.9\delta}}$ and
$q_{2}(i_{k})=q_{2}(i_{k-1})$ otherwise. For each level
$i_{k}\in{\mathcal{I}}^{*}$, we also define
$L^{*}(i_{k})=\frac{q_{1}(i_{k})}{q_{2}(i_{k})}\cdot\frac{\mu_{i_{0}}}{\mu_{i_{k}}}$.
We use the following two claims, whose proofs follow those of LABEL:{clm:_ncm-
jump-load-induction} and LABEL:{{clm:_ncm-load-i-small}}, and are deferred to
LABEL:{prf-clm:_ncm-savable-load-induction} and LABEL:{prf-clm:_ncm-savable-
load-i-small} respectively.

######  Claim 4.5.50.

For each level $i_{k}\in{\mathcal{I}}^{*}$, $\mathsf{load}(i_{k})\leq
L^{*}(i_{k})$.

######  Claim 4.5.51.

For each level $i_{k}\in{\mathcal{I}}^{*}$, $\L^{*}(i_{k})\leq
N^{\frac{1}{2}-\frac{\delta}{10^{9}}}$.

We are now ready to analyze the space complexity of
$\mathsf{Alg}\mathsf{Savable}{(i_{0})}$. We consider its state when processing
some element $a_{t}\in S$. Consider a level $i=i_{k}\in{\mathcal{I}}^{*}$ and
let $B_{i}\in{\mathcal{B}}^{i}_{\Psi}$ be the unique level-$i$ stream-block
that contains $a_{t}$. Observe that $B_{i}$ participates in all the active
calls to the level-$i$ algorithm $\mathsf{Alg}\mathsf{Savable}{(i)}$. Hence,
there are at most $\mathsf{load}(i)$ active calls to
$\mathsf{Alg}\mathsf{Savable}{(i)}$.

We first consider the case where
$i_{k}\not\in{\mathcal{I}}_{\mathsf{savable}}$. From the guarantee of
Observation 4.5.47, the space complexity used by such an execution of
$\mathsf{Alg}\mathsf{Savable}{(i)}$, excluding the space required by the calls
to lower level algorithms, is at most $N^{6\epsilon}$. From LABEL:{clm:_ncm-
savable-load-induction} and LABEL:{clm:_ncm-savable-load-i-small}, the
contribution to the space complexity of
$\mathsf{Alg}\mathsf{Savable}{(i_{0})}$ due to this level is,

$\begin{split}\mathsf{load}(i)\cdot N^{6\epsilon}&\leq L^{*}(i)\cdot
N^{6\epsilon}\\\ &\leq N^{\frac{1}{2}-\frac{\delta}{10^{9}}}\cdot
N^{6\epsilon}=N^{\frac{1}{2}-\frac{\delta}{10^{9}}+6\epsilon}\leq
N^{\frac{1}{2}-2\epsilon},\end{split}$ (4.20)

since $\epsilon=\delta/10^{12}$. We now consider the remaining case where
$i\in{\mathcal{I}}_{\mathsf{savable}}$. From the guarantee of Lemma 4.5.48,
the space complexity used by such an execution of
$\mathsf{Alg}\mathsf{Savable}{(i)}$, excluding the space required by the calls
to lower level algorithms, is at most $N^{o(1)}$. As before, we can now bound
the contribution due to level $i$ to the space complexity of
$\mathsf{Alg}\mathsf{Savable}{(i_{0})}$ by,

$\begin{split}\mathsf{load}(i)\cdot N^{o(1)}&\leq L^{*}(i)\cdot N^{o(1)}\\\
&\leq N^{\frac{1}{2}-\frac{\delta}{10^{9}}}\cdot
N^{o(1)}=N^{\frac{1}{2}-\frac{\delta}{10^{9}}+o(1)}\leq
N^{\frac{1}{2}-2\epsilon},\end{split}$ (4.21)

since $\epsilon=\delta/10^{12}$. From LABEL:{eqn:_ncm-savable-bound-one} and
LABEL:{eqn:_ncm-savable-bound-two}, we now conclude that the space complexity
of $\mathsf{Alg}\mathsf{Savable}{(i_{0})}$ is indeed bounded by,

$|{\mathcal{I}}^{*}|\cdot N^{1/2-2\epsilon}<r\cdot
N^{1/2-2\epsilon}<N^{1/2-\epsilon}.$

Here, the last inequality follows since $r<\log N$ and $\epsilon$ is a
constant. This completes the analysis of the space complexity of
$\mathsf{Alg}\mathsf{Savable}{(i_{0})}$, completing the proof of Claim 4.5.49.
$\Box$

####  4.5.9 $\mathsf{Alg}\mathsf{Savable}{(i)}$ and its Properties — Proof of
Lemma 4.5.48

We are given a perfectly savable level
$i:=i_{k}\in{\mathcal{I}}_{\mathsf{savable}}$. We are also given a level
$j:=i_{k+1}=i+1$ of ${\mathcal{I}}^{*}$ along with a level-$j$
$(\alpha_{j},\alpha^{\prime}_{j})$-canonical distinguisher algorithm
$\mathsf{Alg}\mathsf{Savable}{(j)}$. Our goal is to prove Lemma 4.5.48 by
devising a level-$i$ $(\alpha_{i},\alpha^{\prime}_{i})$-canonical
distinguisher algorithm $\mathsf{Alg}\mathsf{Savable}{(i)}$ with low space
complexity that performs a small number of calls to
$\mathsf{Alg}\mathsf{Savable}{(j)}$. Recall that the input to
$\mathsf{Alg}\mathsf{Savable}{(i)}$ is a level-$i$ pair
$(B^{*},B^{*^{\prime}})$ and a subblock $B^{**}$ of $B^{*}$.

We consider the collection ${\mathcal{B}}$ of level-$j$ descendant stream-
blocks of $B^{*}$ that are entirely contained in $B^{**}$. We also consider
the collection ${\mathcal{B}}^{\prime}$ of level-$j$ descendant range-blocks
of $B^{*^{\prime}}$. We first claim that if
${\mathcal{B}}<\frac{Z_{i}}{2\alpha_{i}Z_{j}}$, we can report no. Indeed, if
that is the case, $B^{**}$ shares elements with fewer than
$\frac{Z_{i}}{2\alpha_{i}Z_{j}}+2\leq\frac{Z_{i}}{\alpha_{i}Z_{j}}$ level-$j$
blocks. Here, the inequality follows from the fact that $\alpha_{i}=4$ and
Property P4 of the ensemble $\Upsilon$. But then, $B^{**}$ must contain fewer
than $\frac{Z_{i}}{\alpha_{i}Z_{j}}\cdot Z_{j}=\frac{Z_{i}}{\alpha_{i}}$
elements of each $\Upsilon$-canonical subsequence, and in particular, of
$S^{*}$. Thus, assume from now on that
$|{\mathcal{B}}|\geq\frac{Z_{i}}{2\alpha_{i}Z_{j}}\geq\frac{\eta^{3/4}}{8}$.
Here, the last inequality follows since $\alpha_{i}=4$ and
$\frac{Z_{i}}{Z_{j}}=\frac{Z_{i}}{Z_{i+1}}\geq\eta^{3/4}$ since $i$ is a
perfectly savable level. On the other hand, we have
$|{\mathcal{B}}^{\prime}|=\psi_{j}=\psi_{i+1}\leq\eta^{\max{\left\\{\eta^{2},\psi_{i+1}\right\\}}}$.
Recall that we have defined
$\zeta(i_{k},i_{k+1})=\zeta(i,j)=\ln{\left(\eta^{2}\cdot\psi_{i+1}\right)}$.
For readability, we denote $\zeta:=\zeta(i,j)$ from now on. Notice that,

$2\ln\eta\leq\zeta\leq\ln{\left(\eta^{2+10^{8}}\right)}\leq\left(2\cdot
10^{8}\right)\ln\eta.$ (4.22)

Before describing our algorithm $\mathsf{Alg}\mathsf{Savable}{(i)}$, we define
a number of instances of the NCM problem in the hybrid model. We will use the
algorithm $\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ as an oracle on these
carefully crafted instances. We consider $\log\eta$ different NCM problem
instances: for each $\tau\in\left\\{2^{0},\ldots,2^{\log{(\eta)}-1}\right\\}$,
there is an instance
$G^{(\tau)}=(L^{(\tau)},R^{(\tau)},E^{(\tau)}_{\mathsf{advice}},E^{(\tau)})$
of the NCM problem in the hybrid model that is probabilistically obtained as
follows.

###### The set $L^{(\tau)}$ of left-vertices.

For each level-$j$ stream-block $B\in{\mathcal{B}}$, there is a collection
$L^{(\tau)}(B)$ of $\tau$ vertices obtained as follows. Consider the partition
${\mathcal{B}}^{(\tau)}(B)$ of $B$ into $\tau$ subblocks, that we denote by
${\mathcal{B}}^{(\tau)}(B)=\left\\{\tilde{B}_{1},\ldots,\tilde{B}_{\tau}\right\\}$
in their natural order. For each subblock
${\tilde{B}\in{\mathcal{B}}^{(\tau)}(B)}$, there is a unique vertex
$v{(\tilde{B})}$ in $L^{(\tau)}(B)$. These vertices appear in their natural
order:
$L^{(\tau)}(B)=\left(v(\tilde{B}_{1}),\ldots,v(\tilde{B}_{\tau})\right)$. Note
that
$\left|\bigcup_{B\in{\mathcal{B}}}L^{(\tau)}(B)\right|=|{\mathcal{B}}|\tau<\eta^{2}$.
The set $L^{(\tau)}$ now contains all the vertices $L^{(\tau)}(B)$ for each
level-$j$ stream-block $B\in{\mathcal{B}}$ in their natural order followed by
${\max{\left\\{\eta^{2},\psi_{i+1}\right\\}}}-|{\mathcal{B}}|\tau$ special
vertices. We will ensure that no edge of $E^{(\tau)}_{\mathsf{advice}}$, and
hence, of $E^{(\tau)}$ is incident on these special vertices. This completes
the description of our set $L^{(\tau)}$ of exactly
${\max{\left\\{\eta^{2},\psi_{i+1}\right\\}}}$ vertices.

###### The set $R^{(\tau)}$ of right-vertices.

For each level-$j$ range-block $B^{\prime}\in{\mathcal{B}}^{\prime}$, there is
a unique vertex $v(B^{\prime})$ in $R^{(\tau)}$. Note that
$\left|\bigcup_{B^{\prime}\in{\mathcal{B}}^{\prime}}\left\\{v(B^{\prime})\right\\}\right|=|{\mathcal{B}}^{\prime}|=\psi_{i+1}$.
The set $R^{(\tau)}$ now contains all such vertices in the natural order of
their underlying range-blocks followed by
${\max{\left\\{\eta^{2},\psi_{i+1}\right\\}}}-|{\mathcal{B}}^{\prime}|$
special vertices. As before, will ensure that no edge of
$E^{(\tau)}_{\mathsf{advice}}$, and hence, of $E^{(\tau)}$ is incident on
these special vertices. This completes the description of our set $R^{(\tau)}$
of exactly ${|L^{(\tau)}|={\max{\left\\{\eta^{2},\psi_{i+1}\right\\}}}}$
vertices.

###### The set $E^{(\tau)}_{\mathsf{advice}}$ of advice-edges.

The set $E^{(\tau)}_{\mathsf{advice}}$ does not contain any edge-slot incident
on special vertices of $L^{(\tau)}\cup R^{(\tau)}$. Consider now some vertex
$v(\tilde{B})\in L^{(\tau)}$ that is not special and let $B\in{\mathcal{B}}$
be the unique level-$j$ block that contains $\tilde{B}$. The set of advice-
edges $E^{(\tau)}_{\mathsf{advice}}$ incident to $v(\tilde{B})$ is obtained as
follows. Let $(\tilde{B}^{(1)},\tilde{B}^{(2)})$ be the partition of
$\tilde{B}$ into two equal subblocks. We sample the elements of
$\tilde{B}^{(1)}\cap B^{*^{\prime}}$ independently with probability
$p={\frac{2^{16}\zeta}{Z_{j}\mu_{j}}}$ each. For each level-$j$ range-block
$B^{\prime}\in{\mathcal{B}}^{\prime}$ whose value is sampled, we add the
corresponding edge $(v(\tilde{B}),v(B^{\prime}))$ to the set of advice-edges
incident to $v(\tilde{B})$. If we sample more than $d:=2^{6}pZ_{j}\mu_{i}$
elements from $\tilde{B}^{(1)}$, we discard all the advice-edges incident to
$v(\tilde{B})$ found so far, and report that there are no advice-edges
incident to it. This completes the description of set of advice-edges incident
to the vertex $v(\tilde{B})$. The final set of $E^{(\tau)}_{\mathsf{advice}}$
is the union of all such advice-edges.

###### The set $E^{(\tau)}$ of edges.

The set $E^{(\tau)}$ does not contain any edge absent from
$E^{(\tau)}_{\mathsf{advice}}$. Consider some vertex $v(\tilde{B})\in
L^{(\tau)}$ that is not special and let $B\in{\mathcal{B}}$ be the unique
level-$j$ block that contains $\tilde{B}$. Also consider the partition
$(\tilde{B}^{(1)},\tilde{B}^{(2)})$ of $\tilde{B}$ into two subblocks. The set
of ${E^{(\tau)}\subseteq E^{(\tau)}_{\mathsf{advice}}}$ edges incident to
$v(\tilde{B})$ is obtained as follows. For each level-$j$ range-block
$B^{\prime}\in{\mathcal{B}}^{*^{\prime}}$ such that there is an advice-edge
$(v(\tilde{B}),v(B^{\prime}))\in E^{(\tau)}_{\mathsf{advice}}$, we run
$\left\lfloor 2^{6}\zeta^{2}\right\rfloor$ independent instances of the
level-$j$ algorithm $\mathsf{Alg}\mathsf{Savable}{(j)}$ with input level-$j$
pair $(B,B^{\prime})$ along with the subblock $\tilde{B}^{(2)}$ of $B$. We say
that $(v(\tilde{B}),v(B^{\prime}))$ is an edge in $E^{(\tau)}$ iff at least
$2^{5}\zeta^{2}$ such executions of $\mathsf{Alg}\mathsf{Savable}{(j)}$ return
yes.

This completes the description of our NCM instance
$G^{(\tau)}=(L^{(\tau)},R^{(\tau)},E^{(\tau)}_{\mathsf{advice}},E^{(\tau)})$
for each $\tau\in\left\\{2^{0},\ldots,2^{\log{(\eta)}-1}\right\\}$. Before
describing our algorithm $\mathsf{Alg}\mathsf{Savable}{(i)}$, we analyze the
properties of these NCM instances.

###### Properties of $G^{(\tau)}$.

Fix some $\tau\in\left\\{2^{0},\ldots,2^{\log{(\eta)}-1}\right\\}$. We note
that the vertex-sets $L^{(\tau)}$ and $R^{(\tau)}$ are completely determined
by the input level-$i$ pair $(B^{*},B^{*^{\prime}})$ and the subblock $B^{**}$
of $B^{*}$. Consider now the corresponding NCM problem instance
$G^{(\tau)}=(L^{(\tau)},R^{(\tau)},E^{(\tau)}_{\mathsf{advice}},E^{(\tau)})$.
The advice-edge set $E^{(\tau)}_{\mathsf{advice}}$ of $G^{(\tau)}$ is a random
variable that depends solely on the randomness used in sampling the
corresponding elements of $B^{**}$. On the other hand, the edge set
$E^{(\tau)}$ of $G^{(\tau)}$ is a random variable that depends on both, on the
randomness used in sampling the corresponding elements of $B^{**}$ and the
randomness used by the corresponding calls to
$\mathsf{Alg}\mathsf{Savable}{(j)}$. It is worthwhile to note that
$G^{(\tau)}$ itself is a random variable independent of the randomness used by
(potentially multiple) executions of
$\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ with $G^{(\tau)}$ as input. Note
that the maximum vertex degree of $L$ for $E_{\mathsf{advice}}$ in
$G^{(\tau)}$ is at most $d$. We fix the parameter
$\gamma:=\frac{Z_{i}}{16Z_{j}\log\eta}$ and will subsequently use
$\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ with input $G^{(\tau)}$ to
distinguish between
$\mathsf{OPT}_{\mbox{{\scriptsize{NCM}}}}(G^{(\tau)})\geq\gamma$ from the case
where
$\mathsf{OPT}_{\mbox{{\scriptsize{NCM}}}}(G^{(\tau)})<\gamma/\alpha(G^{(\tau)})$.
To ensure that $\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ succeeds on this
decision problem, we need to ensure that $\gamma$ is large enough, as a
function of $d$. From our choice of $d=2^{6}pZ_{j}\mu_{i}$ and
$p={\frac{2^{16}\zeta}{Z_{j}\mu_{j}}}$, we immediately obtain,

$d=2^{6}pZ_{j}\mu_{i}=2^{6}\cdot\frac{2^{16}\zeta}{Z_{j}\mu_{j}}\cdot
Z_{j}\mu_{i}=2^{22}\zeta\frac{\mu_{i}}{\mu_{j}}=2^{22}\zeta\eta^{w_{i}}.$
(4.23)

From Equation 4.22 and the fact that $w_{i}<100$ since level-$i$ is a savable
level, we can upper bound $d$ by,

$d<O(\zeta)\cdot\eta^{w_{i}}<O(\ln\eta)\cdot\eta^{100}.$ (4.24)

Recall that $w_{i}>0.9$ and
${|G|=|L|\cdot|R|=\left({\max{\left\\{\eta^{2},\psi_{i+1}\right\\}}}\right)^{2}\leq\eta^{2\cdot
10^{8}}}$, since $i$ is a perfectly savable level. Plugging this inequalities
in LABEL:{eqn:_ncm-savable-d-eq-bound} to obtain a lower bound on $d$,

$d>\eta^{w_{i}}>\eta^{0.9}>|G|^{0.9/(2\cdot 10^{8})}>|G|^{10^{-9}}.$ (4.25)

Plugging Equation 4.24 in our choice of
$\gamma=\frac{Z_{i}}{16Z_{j}\log\eta}$, we now obtain,

$\gamma=\frac{Z_{i}}{16Z_{j}\log\eta}\geq\frac{\eta^{3/4}}{16\log\eta}>d^{10^{-3}}.$
(4.26)

Here, the first inequality follows since $\frac{Z_{i}}{Z_{j}}\geq\eta^{3/4}$
as $i$ is a perfectly savable level and the second inequality follows since
$\eta=\eta(N)=\omega(1)$ is an increasing function of $N$. From
LABEL:{eqn:_ncm-savable-d-lower-bound} and LABEL:{eqn:_ncm-savable-gamma-
lower-bound} along with our construction of $G^{(\tau)}$, we immediately
obtain the following observation.

######  Observation 4.5.52.

Fix an instance
$G^{(\tau)}=(L^{(\tau)},R^{(\tau)},E^{(\tau)}_{\mathsf{advice}},E^{(\tau)})$
of the NCM problem as detailed above. Then the algorithm
$\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ assumed in Lemma 4.5.48 with input
instance $G^{(\tau)}$ in the hybrid model distinguishes the case where
$\mathsf{OPT}_{\mbox{{\scriptsize{NCM}}}}(G^{(\tau)})\geq\gamma$ from the case
where
$\mathsf{OPT}_{\mbox{{\scriptsize{NCM}}}}(G^{(\tau)})<\gamma/\alpha^{*}$, with
per-vertex query complexity at most $d^{\left(1-\delta\right)}$, succeeding
with probability at least $2/3$. Here, the probability is solely over the
randomness used by $\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ and is
independent of the same used in the generation of the instance $G^{(\tau)}$.

This completes the analysis of the generated NCM problem instances. We are now
ready to describe our algorithm $\mathsf{Alg}\mathsf{Savable}{(i)}$ for
processing the input level-$i$ pair $(B^{*},B^{*^{\prime}})$ and the subblock
$B^{**}$ of $B^{*}$.

###### Description of $\mathsf{Alg}\mathsf{Savable}{(i)}$.

For each $\tau\in\left\\{2^{0},\ldots,2^{\log{(\eta)}-1}\right\\}$, we run
$\left\lfloor 2^{6}\zeta\right\rfloor$ independent instances of the algorithm
$\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ on the NCM problem instance
$G^{(\tau)}$ to distinguish between the case where
$\mathsf{OPT}_{\mbox{{\scriptsize{NCM}}}}(G^{(\tau)})\geq\gamma$ from the case
where
$\mathsf{OPT}_{\mbox{{\scriptsize{NCM}}}}(G^{(\tau)})<\frac{\gamma}{\alpha(G^{(\tau)})}$.
We report yes iff there is a
$\tau\in\left\\{2^{0},\ldots,2^{\log{(\eta)}-1}\right\\}$ such that at least
$2^{5}\zeta$ corresponding executions of
$\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ return yes. This completes the
description of our level-$i$ algorithm $\mathsf{Alg}\mathsf{Savable}{(i)}$.

It is immediate to see that the run of algorithm
$\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ on $G^{(\tau)}$ in the hybrid model
can be simulated in the streaming model while processing the elements of
$B^{**}$. Indeed, we know the vertices $L^{(\tau)}$ and $R^{(\tau)}$ before
processing the elements of $B^{**}$. We run the algorithm
$\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ on the instance $G^{(\tau)}$ in the
hybrid model as follows. Consider the time just before
$\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ starts to process some vertex
$v(\tilde{B})\in L^{(\tau)}$. Let $B\in{\mathcal{B}}$ be the unique level-$j$
stream-block that contains $\tilde{B}$. We will simulate the processing of
$\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ on $v(\tilde{B})$ while processing
the elements of $\tilde{B}$ as they arrive as the part of the sequence $S$.
Let $(\tilde{B}^{(1)},\tilde{B}^{(2)})$ be the partition of $\tilde{B}$ into
two subblocks, that we can compute before the arrival of elements of
$\tilde{B}$. We now compute the set of advice-edges
$E^{(\tau)}_{\mathsf{advice}}$ incident on $v(\tilde{B})$ while processing the
elements of $\tilde{B}^{(1)}$. We reveal this set of advice-edges to
$\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ and wait for the subset of advice-
edges that it choses to query. For each level-$j$ range-block $B^{\prime}$
such that $\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ chose to query the
advice-edge $(v(\tilde{B}),v(B^{\prime}))$, we run the algorithm
$\mathsf{Alg}\mathsf{Savable}{(j)}$ with input level-$j$ pair $(B,B^{\prime})$
and the subblock $\tilde{B}^{(2)}$ of $B$ while processing the elements of
$\tilde{B}^{(2)}$ as they arrive as a part of $B^{**}$. At the end of the
subblock $\tilde{B}^{(2)}$, we know which runs of $\mathsf{Alg}^{(j)}$
returned yes. We report the corresponding edges to
$\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ as edges of $E^{(\tau)}\cap
E^{(\tau)}_{\mathsf{advice}}$ and proceed to process subsequent vertices of
$L^{(\tau)}$. Thus, we can indeed simulate the run of algorithm
$\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ on $G^{(\tau)}$ in the hybrid model
while processing the elements of $B^{**}$ in the streaming model.

We now turn to analyze the properties of $\mathsf{Alg}\mathsf{Savable}{(i)}$,
starting with correctness guarantee.

###### Soundness guarantee.

Assume that $\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(B^{**}\cap
B^{*^{\prime}})<Z_{i}/\alpha^{\prime}_{i}$. Our goal is to show that we report
yes with probability less than $1/4$. For each
$\tau\in\left\\{2^{0},\ldots,2^{\log{(\eta)}-1}\right\\}$, we fix the
corresponding NCM problem instance $G^{(\tau)}$. Recall that $G^{(\tau)}$ is a
random variable and is independent of the randomness used by the executions of
$\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$. We let
${\mathcal{E}}_{\mathsf{bad}}(\tau)$ be the event that
$\mathsf{OPT}_{\mbox{{\scriptsize{NCM}}}}(G^{(\tau)})\geq\frac{Z_{i}/\alpha^{\prime}_{i}}{Z_{j}/\alpha^{\prime}_{j}}=\frac{\gamma}{\alpha^{*}}$.
We also let
${\mathcal{E}}_{\mathsf{bad}}:=\bigcup_{\tau\in\left\\{2^{0},\ldots,2^{\log{(\eta)}-1}\right\\}}{\mathcal{E}}_{\mathsf{bad}}(\tau)$
be the event that at least one of these events occur. We first bound the
probability that the event ${\mathcal{E}}_{\mathsf{bad}}$ occurs in the
following claim whose proof is deferred to Section C.2.6.4.

######  Claim 4.5.53.

$\text{\bf Pr}\left[{\mathcal{E}}_{\mathsf{bad}}\right]\leq 1/8$.

We assume from now on that the event ${\mathcal{E}}_{\mathsf{bad}}$ does not
occur, or in other words, for each
$\tau\in\left\\{2^{0},\ldots,2^{\log{(\eta)}-1}\right\\}$, the corresponding
NCM problem instance $G^{(\tau)}$ has
${\mathsf{OPT}_{\mbox{{\scriptsize{NCM}}}}(G^{(\tau)})<\frac{\gamma}{\alpha^{*}}\leq\frac{\gamma}{\alpha(G^{(\tau)})}}$.
Consider some $\tau\in\left\\{2^{0},\ldots,2^{\log{(\eta)}-1}\right\\}$. We
let ${\mathcal{E}}^{\prime}_{\mathsf{bad}}(\tau)$ be the event that at least
$2^{5}\zeta$ executions of $\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ with
input $G^{(\tau)}$ out of $\left\lfloor 2^{6}\zeta\right\rfloor$ independent
ones return yes. From Observation 4.5.52, for each such $\tau$ and the
corresponding instance $G^{(\tau)}$, an execution of
$\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ returns yes with probability at
most $1/3$. Thus, from Chernoff bound (4.2.4), ${\text{\bf
Pr}\left[{\mathcal{E}}^{\prime}_{\mathsf{bad}}(\tau)\>|\>\neg{\mathcal{E}}_{\mathsf{bad}}\right]\leq
e^{-3\zeta}}$. We denote by ${\mathcal{E}}^{\prime}_{\mathsf{bad}}$ the event
that there is a $\tau\in\left\\{2^{0},\ldots,2^{\log{(\eta)}-1}\right\\}$ such
that the event ${\mathcal{E}}^{\prime}_{\mathsf{bad}}(\tau)$ occurs. From
union bound, the probability that the event
${\mathcal{E}}^{\prime}_{\mathsf{bad}}$ occurs conditioned that the event
${\mathcal{E}}_{\mathsf{bad}}$ does not occur is at most ${\text{\bf
Pr}\left[{\mathcal{E}}^{\prime}_{\mathsf{bad}}\>|\>\neg{\mathcal{E}}_{\mathsf{bad}}\right]\leq\eta\cdot
e^{-3\zeta}\leq\eta\cdot\eta^{-6}\leq 1/8}$. Hence, ${\text{\bf
Pr}\left[{\mathcal{E}}^{\prime}_{\mathsf{bad}}\right]\leq\text{\bf
Pr}\left[{\mathcal{E}}_{\mathsf{bad}}\right]+\text{\bf
Pr}\left[{\mathcal{E}}^{\prime}_{\mathsf{bad}}\>|\>\neg{\mathcal{E}}_{\mathsf{bad}}\right]\leq
1/4}$. Recall that we report yes iff the event
${\mathcal{E}}^{\prime}_{\mathsf{bad}}$ occurs and the soundness guarantee of
$\mathsf{Alg}\mathsf{Savable}{(i)}$ now follows.

###### Completeness guarantee.

Recall that we have fixed an optimal $\Upsilon$-canonical increasing
subsequence $S^{*}$ of $S$. Assume that $(B^{*},B^{*^{\prime}})$ is a yes-pair
for $S^{*}$ and the subblock $B^{**}$ of $B^{*}$ contains at least
$\frac{Z_{i}}{2}$ elements of $S^{*}$. Our goal is to show that we report yes
with probability at least $3/4$. We use the following claim whose proof
follows standard techniques and is present in Section C.2.6.5.

######  Claim 4.5.54.

With probability at least $0.9$, there is some
$\tau\in\left\\{2^{0},\ldots,2^{\log{(\eta)}-1}\right\\}$ such that
$\mathsf{OPT}_{\mbox{{\scriptsize{NCM}}}}(G^{(\tau)})\geq\frac{Z_{i}}{16Z_{j}\log\eta}=\gamma$.

Assume from now on that this event indeed occurs. We fix such $\tau$ and
corresponding NCM problem instance $G^{(\tau)}$. From Observation 4.5.52, each
execution of $\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ with input
$G^{(\tau)}$ returns yes with probability at least $2/3$, where the
probability is over the randomness used by
$\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$. From Chernoff bound (4.2.4), it is
immediate to verify that with probability at least $0.9$, at least
$2^{5}\zeta^{2}$ executions of $\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ on
input $G^{(\tau)}$ report yes. Thus, we report yes with probability at least
$0.8$ and the completeness guarantee of $\mathsf{Alg}\mathsf{Savable}{(i)}$
follows.

###### Calls to ${\mathsf{Alg}}\mathsf{Jump}{(j)}$.

Consider a $\tau\in\left\\{2^{0},\ldots,2^{\log(\eta)-1}\right\\}$ and the
corresponding NCM problem instance
$G^{(\tau)}=(L^{(\tau)},R^{(\tau)},E^{(\tau)}_{\mathsf{advice}},E^{(\tau)})$.
We examine one out of $\left\lfloor 2^{6}\zeta\right\rfloor$ parallel runs of
$\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ that we execute with input
$G^{(\tau)}$. Consider a level-$j$ stream-block $B\in{\mathcal{B}}$ and a
partition ${\mathcal{B}}^{(\tau)}(B)$ of $B$ into $\tau$ subblocks. Finally,
consider a block $\tilde{B}\in{\mathcal{B}}^{(\tau)}(B)$ and its partition
$\left(\tilde{B}^{(1)},\tilde{B}^{(2)}\right)$ into $2$ subblocks. Notice that
when we are processing the block $\tilde{B}$, the subblock $\tilde{B}^{(2)}$
participates in all the ongoing calls to $\mathsf{Alg}\mathsf{Savable}{(j)}$.
Specifically, for each advice-edge incident to $v(\tilde{B})$ that is queried
by $\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$, we perform $\left\lfloor
2^{6}\zeta^{2}\right\rfloor$ calls to $\mathsf{Alg}\mathsf{Savable}{(j)}$ in
which $\tilde{B}^{(2)}$ participates. Recall that
$\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ performs at most $d^{1-\delta}$
such queries. Hence, the number of concurrent calls to
${\mathsf{Alg}}\mathsf{Jump}{(j)}$ is bounded by,

$\displaystyle\log{(\eta)}\cdot 2^{6}\zeta\cdot d^{1-\delta}\cdot
2^{6}\zeta^{2}$ $\displaystyle\leq O(\log\eta)\cdot\zeta^{3}\cdot
d^{1-\delta}$ $\displaystyle\leq
O(\log\eta)\cdot\zeta^{4}\cdot\eta^{(1-\delta)w_{i}}$ $\displaystyle\leq
O(\zeta^{5})\cdot\frac{\mu_{i}}{\mu_{j}}\cdot\frac{1}{\eta^{\delta w_{i}}}$
$\displaystyle\leq
O(\zeta^{5})\cdot\frac{\mu_{i}}{\mu_{j}}\cdot\frac{1}{\eta^{0.9\delta}}.$

Here, the second inequality follows from Equation 4.23 and the last inequality
follows since $i$ is a savable level and hence, $w_{i}>0.9$.

###### Space complexity.

We first analyze the space complexity of $\mathsf{Alg}\mathsf{Savable}{(i)}$
excluding the space used by the calls to
$\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ and
$\mathsf{Alg}\mathsf{Savable}{(j)}$. Consider a
$\tau\in\left\\{2^{0},\ldots,2^{\log(\eta)-1}\right\\}$ and the corresponding
NCM problem instance
$G^{(\tau)}=(L^{(\tau)},R^{(\tau)},E^{(\tau)}_{\mathsf{advice}},E^{(\tau)})$.
Consider one out of $\left\lfloor 2^{6}\zeta\right\rfloor$ parallel instances
of $\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ that we execute with input
$G^{(\tau)}$. Consider a vertex $v(\tilde{B})\in L^{(\tau)}$ and the
corresponding block $\tilde{B}$. Let $B\in{\mathcal{B}}$ be the level-$j$
stream-block containing $\tilde{B}$. It is immediate to verify that we can
compute the subset of advice edges incident to $v(\tilde{B})$ in space $O(d)$.
For each advice-edge that $\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ chose to
query, we execute a number of parallel instances of
$\mathsf{Alg}\mathsf{Savable}{(j)}$. It is also easy to see that we can charge
the space used in computing the edges to report to
$\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ to the space freed after the
respective calls to $\mathsf{Alg}\mathsf{Savable}{(j)}$ terminate. Thus, the
space used by $\mathsf{Alg}\mathsf{Savable}{(i)}$, excluding the space used by
the calls to $\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ and
$\mathsf{Alg}\mathsf{Savable}{(j)}$, is bounded by,

$\displaystyle\log{(\eta)}\cdot 2^{6}\zeta\cdot O(d)$ $\displaystyle\leq
O(\zeta^{2})\cdot d=O(\zeta^{2})\cdot
pZ_{j}\mu_{i}=O(\zeta^{3})\cdot\frac{\mu_{i}}{\mu_{j}}\leq
O(\zeta^{3})\cdot\eta^{100}<N^{o(1)}.$

Here, second-last inequality follows since $i$ is a savable level with weight
$w_{i}=\log_{\eta}{\left(\frac{\mu_{i}}{\mu_{j}}\right)}<100$. The last
inequality follows since $\zeta\leq\operatorname{poly}\log\eta$ and
$\eta=O(\log\log N)$ are small enough.

We now bound the space used by calls to
$\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$. Consider an execution of
$\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ with input NCM instance
$G^{(\tau)}=(L^{(\tau)},R^{(\tau)},E^{(\tau)}_{\mathsf{advice}},E^{(\tau)})$
It is immediate to verify that the space complexity of this execution is at
most
$2^{\operatorname{poly}(|G^{(\tau)}|)}=2^{\operatorname{poly}(|L^{(\tau)}|\cdot|R^{(\tau)}|)}=2^{\operatorname{poly}\left(\eta^{O(1)}\right)}=2^{\eta^{O(1)}}$.
But from our choice of $\eta=O(\log\log N)$, we can further bound this space
complexity by ${2^{\eta^{O(1)}}=2^{\operatorname{poly}\log\log N}=2^{o(\log
N)}=N^{o(1)}}$. Since we perform at most $\log(\eta)\cdot 2^{6}\zeta\leq
N^{o(1)}$ concurrent calls to $\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$, the
overall space used the calls to $\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ is
bounded by $N^{o(1)}$. We now conclude that the space complexity of
$\mathsf{Alg}\mathsf{Savable}{(i)}$, excluding the space used by the calls
$\mathsf{Alg}\mathsf{Savable}{(j)}$ is bounded by $N^{o(1)}$.

This completes the analysis of $\mathsf{Alg}\mathsf{Savable}{(i)}$ and
LABEL:{lem:_ncm-savable-savable} now follows.

###  4.6 Randomized LIS Algorithm in Streaming Model with
$\alpha$-approximation

The goal of this section is to prove Theorem 4.1.3. Consider an input stream
$S=(a_{1},\ldots,a_{N})$ for the LIS problem in streaming model consisting of
elements with values in the universe
${\mathcal{U}}=\left\\{1,\ldots,M\right\\}$. We assume that each element of
${\mathcal{U}}$ can be stored in unit space. As earlier, we also assume that
the length $N$ of the stream is an integral power of $2$, and is known to us
in advance. Given a parameter $\alpha\leq N^{1/4}$ such that $\alpha\geq
1+\epsilon$ for some constant $\epsilon$, our goal is to estimate
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)$ within a factor of $\alpha$
using at most $\tilde{O}(\sqrt{N}/\alpha)$ units of space. We assume that $N$
is large enough, so that, $\log N\geq 2^{32}$.

Note that in the case where $\alpha\leq\log^{12}N$, the (deterministic)
algorithm $\mathsf{Alg}_{3}$ from LABEL:{obs:_ncm-det-sqrt-n-space-sound}
already achieves factor-$(1+\epsilon)$ approximation in space $O(\sqrt{N})$.
Thus, we assume from now on that $\alpha>\log^{12}N$. Using the standard
techniques, it suffices to show the algorithm
$\mathsf{Alg}_{\mbox{{\scriptsize{LIS}}}}$ for the LIS problem, where, in
addition to the input sequence $S$, we are given a ‘guess’ $\tau^{*}$ for
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)$. Our goal is then to distinguish
the case where $\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)\geq\tau^{*}$ from
the case where $\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)<2\tau^{*}/\alpha$.
We thus assume that we are given such a guess $\tau^{*}$. If
$\tau^{*}\leq\sqrt{N}/\alpha$, we can use the algorithm $\mathsf{Alg}_{1}$
from Lemma 4.2.1 to distinguish the case where
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)\geq\tau^{*}$ from the case where
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)<\tau^{*}$ in space
$O(\tau^{*})=O(\sqrt{N}/\alpha)$. On the other hand, if
$\tau^{*}\geq\alpha\sqrt{N}$, we can use the algorithm $\mathsf{Alg}_{2}$ from
Lemma 4.2.2 to distinguish the case where
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)\geq\tau^{*}$ from the case where
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)<\tau^{*}/2$. The space complexity
of the algorithm $\mathsf{Alg}_{2}$ is
$\tilde{O}(N/\tau^{*})\leq\tilde{O}(\sqrt{N}/\alpha)$ as required. We assume
from now on that $\tau^{*}$ satisfies,

$\sqrt{N}/\alpha<\tau^{*}<\alpha\sqrt{N}.$ (4.27)

We set parameters $\frac{\tau^{*}}{2\alpha}<Z_{1}\leq\frac{\tau^{*}}{\alpha}$
and $\frac{Z_{1}}{\alpha}<Z_{2}\leq\frac{2Z_{1}}{\alpha}$, such that both,
$Z_{1}$ and $Z_{2}$ are integral powers of $2$. We also let
$\frac{\tau^{*}}{2\log^{9}N}<Z_{0}\leq\frac{\tau^{*}}{\log^{9}N}$ such that
$Z_{0}$ is an integral power of $2$. It is worthwhile to note that

$\frac{Z_{0}}{Z_{1}}\geq\frac{\tau^{*}/\log^{9}N}{\tau^{*}/\alpha}=\frac{\alpha}{\log^{9}N}$
(4.28)

We need the following observation that is analogous to the Partition Lemma
4.4.3 but optimized for two levels of hierarchical partition instead of an
arbitrary increasing number of levels.

######  Observation 4.6.1.

There are $\psi_{1}$ and $\psi_{2}$, both integral powers $2$, such that for
$\bm{Z}=(Z_{1},Z_{2})$ and $\Psi=(\psi_{1},\psi_{2})$, the resulting
hierarchical partition ${\mathcal{B}}_{\Psi}(S)$ of $S$ into $2$ levels of
stream-blocks achieves the following guarantee. There is an increasing
subsequence $S^{*}$ of $S$ of size at least
${\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)}/{\log^{9}N}$ that is
$\bm{Z}$-canonical w.r.t. the hierarchical partition
${\mathcal{B}}_{\Psi}(S)$.

The proof of this observation is similar to that of LABEL:{lem:_ncm-partition-
lemma} and LABEL:{lem:_ncm-vanilla-partition} and is present in Section
C.3.0.1. We are now ready to describe our algorithm of this section, that is
similar to the one of Section 4.5.6.

We fix the parameters $\psi^{*}_{1}$ and $\psi^{*}_{2}$ such that the
resulting hierarchical partition ${\mathcal{B}}_{\Psi^{*}}(S)$, where
$\Psi^{*}=(\psi^{*}_{1},\psi^{*}_{2})$, achieves the claimed guarantee of
Observation 4.6.1. Note that there are only $O(\log^{2}N)$ potential choices
of these parameters $\psi^{*}_{1}$ and $\psi^{*}_{2}$. Hence, at the cost of
multiplicative overhead of $O(\log^{2})$ in our space complexity, we run in
the following algorithm in parallel for all pairs of $\psi_{1}$ and
$\psi_{2}$, that are integral powers of $2$ in $\left\\{1,\ldots,N\right\\}$.
Let ${\mathcal{B}}^{1}={\mathcal{B}}^{1}_{\Psi}(S)$ and
${\mathcal{B}}^{2}={\mathcal{B}}^{2}_{\Psi}(S)$ be the partitions of the
resulting hierarchical partition ${\mathcal{B}}_{\Psi}(S)$ of $S$ into $2$
levels of stream-blocks. We also fix an optimal
$\bm{Z}=(Z_{1},Z_{2})$-canonical-increasing subsequence $S^{*}$ of $S$. Note
that if $\psi_{1}=\psi^{*}_{1}$ and $\psi_{2}=\psi^{*}_{2}$, the length of
$S^{*}$ is at least $\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)/\log^{9}N$.
Furthermore, if $S$ is a Yes-Instance, or in other words,
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)\geq\tau^{*}$, we have,

$|S^{*}|\geq\frac{\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)}{\log^{9}N}\geq\frac{\tau^{*}}{\log^{9}N}\geq
Z_{0}.$

It now suffices to show an algorithm that achieves the following guarantee. It
is given access to the original input sequence $S$ in the streaming model
along with parameters $\psi_{1}$, $\psi_{2}$, $\tau^{*}$, $Z_{0}$, $Z_{1}$,
and $Z_{2}$. If $\psi_{1}=\psi^{*}_{1}$, $\psi_{2}=\psi^{*}_{2}$, and $S$ is a
Yes-Instance, or in other words, there is an increasing subsequence $S^{*}$ of
size at least $Z_{0}$ that is $\bm{Z}$-canonical w.r.t. the partition
${\mathcal{B}}_{\Psi}(S)$, where $\Psi=(\psi_{1},\psi_{2})$ of $S$; then it
must report yes with probability at least $1-1/N$. On the other hand, the
probability that it report yes even though
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)<Z_{0}/\alpha$, is at most $1/N$
over the randomness used by our algorithm. We are now ready to describe our
algorithm.

We let $\Psi~{}=~{}(\psi_{1},\psi_{2})$ and consider the hierarchical
partition ${\mathcal{B}}_{\Psi}(S)=({\mathcal{B}}^{1},{\mathcal{B}}^{2})$ of
the stream $S$ into stream-blocks. We will process stream-blocks of
${\mathcal{B}}^{1}$ as they arrive as a part of the original input sequence
$S$. While processing these elements, we will maintain an ordered collection
$\tilde{\mathcal{R}}$ of at most $Z_{0}/Z_{1}$ disjoint non-empty blocks of
$H^{*}$. Let
$\mathsf{leftover}(\tilde{\mathcal{R}}):=H^{*}\backslash\bigcup_{R\in\tilde{\mathcal{R}}}R$
be the set of elements not appearing in the blocks of $\tilde{\mathcal{R}}$.
We will ensure that $\mathsf{leftover}(\tilde{\mathcal{R}})$ is also a
(possibly empty) range-block and the non-empty blocks of
$\tilde{\mathcal{R}}\cup\left\\{\mathsf{leftover}(\tilde{\mathcal{R}})\right\\}$
constitute a partition of the range $H^{*}$. We initialize this collection by
$\tilde{\mathcal{R}}\leftarrow\emptyset$ and hence,
$\mathsf{leftover}(\tilde{\mathcal{R}})=H^{*}$.

Consider a stream-block $B\in{\mathcal{B}}^{1}$ and let $\tilde{\mathcal{R}}$
be our collection of the blocks of $H^{*}$ just before processing the first
element of $B$. We also fix the special range-block
$\mathsf{leftover}(\tilde{\mathcal{R}})$. For each non-empty range-block
$R_{i}\in\tilde{\mathcal{R}}\cup\left\\{\mathsf{leftover}(\tilde{\mathcal{R}})\right\\}$,
we run the following procedure in parallel.

We mark each descendant stream-block $B^{\prime}$ of $B$ in
${\mathcal{B}}^{2}$ independently at random with probability
$p=\frac{Z_{2}}{Z_{1}}\log^{11}N=\frac{\log^{11}N}{\alpha}$ each. Consider a
stream-block $B^{\prime}\in{\mathcal{B}}^{2}$ that is marked. We run the
algorithm $\mathsf{Alg}_{1}$ from Lemma 4.2.1 with input $B^{\prime}\cap
R_{i}$ and the threshold $Z=Z_{2}$. If it reports yes, let
$v_{i}(B^{\prime})\in R_{i}$ be the element that it additionally reports. At
the end of the stream-block $B$, if at least one such execution returned yes,
we let $v_{i}(B)$ be the smallest of the corresponding reported elements.
Otherwise, we let $v_{i}(B)$ remain undefined. This completes the description
of our algorithm for processing the stream-sub-block $B^{\prime}$ and the
range-block $R_{i}$.

At the end of stream-block $B$, we are ready to update our collection
$\tilde{\mathcal{R}}$. Let $v_{\mathsf{leftover}}(B)$ be as computed by our
algorithm when processing the special region
$\mathsf{leftover}(\tilde{\mathcal{R}})$. If $\tilde{\mathcal{R}}=\emptyset$
and $v_{\mathsf{leftover}}(B)$ is left undefined, we do not update the regions
and let $\tilde{\mathcal{R}}=\emptyset$. Assume now on that either
$v_{\mathsf{leftover}}(B)$ is defined or $\tilde{\mathcal{R}}\neq\emptyset$
(or both).

###### Case $1$: $v_{\mathsf{leftover}}(B)$ is left undefined and
$\tilde{\mathcal{R}}\neq\emptyset$.

Let $\tilde{\mathcal{R}}=(R_{1},\ldots,R_{k})$ be the range-blocks of our
collection in their natural order, where $k=|\tilde{\mathcal{R}}|$. Since we
ensure that $|\tilde{\mathcal{R}}|\leq Z_{0}/Z_{1}$, we have $1\leq k\leq
Z_{0}/Z_{1}$. In this case, we will ensure that after the update, the
resulting collection $\tilde{\mathcal{R}}$ contains exactly $k$ range-blocks.
For each $1\leq k^{\prime}\leq k$, let $v_{k^{\prime}}(B)$ be as computed
while processing the stream-block $B$ and the range-block $R_{k^{\prime}}$. If
$v_{1}(B)$ is undefined, we do not update the first block:
$R^{(\mathsf{new})}_{1}\leftarrow R_{1}$. Otherwise, we set
$R^{(\mathsf{new})}_{1}$ to be the range-block containing all elements until
$v_{1}(B^{\prime})$ of $H^{*}$ beginning from the first one. For each
successive $2\leq k^{\prime}\leq k$, we obtain the new block
$R^{(\mathsf{new})}_{k^{\prime}}$ as follows. If $v_{k^{\prime}}(B)$ is
defined, we let the new block $R^{(\mathsf{new})}_{k^{\prime}}$ contain all
the elements that appear after the block $R^{(\mathsf{new})}_{k^{\prime}-1}$
until the element $v_{k^{\prime}}(B)$ of $H^{*}$. Otherwise, if
$v_{k^{\prime}}(B)$ is undefined, we let the new block
$R^{(\mathsf{new})}_{k^{\prime}}$ contain all the elements that appear after
the block $R^{(\mathsf{new})}_{k^{\prime}-1}$ until the last element of
$R_{k^{\prime}}$. Finally, we update
$\tilde{\mathcal{R}}\leftarrow(R^{(\mathsf{new})}_{1},\ldots,R^{(\mathsf{new})}_{k})$.
Let
$\mathsf{leftover}(\tilde{\mathcal{R}}):=H^{*}\backslash\bigcup_{R_{i}\in\tilde{\mathcal{R}}}R_{i}$
be the set of elements not present in the blocks of $\tilde{\mathcal{R}}$.
From our construction, it is immediate to verify that
$\mathsf{leftover}(\tilde{\mathcal{R}})$ is indeed a (possibly empty) range-
block and the non-empty blocks of
$\tilde{\mathcal{R}}\cup\left\\{\mathsf{leftover}(\tilde{\mathcal{R}})\right\\}$
constitute a partition of $H^{*}$.

###### Case $2$: $v_{\mathsf{leftover}}(B)$ is defined.

In this case,
$v_{\mathsf{leftover}}(B)\in\mathsf{leftover}(\tilde{\mathcal{R}})$ and
$\tilde{\mathcal{R}}\cup\left\\{\mathsf{leftover}(\tilde{\mathcal{R}})\right\\}$
is a partition of $H^{*}$. We append
$\tilde{\mathcal{R}}\leftarrow\tilde{\mathcal{R}}\cup\left\\{\mathsf{leftover}(\tilde{\mathcal{R}})\right\\}$
for convenience, and let ${\tilde{\mathcal{R}}=({\mathcal{R}}_{1},\ldots,)}$
be these non-empty range-blocks in their natural order. We let
$|\tilde{\mathcal{R}}|=k$ and notice that ${1\leq k\leq\frac{Z_{0}}{Z_{1}}+1}$
holds in this case. We will ensure that after the update, our collection
$\tilde{\mathcal{B}}$ contains exactly $k^{*}:=\min{(k,\frac{Z_{0}}{Z_{1}})}$
range-blocks. We proceed as in case $1$. For each $1\leq k^{\prime}\leq k$,
let $v_{k^{\prime}}(B)$ be as computed while processing stream-block $B$ and
the range-block $R_{k^{\prime}}$. If $v_{1}(B)$ is undefined, we do not update
the first block: $R^{(\mathsf{new})}_{1}\leftarrow R_{1}$. Otherwise, we set
$R^{(\mathsf{new})}_{1}\leftarrow R^{\prime}_{1}$. For each successive $2\leq
k^{\prime}\leq k$, we obtain the new block $R^{(\mathsf{new})}_{k^{\prime}}$
as follows. If $v_{k^{\prime}}(B)\in R_{i}$, we let the new block
$R^{(\mathsf{new})}_{k^{\prime}}$ contain all the elements that appear after
the block $R^{(\mathsf{new})}_{k^{\prime}-1}$ until the element
$v_{k^{\prime}}(B)$. Otherwise, if $v_{k^{\prime}}(B)$ is undefined, we let
the new block $R^{(\mathsf{new})}_{k^{\prime}}$ contain all the elements that
appear after the block $R^{(\mathsf{new})}_{k^{\prime}-1}$ until the last
element of $R_{k^{\prime}}$. Finally, we update
$\tilde{\mathcal{R}}\leftarrow(R^{(\mathsf{new})}_{1},\ldots,R^{(\mathsf{new})}_{k^{*}})$.
Let
$\mathsf{leftover}(\tilde{\mathcal{R}}):=H^{*}\backslash\bigcup_{R_{i}\in\tilde{\mathcal{R}}}R_{i}$
be the set of elements not present in the blocks of $\tilde{\mathcal{R}}$.
From our construction, it is immediate to verify that
$\mathsf{leftover}(\tilde{\mathcal{R}})$ is indeed a range-block and the non-
empty blocks of
$\tilde{\mathcal{R}}\cup\left\\{\mathsf{leftover}(\tilde{\mathcal{R}})\right\\}$
constitute a partition of $H^{*}$. This completes the description of case $2$,
and as a result, the description of our algorithm for processing the stream-
block $B$.

We define $L^{*}:=32pZ_{0}/Z_{1}$. For a stream-block
$B^{\prime}\in{\mathcal{B}}^{2}$, we denote by
${\mathcal{E}}^{*}_{\mathsf{bad}}(B^{\prime})$ the event that the block
$B^{\prime}$ is marked at least $L^{*}$ times while processing its ancestor-
block $B\in{\mathcal{B}}^{1}$. We let ${\mathcal{E}}^{*}_{\mathsf{bad}}$ be
the event that there is a some block $B^{\prime}\in{\mathcal{B}}^{2}$ for
which the event ${\mathcal{E}}^{*}_{\mathsf{bad}}(B^{\prime})$ occurs.
Throughout our algorithm, if at any point the event
${\mathcal{E}}^{*}_{\mathsf{bad}}$ occurs, we immediately stop our algorithm
and report no. Once we process the last stream-block of ${\mathcal{B}}^{1}$,
we are ready to report our answer. Let $\tilde{\mathcal{R}}$ be our collection
of blocks, just after processing the last element of $S$. If
$\tilde{\mathcal{R}}$ contains exactly $\frac{Z_{0}}{Z_{1}}$ regions, we
report yes; otherwise, we report no. This completes the description of our
algorithm $\mathsf{Alg}_{\mbox{{\scriptsize{LIS}}}}$. We now turn to analyze
its properties, starting with the following simple observation whose proof is
included in Section C.3.0.2.

######  Claim 4.6.2.

$\text{\bf Pr}\left[{\mathcal{E}}^{*}_{\mathsf{bad}}\right]\leq 1/N^{2}$.

###### Completeness.

Assume that there is a $\bm{Z}$-canonical increasing subsequence $S^{*}$ of
$S$ with length at least $Z_{0}$, or in other words,
$|{\mathcal{B}}^{1}_{\mathsf{yes}}|\geq Z_{0}/Z_{1}$. Our goal is to show that
we report yes with probability at least $3/4$.

We let ${\mathcal{B}}^{1}_{\mathsf{yes}}$ be the set of yes-blocks of
${\mathcal{B}}^{1}$ for $S^{*}$. We discard the additional yes-blocks to
ensure that $|{\mathcal{B}}^{1}_{\mathsf{yes}}|=Z_{0}/Z_{1}$ holds, and we let
${\mathcal{B}}_{\mathsf{yes}}=\left\\{B(1),\ldots,B(Z_{0}/Z_{1})\right\\}$ in
their natural order. Notice that each such yes-block
$B\in{\mathcal{B}}^{1}_{\mathsf{yes}}$ has $\frac{Z_{1}}{Z_{2}}$ descendant
yes-blocks in ${\mathcal{B}}^{2}$. For each block
$B\in{\mathcal{B}}^{1}_{\mathsf{yes}}$, we let
${\mathcal{E}}^{**}_{\mathsf{bad}}(B)$ be the event that we do not mark any of
its descendant yes-blocks. From Chernoff bound, it is immediate to verify that
$\text{\bf Pr}\left[{\mathcal{E}}^{**}_{\mathsf{bad}}(B)\right]\leq 1/N^{2}$.
We let ${\mathcal{E}}^{**}_{\mathsf{bad}}$ be the event that
${\mathcal{E}}^{**}_{\mathsf{bad}}(B)$ occurs for some yes-block
$B\in{\mathcal{B}}^{1}_{\mathsf{yes}}$. From union bound over at most $N$ yes-
blocks, we obtain that $\text{\bf
Pr}\left[{\mathcal{E}}^{**}_{\mathsf{bad}}\right]\leq 1/N^{2}$. Combining this
with Claim 4.6.2, we conclude that $\text{\bf
Pr}\left[{\mathcal{E}}^{*}_{\mathsf{bad}}\cup{\mathcal{E}}^{**}_{\mathsf{bad}}\right]\leq
2/N^{2}<1/N$.

For each integer $1\leq s\leq Z_{0}/Z_{1}$ and the corresponding yes-block
$B(s)$ of ${\mathcal{B}}^{1}$, let $\tilde{\mathcal{R}}^{(s)}$ be our
collection of range-blocks just after processing $B(s)$. Using techniques
similar to LABEL:{clm:_ncm-jump-dp-completeness}, we obtain the following
claim showing the completeness guarantee.

######  Claim 4.6.3.

If the events ${\mathcal{E}}^{*}_{\mathsf{bad}}$ and
${\mathcal{E}}^{**}_{\mathsf{bad}}$ does not occur, then for each $1\leq
s\leq\frac{Z_{0}}{Z_{1}}$, $|\tilde{\mathcal{R}}^{(s)}|\geq s$.

We defer the proof of Claim 4.6.3 to Section C.3.0.3.

###### Soundness.

We let ${\mathcal{B}}^{1}=\left\\{B(1),\ldots,B(|{\mathcal{B}}^{1}|)\right\\}$
be the stream-blocks in their natural order. For each integer $1\leq
s\leq|{\mathcal{B}}^{1}|$ and the corresponding stream-block
$B(s)\in{\mathcal{B}}^{1}$, let $\tilde{\mathcal{R}}^{(s)}$ be our collection
of range-blocks of $H^{*}$ just after processing $B(s)$. Using techniques
similar to Claim 4.5.37, it is immediate to verify the following claim.

######  Claim 4.6.4.

If the events ${\mathcal{E}}^{*}_{\mathsf{bad}}$ and
${\mathcal{E}}^{**}_{\mathsf{bad}}$ does not occur, then for each $1\leq
s\leq|{\mathcal{B}}^{1}|$ and $1\leq
s^{\prime}\leq|\tilde{\mathcal{R}}^{(s)}|$, there is an increasing subsequence
of length at least $s^{\prime}Z_{2}$ using the elements in $B(1)\cup\ldots\cup
B(s)$ with values in the range-blocks $\tilde{\mathcal{R}}^{(s)}$.

We include the proof of Claim 4.6.4 in Section C.3.0.4 for the sake of
completeness. Recall that we report yes only if there are exactly
$Z_{0}/Z_{1}$ blocks in our collection at the end of $S$, or in other words,
$|\tilde{\mathcal{R}}^{(s)}|=Z_{0}/Z_{1}$, where $s=|{\mathcal{B}}^{1}|$. But
then from Claim 4.6.4, there must be an increasing subsequence of length at
least $\frac{Z_{0}}{Z_{1}}\cdot Z_{2}\geq\frac{Z_{0}}{\alpha}$. We can now
conclude that the probability that
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)<Z_{0}/\alpha$ and we report yes,
is at most $\text{\bf
Pr}\left[{\mathcal{E}}^{*}_{\mathsf{bad}}\cup{\mathcal{E}}^{**}_{\mathsf{bad}}\right]\leq
2/N^{2}<1/N$ as required.

###### Space Complexity.

Consider some stream-block $B\in{\mathcal{B}}^{1}$ and let
$\tilde{\mathcal{R}}$ be our collection of range-blocks just before processing
$B$. The space used by $\mathsf{Alg}_{\mbox{{\scriptsize{LIS}}}}$ can be
divided into three parts: (i) the space required to store the range-blocks
$\tilde{\mathcal{R}}$; (ii) the space used by executions of $\mathsf{Alg}_{1}$
from Lemma 4.2.1 and (iii) the space required to update the range-blocks
$\tilde{\mathcal{R}}$.

Recall that we can store a block $R\in\tilde{\mathcal{R}}$ by storing the
indices of its first and last elements in $H^{*}$. Since there are at most
$Z_{0}/Z_{1}$ regions in $\tilde{\mathcal{R}}$, the space used to store them
is at most $O(Z_{0}/Z_{1})$. Similarly, we can store the special block
$R_{\mathsf{leftover}}=H^{*}\backslash\bigcup_{R\in\tilde{\mathcal{R}}}R$ in
$O(1)$ units of space. Thus, the space used in part (i) is bounded by
$O(Z_{0}/Z_{1})$. Recall that we halt our algorithm immediately if the event
${\mathcal{E}}^{*}_{\mathsf{bad}}$ occurs. Thus, throughout the execution of
our algorithm, each descendant stream-block $B^{\prime}$ of $B$ is marked at
most $L^{*}$ times and the space required by $\mathsf{Alg}_{1}$ of Lemma 4.2.1
can be bounded by $O(L^{*}\cdot Z_{2})$. It is also immediate to verify that
we can update our collection $\tilde{\mathcal{R}}$ using $O(Z_{0}/Z_{1})$
additional space. Hence, the overall space complexity of
$\mathsf{Alg}_{\mbox{{\scriptsize{LIS}}}}$ is bounded by,

$\displaystyle O\left(\frac{Z_{0}}{Z_{1}}\right)+L^{*}\cdot O(Z_{2})$
$\displaystyle=O\left(\frac{Z_{0}}{Z_{1}}+p\cdot\frac{Z_{0}}{Z_{1}}\cdot
Z_{2}\right)$
$\displaystyle\leq\tilde{O}\left(\frac{Z_{0}}{Z_{1}}+\frac{Z_{0}}{\alpha^{2}}\right)$
$\displaystyle\leq\tilde{O}\left(\alpha+\frac{\sqrt{N}}{\alpha}\right)=\tilde{O}\left(\frac{\sqrt{N}}{\alpha}\right).$

Here, the first equality follows from our choice of $L^{*}=32pZ_{0}/Z_{1}$.
The inequalities follow from LABEL:{eqn:_ncm-alpha-approx-z0-by-z1} and
LABEL:{eqn:_ncm-alpha-approx-tau-star}. This completes the analysis of the
properties of $\mathsf{Alg}_{\mbox{{\scriptsize{LIS}}}}$ and Theorem 4.1.3 now
follows.

##  Appendix A Proofs Omitted from Chapter 2

###  A.1 Proof Omitted from Section 2.2

#####  A.1.0.1 Proof of Theorem 2.2.4

Suppose $G$ is a Yes-Instance, and let $\chi$ be a valid coloring of $V(G)$.
Let $\pi_{1},\ldots,\pi_{6}$ be $6$ different permutations of
$\left\\{r,g,b\right\\}$. For each $1\leq i\leq 6$, permutation $\pi_{i}$
defines a valid coloring $\chi_{i}$ of $G$: for every vertex $v\in V(G)$, if
$v$ is assigned a color $c\in\left\\{{\mathcal{C}}\right\\}$ by $\chi$, then
$\chi_{i}$ assigns the color $\pi_{i}(c)$ to $v$. Notice that for each vertex
$v$ and for each color $c\in{\mathcal{C}}$, there are exactly two indices
$i\in\left\\{1,\ldots,6\right\\}$, such that $\chi_{i}$ assigns the color $c$
to $v$. Notice also that for each edge $(u,v)$, if
$c,c^{\prime}\in{\mathcal{C}}$ is any pair of distinct colors, then there is
exactly one index $i\in\left\\{1,\ldots,6\right\\}$, such that $u$ is assigned
the color $c$ and $v$ is assigned the color $c^{\prime}$ by $\chi_{i}$.

Let $B$ be the set of all vectors of length $\ell$, whose entries belong to
$\left\\{1,\ldots,6\right\\}$, so that $|B|=6^{\ell}$. For each such vector
$b\in B$, we define a perfect global assignment $f_{b}$ of answers to the
queries, as follows. Let $Q\in{\mathcal{Q}}^{E}$ be a query to the edge-
player, and assume that $Q=(e_{1},\ldots,e_{\ell})$. Fix some index $1\leq
j\leq\ell$, and assume that $e_{j}=(v_{j},u_{j})$. Assume that $b_{j}=z$, for
some $1\leq z\leq 6$. We assign to $v_{j}$ the color $\chi_{z}(v_{j})$, and we
assign to $u_{j}$ the color $\chi_{z}(u_{j})$. Since $\chi_{z}$ is a valid
coloring of $V(G)$, the two colors are distinct. This defines an answer
$A\in{\mathcal{A}}^{E}$ to the query $Q$, that determines $f_{b}(Q)$.

Consider now some query $Q^{\prime}\in{\mathcal{Q}}^{V}$ to the vertex-player,
and assume that $Q^{\prime}=(v_{1},\ldots,v_{\ell})$. Fix some index $1\leq
j\leq\ell$, and assume that $b_{j}=z$, for some $1\leq z\leq 6$. We assign to
$v_{j}$ the color $\chi_{z}(v_{j})$. This defines an answer
$A^{\prime}\in{\mathcal{A}}^{V}$ to the query $Q^{\prime}$, that determines
$f_{b}(Q^{\prime})$. Notice that for each $1\leq j\leq\ell$, the answers that
we choose for the $j$th coordinate of each query are consistent with the valid
coloring $\chi_{b_{j}}$ of $G$. Therefore, it is immediate to verify that for
each $b\in B$, $f_{b}$ is a perfect global assignment.

We now fix some query $Q\in{\mathcal{Q}}^{E}$ of the edge-prover, and some
answer $A\in{\mathcal{A}}^{E}$ to it. Assume that $Q=(e_{1},\ldots,e_{\ell})$,
where for $1\leq j\leq\ell$, $e_{j}=(v_{j},u_{j})$. Let $c_{j},c^{\prime}_{j}$
are the assignments to $v_{j}$ and $u_{j}$ given by the $j$th coordinate of
$A$, so that $c_{j}\neq c^{\prime}_{j}$. Recall that there is exactly one
index $z_{j}\in\left\\{1,\ldots,6\right\\}$, such that $\chi_{z_{j}}$ assigns
the color $c_{j}$ to $v_{j}$ and the color $c^{\prime}_{j}$ to $u_{j}$. Let
$b^{*}\in B$ be the vector, where for $1\leq j\leq\ell$, $b^{*}_{j}=z_{j}$.
Then $f_{b^{*}}(Q)=A$, and for all $b\neq b^{*}$, $f_{b}(Q)\neq A$.

Finally, fix some query $Q^{\prime}\in{\mathcal{Q}}^{V}$ of the vertex-prover,
and some answer $A^{\prime}\in{\mathcal{A}}^{V}$ to it. Let
$Q^{\prime}=(v_{1},\ldots,v_{\ell})$. Assume that for each $1\leq j\leq\ell$,
the $j$th coordinate of $A^{\prime}$ contains the color $c_{j}$. Recall that
there are exactly two indices $z\in\left\\{1,\ldots,6\right\\}$, such that
$\chi_{z}$ assigns the color $c_{j}$ to $v_{j}$. Denote this set of two
indices by $Z_{j}\subseteq\left\\{1,\ldots,6\right\\}$. Consider now some
vector $b\in B$. If, for all $1\leq j\leq\ell$, $b_{j}\in Z_{j}$, then
$f_{b}(Q^{\prime})=A^{\prime}$; otherwise, $f_{b}(Q^{\prime})\neq A^{\prime}$.
Therefore, the total number of vectors $b\in B$, for which
$f_{b}(Q^{\prime})=A^{\prime}$ is exactly $2^{\ell}$.

###  A.2 Proofs Omitted from Section 2.5

####  A.2.1 Proofs of Auxillary Lemmas 2.5.2 and 2.5.3

The goal of this subsection is to prove Lemmas 2.5.2 and 2.5.3. We will use
the following simple observation.

######  Observation A.2.1.

For any two positive integers $a$ and $b$, $\frac{b-1}{a+b-1}<\frac{b}{a+b}$.

Recall that we are given a set $U$ of $n$ items, such that $P$ of the items
are pink, and the remaining $Y=n-P$ items are yellow. We consider a random
permutation $\pi$ of these items. Given a set
$S\subseteq\left\\{1,\ldots,n\right\\}$ of $\delta$ indices, we let
${\cal{E}}(S)$ be the event that for all $i\in S$, the item of $\pi$ located
at the $i$th position is yellow.

######  Claim A.2.2.

$\text{\bf Pr}\left[{\cal{E}}(S)\right]\leq\left(\frac{Y}{n}\right)^{|S|}.$

###### Proof.

As every subset of $\delta$ items of $U$ is equally likely to appear at the
indices of $S$, we get that:

$\text{\bf
Pr}\left[{\cal{E}}(S)\right]=\frac{\binom{Y}{\delta}}{\binom{P+Y}{\delta}}=\frac{Y\cdot(Y-1)\cdots(Y-\delta+1)}{(P+Y)\cdot(P+Y-1)\cdots(P+Y-\delta+1)}\leq\left(\frac{Y}{P+Y}\right)^{\delta}=\left(\frac{Y}{n}\right)^{|S|}.$

(the last inequality follows from Observation A.2.1).

We now turn to prove Lemma 2.5.2.

######  Lemma A.2.3 (Restatement of Lemma Lemma 2.5.2.).

For any $\log n\leq\mu\leq Y$, the probability that there is a sequence of
$\left\lceil 4n\mu/P\right\rceil$ consecutive items in $\pi$ that are all
yellow, is at most $n/e^{\mu}$.

###### Proof.

Let $\delta=\left\lceil\frac{4n\mu}{P}\right\rceil$. Consider a set $S$ of
$\delta$ consecutive indices of $\left\\{1,\ldots,n\right\\}$. From Claim
A.2.2, the probability that all items located at the indices of $S$ are yellow
is at most:

$\left(\frac{Y}{n}\right)^{\delta}=\left(1-\frac{P}{n}\right)^{\left\lceil
4n\mu/P\right\rceil}\leq\left(1-\frac{P}{n}\right)^{4n\mu/P}\leq e^{-\mu}.$

Since there are at most $n$ possible choices of a set $S$ of $\delta$
consecutive indices, from the Union Bound, the probability that any such set
only contains yellow items is bounded by $n/e^{\mu}$.

######  Lemma A.2.4 (Restatement of Lemma 2.5.3.).

For any $\log n\leq\mu\leq P$, the probability that there is a set $S$ of
$\left\lfloor\frac{n\mu}{P}\right\rfloor$ consecutive items in $\pi$, such
that more than $4\mu$ of the items are pink, is at most $n/4^{\mu}$.

###### Proof.

Let $x=\left\lfloor\frac{n\mu}{P}\right\rfloor$, and let $S$ be any set of $x$
consecutive indices of $\left\\{1,\ldots,n\right\\}$. Denote
$\delta=\left\lceil 4\mu\right\rceil$, and let $S^{\prime}\subseteq S$ be any
subset of $\delta$ indices from $S$. From Claim A.2.2 (by reversing the roles
of the pink and the yellow items), the probability that all items located at
the indices of $S^{\prime}$ are pink is at most
$\left(\frac{P}{n}\right)^{\delta}$. Since there are ${x\choose\delta}$ ways
to choose the subset $S^{\prime}$ of $S$, from the Union Bound, the
probability that at least $\delta$ items of $S$ are pink is at most:

$\begin{split}\left(\frac{P}{n}\right)^{\delta}\cdot{x\choose\delta}&\leq\left(\frac{P}{n}\right)^{\delta}\cdot\left(\frac{ex}{\delta}\right)^{\delta}\\\
&\leq\left(\frac{P}{n}\right)^{\delta}\cdot\left(\frac{e\cdot
n\mu}{P\delta}\right)^{\delta}\\\ &=\left(\frac{e\cdot\mu}{\left\lceil
4\mu\right\rceil}\right)^{\left\lceil 4\mu\right\rceil}\\\
&\leq\left(\frac{e}{4}\right)^{4\mu}<\frac{1}{4^{\mu}}.\end{split}$

Since there are at most $n$ sets $S$ of $x$ consecutive items, taking the
union bound over all such sets completes the proof.

####  A.2.2 Proof of Observation 2.5.7.

From our assumption that $|{\mathcal{M}}^{0}|>c\log^{3}M$,
$E^{2}\neq\emptyset$. Therefore, there must be an index $1\leq i\leq r$ with
$E_{i}\cap E^{2}\neq\emptyset$. Fix any such index $i$. Then there is a vertex
$v^{\prime}_{j}\in W_{i}\cap V_{2}$, such that at least one edge of
$\delta(v^{\prime}_{j})$ belongs to $E^{2}$. But then, from the definition of
$E^{2}$, at least $2^{q-1}$ edges of $\delta(v^{\prime}_{j})$ belong to
$E^{2}$. Assume without loss of generality that these edges connect
$v^{\prime}_{j}$ to vertices $v_{1},\ldots,v_{2^{q-1}}\in V_{1}$. All these
vertices must also belong to $W_{i}$, and for each $1\leq x\leq 2^{q-1}$,
vertex $v_{x}$ has at least one edge in $\delta(v_{x})\cap E^{2}$. From our
definition of $E^{2}$ and $E^{1}$, at least $2^{p-1}$ edges of $\delta(v_{x})$
belonged to $E^{1}$. Therefore, $|E^{1}\cap E_{i}|\geq 2^{q-1}\cdot 2^{p-1}$.
But $|E_{i}|\leq h$, and so $h\geq 2^{p}\cdot 2^{q}/4$. $\Box$

####  A.2.3 Proof of Observation 2.5.8.

Since $|V_{1}|\leq M$, from the union bound, it is enough to prove that for a
fixed vertex $v_{i}\in V_{1}$, the probability that a heavy sub-path
$Q\subseteq K_{i}$ exists is at most $1/(100M)$. We now fix some vertex
$v_{i}\in V_{1}$. Observe that $K_{i}$ may only contain a heavy sub-path if
$\beta(v_{i})=|X_{i}|\geq 16\log M$. We call the vertices of $X^{\prime}_{i}$
pink, and the remaining vertices of $X_{i}$ yellow. Let $P$ denote the number
of the pink vertices. Then $2^{p-1}\leq P<2^{p}$. Let $\mu=4\log M$, and let
${\cal{E}}_{i}$ be the bad event that there is a set of
$\left\lfloor|X_{i}|\mu/P\right\rfloor$ consecutive vertices of $X_{i}$, such
that at least $4\mu$ of them are pink.

Observe that the selection of the pink vertices only depends on the solution
to the (r,h)-GPwB problem, and is independent of our construction of the NDP-
Grid instance. The ordering of the vertices in $X_{i}$ is determined by the
permutation $\rho^{\prime}$ of ${\mathcal{U}}_{2}$, and is completely random.
Therefore, from Lemma 2.5.3, the probability of ${\cal{E}}_{i}$ is at most
$|X_{i}|/4^{\mu}\leq M/4^{4\log M}\leq 1/M^{7}$.

Let ${\cal{E}}^{\prime}_{i}$ be the event that some sub-path $Q$ of $K_{i}$ is
heavy. We claim that ${\cal{E}}^{\prime}_{i}$ may only happen if event
${\cal{E}}_{i}$ happens. Indeed, consider some sub-path $Q$ of $K_{i}$, and
assume that it is heavy. Recall that $Q$ contains
$\left\lfloor\frac{512h\log^{2}M}{2^{p}}\right\rfloor$ vertices. Since every
pair of vertices in $X_{i}$ is separated by at least
$512\left\lceil\frac{h\log M}{\beta(v_{i})}\right\rceil$ vertices, we get
that:

$|V(Q)\cap X_{i}|\leq\frac{\left\lfloor
512h\log^{2}M/2^{p}\right\rfloor}{512\left\lceil h\log
M/\beta(v_{i})\right\rceil}+1\leq\frac{\beta(v_{i})\log
M}{2^{p}}+1\leq\left\lfloor\frac{|X_{i}|\mu}{P}\right\rfloor,$

as $2^{p-1}\leq P<2^{p}$. Since $Q$ is heavy, at least $4\mu=16\log M$ of the
vertices of $V(Q)\cap X_{i}$ belong to $X^{\prime}_{i}$, that is, they are
pink. Therefore, there is a set of $\left\lfloor|X_{i}|\mu/P\right\rfloor$
consecutive vertices of $X_{i}$, out of which $4\mu$ are pink, and
${\cal{E}}_{i}$ happens. We conclude that $\text{\bf
Pr}\left[{\cal{E}}^{\prime}_{i}\right]\leq\text{\bf
Pr}\left[{\cal{E}}_{i}\right]\leq 1/M^{7}$, and overall, since we have assumed
that $M>2^{50}$, the probability that a heavy path exists in any block $K_{i}$
is bounded by $0.99$ as required. $\Box$

####  A.2.4 Proof of Observation 2.5.10.

Since we have started with a perfect solution to ${\mathcal{I}}$, for each
group $U\in{\mathcal{U}}^{\prime}$, there is exactly one vertex of $U$ in
$W_{i}$. Due to Step 1 of regularization, each such vertex contributed at
least $2^{q-1}$ edges to $E^{1}\cap E_{i}$, while $|E^{1}\cap E_{i}|\leq h$.
Therefore, $n^{*}\leq h/2^{q-1}$. $\Box$

####  A.2.5 Routing via Spaced-out Paths - Proof of Claim 2.5.13

The goal of this subsection is to prove Claim 2.5.13. We show an efficient
algorithm to construct a set
${\mathcal{P}}^{1}=\left\\{P_{1},\ldots,P_{M^{\prime}}\right\\}$ of spaced-out
paths, that originate at the vertices of $X$ on $R$, and traverse the boxes
$\hat{K}_{j}$ in a snake-like fashion (see Figure 2.4). We will ensure that
for each $1\leq i\leq M^{\prime}$ and $1\leq j\leq N_{1}$, the intersection of
the path $P_{i}$ with the box $\hat{K}_{j}$ is the $i$th column of
${\mathcal{W}}_{j}$, and that $P_{i}$ contains the vertex $x_{i}$.

Fix some index $1\leq j\leq N_{1}$, and consider the box $\hat{K}_{j}$. Let
$I^{\prime}_{j}$ and $I^{\prime\prime}_{j}$ denote the top and the bottom
boundaries of $\hat{K}_{j}$, respectively. For each $1\leq i\leq M^{\prime}$,
let $W_{j}^{i}$ denote the $i$th column of ${\mathcal{W}}_{j}$, and let
$x^{\prime}(j,i)$ and $x^{\prime\prime}(j,i)$ denote the topmost and the
bottommost vertices of $W_{j}^{i}$, respectively.

For convenience, we also denote $I^{\prime\prime}_{0}=R$, and, for each $1\leq
i\leq M^{\prime}$, $x^{\prime\prime}(0,i)=x_{i}$. The following claim is
central to our proof.

######  Claim A.2.5.

There is an efficient algorithm to construct, for each $1\leq j\leq N_{1}$, a
set ${\mathcal{P}}_{j}=\left\\{P_{j}^{1},\ldots,P_{j}^{M^{\prime}}\right\\}$
of paths, such that:

  * •

For each $1\leq j\leq N_{1}$ and $1\leq i\leq M^{\prime}$, path $P_{j}^{i}$
connects $x^{\prime\prime}(j-1,i)$ to $x^{\prime}(j,i)$;

  * •

The set $\bigcup_{j=1}^{N_{1}}{\mathcal{P}}_{j}$ of paths is spaced-out; and

  * •

All paths in $\bigcup_{j=1}^{N_{1}}{\mathcal{P}}_{j}$ are contained in
$G^{t}$, and are internally disjoint from $R$.

Notice that by combining the paths in $\bigcup_{j=1}^{N_{1}}{\mathcal{P}}_{j}$
with the set $\bigcup_{j=1}^{N_{1}}{\mathcal{W}}_{j}$ of columns of the boxes,
we obtain the desired set ${\mathcal{P}}^{1}$ of paths, completing the proof
of Claim 2.5.13. In the remainder of this section we focus on proving Claim
A.2.5.

Recall that each box $\hat{K}_{j}$ is separated by at least $2M$ columns from
every other such box, and from the left and right boundaries of $\hat{G}$. It
is also separated by at least $4M$ rows from the top boundary of $\hat{G}$ and
from the row $R$. We exploit this spacing in order to construct the paths, by
utilizing a special structure called a _snake_ , that we define next.

Given a set ${\mathcal{L}}$ of consecutive rows of $\hat{G}$ and a set
${\mathcal{W}}$ of consecutive columns of $\hat{G}$, we denote by
$\Upsilon({\mathcal{L}},{\mathcal{W}})$ the subgraph of $\hat{G}$ spanned by
the rows in ${\mathcal{L}}$ and the columns in ${\mathcal{W}}$; we refer to
such a graph as a _corridor_. Let
$\Upsilon=\Upsilon({\mathcal{L}},{\mathcal{W}})$ be any such corridor. Let
$L^{\prime}$ and $L^{\prime\prime}$ be the top and the bottom row of
${\mathcal{L}}$ respectively, and let $W^{\prime}$ and $W^{\prime\prime}$ be
the first and the last column of ${\mathcal{W}}$ respectively. The four paths
$\Upsilon\cap L^{\prime},\Upsilon\cap L^{\prime\prime},\Upsilon\cap
W^{\prime}$ and $\Upsilon\cap W^{\prime\prime}$ are called the top, bottom,
left and right boundaries of $\Upsilon$ respectively, and their union is
called the _boundary_ of $\Upsilon$. The width of the corridor $\Upsilon$ is
$w(\Upsilon)=\min\left\\{|{\mathcal{L}}|,|{\mathcal{W}}|\right\\}$. We say
that two corridors $\Upsilon,\Upsilon^{\prime}$ are _internally disjoint_ ,
iff every vertex $v\in\Upsilon\cap\Upsilon^{\prime}$ belongs to the boundaries
of both corridors. We say that two internally disjoint corridors
$\Upsilon,\Upsilon^{\prime}$ are _neighbors_ iff
$\Upsilon\cap\Upsilon^{\prime}\neq\emptyset$. We are now ready to define
snakes.

A snake ${\mathcal{Y}}$ of length $z$ is a sequence
$(\Upsilon_{1},\Upsilon_{2},\ldots,\Upsilon_{z})$ of $z$ corridors that are
pairwise internally disjoint, such that for all $1\leq
z^{\prime},z^{\prime\prime}\leq z$, $\Upsilon_{z^{\prime}}$ is a neighbor of
$\Upsilon_{z^{\prime\prime}}$ iff $|z^{\prime}-z^{\prime\prime}|=1$. The width
of the snake is defined to be the minimum of two quantities: (i) $\min_{1\leq
z^{\prime}<z}\left\\{|\Upsilon_{z^{\prime}}\cap\Upsilon_{z^{\prime}+1}|\right\\}$;
and (ii) $\min_{1\leq z^{\prime}\leq
z}\left\\{w(\Upsilon_{z^{\prime}})\right\\}$. Notice that, given a snake
${\mathcal{Y}}$, there is a unique simple cycle $\sigma({\mathcal{Y}})$
contained in $\bigcup_{z^{\prime}=1}^{z}\Upsilon_{z^{\prime}}$, such that, if
$D$ denotes the disc on the plane whose boundary is $\sigma({\mathcal{Y}})$,
then every vertex of $\bigcup_{z^{\prime}=1}^{z}\Upsilon_{z^{\prime}}$ lies in
$D$, while every other vertex of $\hat{G}$ lies outside $D$. We call
$\sigma({\mathcal{Y}})$ the _boundary_ of ${\mathcal{Y}}$. We say that a
vertex $u$ belongs to a snake ${\mathcal{Y}}$, and denote $u\in{\mathcal{Y}}$,
iff $u\in\bigcup_{z^{\prime}=1}^{z}\Upsilon_{z^{\prime}}$. We use the
following simple claim, whose proof can be found, e.g. in [CKN17].

######  Claim A.2.6.

Let ${\mathcal{Y}}=(\Upsilon_{1},\ldots,\Upsilon_{z})$ be a snake of width
$w$, and let $A$ and $A^{\prime}$ be two sets of vertices with
$|A|=|A^{\prime}|\leq w-2$, such that the vertices of $A$ lie on a single
boundary edge of $\Upsilon_{1}$, and the vertices of $A^{\prime}$ lie on a
single boundary edge of $\Upsilon_{z}$. There is an efficient algorithm, that,
given the snake ${\mathcal{Y}}$, and the sets $A$ and $A^{\prime}$ of vertices
as above, computes a set ${\mathcal{Q}}$ of node-disjoint paths contained in
${\mathcal{Y}}$, that connect every vertex of $A$ to a distinct vertex of
$A^{\prime}$.

Let $L,L^{\prime}$ be any pair of rows of $G$. Let ${\mathcal{Q}}$ be a set of
node-disjoint paths connecting some set of vertices $B\subseteq L$ to
$B^{\prime}\subseteq L^{\prime}$. We say that the paths in ${\mathcal{Q}}$ are
_order-preserving_ iff the left-to-right ordering of their endpoints on $L$ is
same as that of their endpoints on $L^{\prime}$.

######  Corollary A.2.7.

Let ${\mathcal{Y}}=(\Upsilon_{1},\ldots,\Upsilon_{z})$ be a snake of width
$w$, and let $B$ and $B^{\prime}$ be two sets of $r\leq\left\lfloor
w/2\right\rfloor-1$ vertices each, such that the vertices of $B$ lie on the
bottom boundary edge of $\Upsilon_{1}$, the vertices of $B^{\prime}$ lie on
the top boundary edge of $\Upsilon_{z}$ and for every pair $v,v^{\prime}\in
B\cup B^{\prime}$ of vertices, $d_{\hat{G}}(v,v^{\prime})\geq 2$. There is an
efficient algorithm, that, given the snake ${\mathcal{Y}}$, and the sets $B$
and $B^{\prime}$ of vertices as above, computes a set $\hat{\mathcal{Q}}$ of
spaced-out order-preserving paths contained in ${\mathcal{Y}}$.

###### Proof.

Let $B=\left\\{b_{1},b_{2},\ldots,b_{r}\right\\}$ and
$B^{\prime}=\left\\{b^{\prime}_{1},b^{\prime}_{2},\ldots,b^{\prime}_{r}\right\\}$.
Assume that the vertices in both sets are indexed according to their left-to-
right ordering on their corresponding rows of the grid. Since set $B$ does not
contain a pair of neighboring vertices, we can augment it to a larger set $A$,
by adding a vertex between every consecutive pair of vertices of $B$. In other
words, we obtain $A=\left\\{a_{1},\ldots,a_{2r-1}\right\\}$, such that for all
$1\leq i\leq r$, $a_{2i-1}=b_{i}$, and the vertices of $A$ are indexed
according to their left-to-right ordering on the bottom boundary of
$\Upsilon_{1}$. Similarly, we can augment the set $B^{\prime}$ to a set
$A^{\prime}=\left\\{a^{\prime}_{1},\ldots,a^{\prime}_{2r-1}\right\\}$ of
vertices, such that for all $1\leq i\leq r$,
$a^{\prime}_{2i-1}=b^{\prime}_{i}$, and the vertices of $A^{\prime}$ are
indexed according to their left-to-right ordering on the top boundary of
$\Upsilon_{z}$.

We apply Claim A.2.6 to the sets $A,A^{\prime}$ of vertices, obtaining a set
${\mathcal{Q}}$ of node-disjoint paths, that are contained in ${\mathcal{Y}}$,
and connect every vertex of $A$ to a distinct vertex of $A^{\prime}$. For all
$1\leq i\leq r$, let $Q_{i}$ be the path originating from $a_{i}$. We claim
that ${\mathcal{Q}}$ is an order-preserving set of paths. Indeed, assume for
contradiction that some path $Q_{i}\in{\mathcal{Q}}$ connects $a_{i}$ to
$a^{\prime}_{i^{\prime}}$, for $i\neq i^{\prime}$. Notice that the path
$Q_{i}$ partitions the snake ${\mathcal{Y}}$ into two sub-graphs: one
containing $(i-1)$ vertices of $A$ and $(i^{\prime}-1)$ vertices of
$A^{\prime}$; and the other containing the remaining vertices of $A$ and
$A^{\prime}$ (excluding the endpoints of $Q_{i}$). Since $i\neq i^{\prime}$,
there must be a path $Q_{i^{\prime\prime}}\in{\mathcal{Q}}$ intersecting the
path $Q_{i}$, a contradiction to the fact that ${\mathcal{Q}}$ is a set of
node-disjoint paths.

Similarly, it is easy to see that for all $1\leq i<r$,
$d(Q_{2i-1},Q_{2i+1})\geq 2$. This is since the removal of the path $Q_{2i}$
partitions the snake ${\mathcal{Y}}$ into two disjoint sub-graphs, with path
$Q_{2i-1}$ contained in one and path $Q_{2i+1}$ contained in the other.

Our final set of path is $\hat{\mathcal{Q}}=\left\\{Q_{2i-1}:1\leq i\leq
r\right\\}$. From the above discussion, it is a spaced-out set of paths
contained in ${\mathcal{Y}}$, and for each $1\leq i\leq r$, path
$Q_{2i-1}\in\hat{\mathcal{Q}}$ connects $b_{i}$ to $b^{\prime}_{i}$.

In order to complete the proof, we need the following easy observation.

######  Observation A.2.8.

There is an efficient algorithm that constructs, for each $1\leq j\leq N_{1}$,
a snake ${\mathcal{Y}}_{j}$ of width at least $2M$ in $G^{t}$, such that all
resulting snakes are mutually disjoint, and for each $1\leq j\leq N_{1}$:

  * •

the bottom boundary of the first corridor of ${\mathcal{Y}}_{j}$ contains
$I^{\prime\prime}_{j-1}$;

  * •

the top boundary of the last corridor of ${\mathcal{Y}}_{j}$ contains
$I^{\prime}_{j}$; and

  * •

all snakes are disjoint from $R$, except for ${\mathcal{Y}}_{1}$, that
contains $I_{0}^{\prime\prime}\subseteq R$ as part of is boundary, and does
not contain any other vertices of $R$.

The construction of the snakes is immediate and exploits the ample space
between the boxes $\hat{K}_{j}$; (see Figure 2.4 for an illustration). From
Corollary A.2.7, for each $1\leq j\leq N_{1}$, we obtain a set
${\mathcal{P}}_{j}$ of spaced-out paths contained in ${\mathcal{Y}}_{j}$, such
that for each $1\leq i\leq M^{\prime}$, there is a path
$P^{i}_{j}\in{\mathcal{P}}_{j}$ connecting $x^{\prime\prime}(j-1,i)$ to
$x^{\prime}(j,i)$. For each $1\leq i\leq M^{\prime}$, let $P_{i}$ be the path
obtained by concatenating the paths
$\left\\{P^{i}_{1},{\mathcal{W}}^{i}_{1},P^{i}_{2},\ldots,P^{i}_{N_{1}},{\mathcal{W}}^{i}_{N_{1}}\right\\}$.
The final set of paths is
${\mathcal{P}}^{1}=\left\\{P_{1},\ldots,P_{M^{\prime}}\right\\}$.

####  A.2.6 Proof of Observation 2.5.21.

Clearly, $|V(\hat{\mathbf{H}})|=\sum_{v\in V(\mathbf{H})}d^{2}_{v}$. Observe
that for every pair $a\geq b\geq 0$ of integers, $(a+1)^{2}+(b-1)^{2}\geq
a^{2}+b^{2}$. Since maximum vertex degree in $\mathbf{H}$ is bounded by $d$,
the sum is maximized when all but possibly one summand are equal to $d$, and,
since $\sum_{v\in\mathbf{H}}d_{v}=2m$, there are at most $\left\lceil
2m/d\right\rceil$ summands. Therefore, $|V(\hat{\mathbf{H}})|\leq\left\lfloor
2m/d\right\rfloor\cdot d^{2}+d^{2}\leq(2m+d)d$. $\Box$

####  A.2.7 Observation Proof of 2.5.23.

It is easy to verify that for any bi-partition $(X^{\prime},Y^{\prime})$ of
$U$ into two disjoint subsets, there is a set ${\mathcal{P}}$ of
$\min\left\\{|X^{\prime}|,|Y^{\prime}|\right\\}$ node-disjoint paths in $Q$
connecting vertices of $X^{\prime}$ to vertices of $Y^{\prime}$. The
observation follows from the maximum flow – minimum cut theorem. $\Box$

###  A.3 Proof Omitted from Section 2.6

Proof of Claim 2.6.2. The assertion that
$\mathsf{OPT}^{\prime}\geq\mathsf{OPT}$ is immediate, as any set
${\mathcal{P}}$ of node-disjoint paths in the wall $G$ is also a set of edge-
disjoint paths.

Assume now that we are given a set ${\mathcal{P}}^{\prime}$ of edge-disjoint
paths in $G$. We show an efficient algorithm to compute a subset
${\mathcal{P}}\subseteq{\mathcal{P}}^{\prime}$ of
$\Omega(|{\mathcal{P}}^{\prime}|)$ paths that are node-disjoint. Since the
maximum vertex degree in $G$ is 3, the only way for two paths
$P,P^{\prime}\in{\mathcal{P}}^{\prime}$ to share a vertex $x$ is when $x$ is
an endpoint of at least one of these two paths. If $x$ is an endpoint of $P$,
and $x\in V(P^{\prime})$, then we say that $P$ has a conflict with
$P^{\prime}$.

We construct a directed graph $H$, whose vertex set is $\left\\{v_{P}\mid
P\in{\mathcal{P}}^{\prime}\right\\}$, and there is an edge
$(v_{P},v_{P^{\prime}})$ iff $P$ has a conflict with $P^{\prime}$. It is
immediate to verify that the maximum out-degree of any vertex in $H$ is at
most $4$, as each of the two endpoints of a path $P$ may be shared by at most
two additional paths. Therefore, every sub-graph $H^{\prime}\subseteq H$ of
$H$ contains a vertex of total degree at most $8$. We construct a set $U$ of
vertices, such that no two vertices of $U$ are connected by an edge, using a
standard greedy algorithm: while $H\neq\emptyset$, select a vertex $v\in H$
with total degree at most $8$ and add it to $U$; remove $v$ and all its
neighbors from $H$. It is easy to verify that at the end of the algorithm,
$|U|=\Omega(|V(H)|)=\Omega(|{\mathcal{P}}^{\prime}|)$, and no pair of vertices
in $U$ is connected by an edge. Let ${\mathcal{P}}=\left\\{P\mid v_{P}\in
U\right\\}$. Then the paths in ${\mathcal{P}}$ are node-disjoint, and
$|{\mathcal{P}}|=\Omega(|{\mathcal{P}}^{\prime}|)$. $\Box$

##  Appendix B Proofs Omitted from Chapter 3

###  B.1 Proofs Omitted from Sections 3.1.1 and 3.2

####  B.1.1 Proof of Corollary 3.1.3 .

In this subsection we prove Corollary 3.1.3. We use the following result of
Krivelevich [Kri18]:

######  Theorem B.1.1 (Corollary 1 of [Kri18]).

For every $\epsilon>0$, there exists $\gamma>0$, such that for every $n>0$, a
random graph $G\sim{\mathcal{G}}(n,\frac{1+\epsilon}{n})$ contains an induced
bounded-degree $\gamma$-expander $\tilde{G}$ on at least $\gamma n$ vertices
w.h.p.

Let $G\sim{\mathcal{G}}(n,\frac{1+\epsilon}{n})$. From the above theorem,
w.h.p., there is an induced bounded-degree $\gamma$-expander
$\tilde{G}\subseteq G$ on at least $\gamma n$ vertices, for some $\gamma$
depending only on $\epsilon$. From Theorem 3.1.1, every graph $H$ of size at
most $c_{\epsilon}n/\log n$ is a minor of $\tilde{G}$, where $c_{\epsilon}$ is
some constant depending on $\epsilon$ only. Corollary 3.1.3 now follows.
$\Box$

####  B.1.2 Proof of Observation 3.1.4.

Recall that we are given a integer $s$ and a graph $G=(V,E)$ of size $s$.
Assume for now that $2\leq s<2^{20}$. Let $H_{G}$ be a graph with $s+1$
vertices and $0$ edges. Notice that the number of vertices in $H_{G}$ is
strictly more than that in $G$, and hence $H_{G}$ is not a minor of $G$. The
observation now follows since ${20}s/\log s\geq s+1$. Thus from now on, we
assume that $s\geq 2^{20}$ and hence, ${20}s/\log s\geq 2^{{20}}$.

We denote by $\mu(G)=|\left\\{H\>|\>H\text{ is a minor of }G\right\\}|$. For
an integer $r$, let ${\mathcal{F}}_{r}$ be the set of all graphs of size at
most $r$. The following two observations now complete the proof of Observation
3.1.4.

######  Observation B.1.2.

$\mu(G)\leq 3^{s}$.

###### Proof.

From the definition of minors, every minor $H$ of $G$ can be identified by a
subset $E^{\text{del}}_{H}\subseteq E$ of deleted edges, a subset
$E^{\text{cont}}_{H}\subseteq E$ of contracted edges and a subset
$V^{\text{del}}_{H}\subseteq V$ of deleted vertices. Thus,

$\mu(G)\leq 2^{|V|}\cdot 3^{|E|}\leq 3^{|V|+|E|}\leq 3^{s}.$

######  Observation B.1.3.

For every even integer $r\geq 2^{10}$, $|{\mathcal{F}}_{r}|\geq r^{r/10}$.

###### Proof.

Let $k=\left\lfloor r^{0.9}\right\rfloor$. We lower-bound the number of graphs
containing exactly $k$ vertices and exactly $r/2$ edges. Notice that, since
$r\geq 2^{10}$, $k+r/2\leq r$. For convenience, assume that the set
$V^{*}=\left\\{1,\ldots,k\right\\}$ of vertices and their indices are fixed.
We will first lower-bound the number of vertex-labeled graphs with the set
$V^{*}$ of vertices, that contain exactly $r/2$ edges. Since there are only
$\binom{k}{2}$ ‘edge-slots’, this number is at least:

$\binom{\binom{k}{2}}{r/2}\geq\binom{r^{1.6}}{r/2}\geq\left(\frac{r^{1.6}-r/2}{r/2}\right)^{r/2}\geq\left(r^{0.6}\right)^{r/2}\geq
r^{0.3r}.$

Here, the inequalities hold for all $r\geq 2^{10}$. Notice that two graphs
$G_{1}=(V^{*},E_{1})$ and $G_{2}=(V^{*},E_{2})$ with labeled vertices are
isomorphic to each other iff there is a permutation $\psi$ of the vertices,
mapping $E_{1}$ to $E_{2}$. Thus, the number of non-isomorphic graphs on $k$
vertices and $r/2$ edges is at least:

$\frac{r^{0.3r}}{k!}\geq\frac{r^{0.3r}}{\left(r^{0.9}\right)!}>\frac{r^{0.3r}}{r^{0.9r^{0.9}}}\geq
r^{r^{0.9}(0.3r^{0.1}-0.9)}\geq r^{r/10}.$

We are now ready to complete the proof of Observation 3.1.4. Assume for
contradiction that $G$ contains every graph in the family
${\mathcal{F}}^{*}={\mathcal{F}}_{({20}s/\log s)}$ as a minor. Recall that
${20}s/\log s\geq 2^{20}$. However, from the above two observations,
$|{\mathcal{F}}^{*}|\geq({20}s/\log s)^{{20}s/(10\log s)}$, while $\mu(G)\leq
3^{s}$. It is immediate to verify that $|{\mathcal{F}}^{*}|>\mu(G)$, a
contradiction. $\Box$

####  B.1.3 Proof of Observation 3.2.1.

We assume without loss of generality that $x_{1}\geq x_{2}\geq\cdots\geq
x_{r}$, and process the integers in this order. When $x_{i}$ is processed, we
add $i$ to $A$ if $\sum_{j\in A}x_{j}\leq\sum_{j\in B}x_{j}$, and we add it to
$B$ otherwise. We claim that at the end of this process, $\sum_{i\in
A}x_{i},\sum_{i\in B}x_{i}\geq N/4$ must hold. Indeed, $1$ is always added to
$A$. If $x_{1}\geq N/4$, then, since $x_{1}\leq 3N/4$, it is easy to see that
both subsets of integers sum up to at least $N/4$. Otherwise, $|\sum_{i\in
A}x_{i}-\sum_{i\in B}x_{i}|\leq\max_{i}\left\\{x_{i}\right\\}\leq x_{1}\leq
N/4$, and so $\sum_{i\in A}x_{i},\sum_{i\in B}x_{i}\geq N/4$. $\Box$

####  B.1.4 Proof of Claim 3.2.3.

Our algorithm iteratively removes edges from $T\setminus E^{\prime}$, until we
obtain a connected component of the resulting graph that is an
$\alpha/4$-expander. We start with $T^{\prime}=T\setminus E^{\prime}$ (notice
that $T^{\prime}$ is not necessarily connected). We also maintain a set
$E^{\prime\prime}$ of edges that we remove from $T^{\prime}$, initialized to
$E^{\prime\prime}=\emptyset$. While $T^{\prime}$ is not an
$\alpha/4$-expander, let $(X,Y)$ be a cut of sparsity less than $\alpha/4$ in
$T^{\prime}$, that is $|E_{T^{\prime}}(X,Y)|<\alpha\min{(|X|,|Y|)}/4$. Assume
w.l.o.g. that $|X|\geq|Y|$. Update $T^{\prime}$ to be $T^{\prime}[X]$, add the
edges of $E(X,Y)$ to $E^{\prime\prime}$, and continue to the next iteration.

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(T^{\prime})|/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}|\leq\alpha\sum_{i=1}^{r}|Y_{i}|/4.$

On the other hand, since $T$ is an expander, the total number of edges leaving
each set $Y_{i}$ in $T$ 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$. We get that
$\sum_{i=1}^{r}|Y_{i}|\leq\frac{4|E^{\prime}|}{\alpha}$, and therefore
$|V(T^{\prime})|\geq|V(T)|-\frac{4|E^{\prime}|}{\alpha}$. $\Box$

###  B.2 Proofs Omitted from Section 3.4

####  B.2.1 Proof of Observation 3.4.1.

Let $\tau$ be any spanning tree of $\hat{G}$, rooted at an arbitrary
degree-$1$ vertex of $\tau$. We start with ${\mathcal{U}}=\emptyset$. Our
algorithm performs a number of iterations, where in each iteration we add one
new set $U\subseteq V(\hat{G})$ of vertices to ${\mathcal{U}}$, such that
$\hat{G}[U]$ is connected and $\left\lfloor|R|/(dr)\right\rfloor\leq|U\cap
R|\leq|R|/r$, and we remove the vertices of $U$ from $\tau$. We execute the
iterations as long as $|V(\tau)\cap R|\geq\left\lfloor|R|/(dr)\right\rfloor$,
after which we terminate the algorithm, and return the current collection
${\mathcal{U}}$ of vertex subsets.

In order to execute an iteration, we let $v$ be the lowest vertex of $\tau$,
such that the subtree $\tau_{v}$ of $\tau$ rooted at $v$ contains at least
$\left\lfloor|R|/(dr)\right\rfloor$ vertices of $R$. Since the maximum vertex
degree in $\hat{G}$ is bounded by $d$, tree $\tau_{v}$ contains fewer than
$d\cdot\left\lfloor|R|/(dr)\right\rfloor\leq|R|/r$ vertices of $R$. We add a
new set $U=V(\tau_{v})$ of vertices to ${\mathcal{U}}$, delete the vertices of
$U$ from $\tau$, and continue to the next iteration.

Let ${\mathcal{U}}$ be the final collection of vertex subsets obtained at the
end of the algorithm. It is immediate to verify that for every set
$U\in{\mathcal{U}}$, $\hat{G}[U]$ is connected and, from the above discussion,
$\left\lfloor|R|/(dr)\right\rfloor\leq|U\cap R|\leq|R|/r$. Therefore,
$|{\mathcal{U}}|\geq r$. $\Box$

####  B.2.2 Proof of Claim 3.4.6.

From the definition of the Path-of-Expanders System, for $3\leq j\leq 6$, the
set $A_{j}\cup B_{j}$ of vertices is well-linked in $S_{j}$. Therefore, there
is a set ${\mathcal{P}}_{j}$ of $w$ node-disjoint paths in $S_{j}$, connecting
$A_{j}$ to $B_{j}$. By concatenating the path sets
${\mathcal{P}}_{3},{\mathcal{P}}_{4},{\mathcal{P}}_{5},{\mathcal{P}}_{6}$, and
the edge sets ${\mathcal{M}}_{3},{\mathcal{M}}_{4},{\mathcal{M}}_{5}$, we
obtain a collection ${\mathcal{P}}$ of $w$ node-disjoint paths in
$G^{\prime\prime}_{\Pi}$, connecting $A_{3}$ to $B_{6}$. We partition
${\mathcal{P}}$ into two subsets: set ${\mathcal{P}}^{(1)}$ contains all paths
originating at the vertices of $W_{1}\cup Y_{1}$, and set
${\mathcal{P}}^{(2)}$ contains all paths originating at the vertices of
$W_{2}\cup Y_{2}$.

We are now ready to define the two graphs $G^{(1)}$ and $G^{(2)}$. Graph
$G^{(1)}$ is obtained from the union of the expanders $T_{3}$ and $T_{4}$, the
paths of ${\mathcal{P}}^{(1)}$, and the edges of
${\mathcal{M}}^{\prime}_{3}\cup{\mathcal{M}}^{\prime}_{4}$ that have an
endpoint lying on the paths of ${\mathcal{P}}^{(1)}$. Graph $G^{(2)}$ is
defined similarly by using $T_{5},T_{6}$, the paths of ${\mathcal{P}}^{(2)}$,
and the edges of ${\mathcal{M}}^{\prime}_{5}\cup{\mathcal{M}}^{\prime}_{6}$
that have an endpoint lying on the paths of ${\mathcal{P}}^{(2)}$. It is
immediate to verify that the graphs $G^{(1)}$ and $G^{(2)}$ are disjoint.

It now remains to show that each of the resulting graphs contains a Duo-of-
Expanders System as a minor, with the required properties. We show this for
$G^{(1)}$; the proof for $G^{(2)}$ is symmetric. Our first step is to contract
every path of ${\mathcal{P}}^{(1)}$ into a single vertex. For each such path
$P\in{\mathcal{P}}^{(1)}$, let $w\in W_{1}\cup Y_{1}$ be the first vertex of
$P$. We denote the new vertex obtained by contracting $P$ by $v(w)$. We let
the backbone $X^{(1)}$ of the new Duo-of-Expanders System
${\mathcal{D}}^{(1)}$ be $X^{(1)}=\left\\{v(w)\mid w\in W_{1}\right\\}$, so
$|X^{(1)}|=w/4$. We map every vertex $w\in W_{1}$ to the corresponding vertex
$v(w)$ in the model of $G_{{\mathcal{D}}^{(1)}}$ that we are constructing in
$G^{(1)}$; that is, we set $f^{(1)}(w)=v(w)$. We also map the two expanders
$T^{(1)}_{1},T^{(1)}_{2}$ of ${\mathcal{D}}^{(1)}$ to $T_{3}$ and $T_{4}$,
respectively, by setting $T^{(1)}_{1}=T_{3}$ and $T^{(1)}_{2}=T_{4}$.

Consider some vertex $w\in W_{1}\cup Y_{1}$ and the path
$P\in{\mathcal{P}}^{(1)}$ originating from $w$. Let $w^{\prime}$ be the unique
vertex of $P$ that belongs to $B_{3}$, and let $w^{\prime\prime}$ be the
unique vertex of $P$ that belongs to $B_{4}$, in the original Path-of-
Expanders System $\Pi$. Recall that there is an edge of
${\mathcal{M}}^{\prime}_{3}$, connecting $w^{\prime}$ to some vertex $u_{w}\in
C_{3}$, and there is an edge of ${\mathcal{M}}^{\prime}_{4}$, connecting
$w^{\prime\prime}$ to some vertex $u^{\prime}_{w}\in C_{4}$. Therefore, there
are edges $(v(w),u_{w})$ and $(v(w),u^{\prime}(w))$ in the new contracted
graph.

We set $D_{0}^{(1)}=\left\\{u_{w}\mid w\in W_{1}\right\\}$, and we let
$\tilde{\mathcal{M}}^{(1)}=\left\\{(v(w),u_{w})\mid w\in W_{1}\right\\}$. We
also set $D_{1}^{(1)}=\left\\{u_{y}\mid y\in\hat{Y}_{1}\right\\}$, and
$D_{1}^{(2)}=\left\\{u^{\prime}_{y}\mid y\in\hat{Y}_{1}\right\\}$. Observe
that all three sets $D^{(1)}_{0},D^{(1)}_{1},D^{(1)}_{2}$ of vertices are
disjoint, and they contain $w/4$ vertices each. It now remains to define the
set $(\tilde{\mathcal{M}}^{\prime})^{(1)}$ of edges, that connect vertices of
$D_{1}^{(1)}$ and $D_{2}^{(1)}$. In order to do so, for every vertex $y\in
Y_{1}$, we merge the two edges $(v(y),u_{y})$ and $(v(y),u^{\prime}_{y})$ into
a single edge, by contracting one of these two edges. The resulting edge is
added to $(\tilde{\mathcal{M}}^{\prime})^{(1)}$. It is easy to see that we
have obtained a Duo-of-Expanders System ${\mathcal{D}}^{(1)}$, whose width is
$w/4$ and expansion $\alpha$. It is easy to verify that the maximum vertex
degree in the corresponding graph $G_{{\mathcal{D}}^{(1)}}$ is bounded by $d$.
Notice that for every vertex $w\in W_{1}$, there is a distinct vertex $v(w)\in
X^{(1)}$, such that $w\in f^{(1)}(v(w))$. Thus, $G^{(1)}$ indeed contain a
Duo-of-Expanders System ${\mathcal{D}}^{(1)}$ with claimed properties as minor
and we have computed its model $f^{(1)}$ in $G^{(1)}$. The proof for $G^{(2)}$
is analogous and Claim 3.4.6 now follows. $\Box$

####  B.2.3 Proof of Claim 3.4.10.

Consider the following sequence of vertex subsets. Let $S_{0}=Z$, and for all
$i>0$, let $S_{i}$ contain all vertices of $S_{i-1}$, and all neighbors of
vertices in $S_{i-1}$. Notice that, if $|S_{i-1}|\leq|V(T)|/2$, then, since
$T$ is an $\alpha^{\prime}$-expander, there are at least
$\alpha^{\prime}|S_{i-1}|$ edges leaving the set $S_{i-1}$, and, since the
maximum vertex degree in $T$ is at most $d$, there are at least
$\frac{\alpha^{\prime}|S_{i-1}|}{d}$ vertices that do not belong to $S_{i-1}$,
but are neighbors of vertices in $S_{i-1}$. Therefore,
$|S_{i}|\geq|S_{i-1}|\left(1+\frac{\alpha^{\prime}}{d}\right)$. We claim that
there must be an index $i^{*}\leq\frac{8d}{\alpha^{\prime}}\log(n/z)$, such
that $|S_{i^{*}}|>|V(T)|/2$. Indeed, otherwise, we get that for
$i=\left\lceil\frac{8d}{\alpha^{\prime}}\log(n/z)\right\rceil$:

$|S_{i^{*}}|\geq|S_{0}|\left(1+\frac{\alpha^{\prime}}{d}\right)^{i}\geq z\cdot
e^{i\alpha^{\prime}/(2d)}\geq z\cdot e^{4\log(n/z)}>n/2.$

Here, the second inequality follows from the fact that $(1+1/x)^{2x}>e$ for
all $x>1$. We construct a similar sequence
$S^{\prime}_{0},S^{\prime}_{1},\ldots,$ for $Z^{\prime}$. Similarly, there is
an index $i^{**}\leq\frac{8d}{\alpha^{\prime}}\log(n/z^{\prime})$, such that
$S^{\prime}_{i^{**}}$ contains more than half the vertices of $T$. Therefore,
there is a path connecting a vertex of $Z$ to a vertex of $Z^{\prime}$, whose
length is at most $\frac{8d}{\alpha^{\prime}}(\log(n/z)+\log(n/z^{\prime}))$.
$\Box$

####  B.2.4 Proof of Claim 3.4.11.

We say that a vertex $v$ of $D_{0}\cap V(T_{1}^{\prime})$ is _happy_ iff there
is a path in $T_{1}^{\prime}$, of length at most $(\gamma\log\log n)/4$,
connecting $v$ to a vertex of $D_{1}^{\prime}$. Assume for contradiction that
the claim is false. Then for each good index $j$, either all vertices of
$Y_{j}^{\prime}$ are unhappy, or all vertices of $Y_{j+r}^{\prime}$ are
unhappy. Let $Z\subseteq D_{0}\cap V(T_{1}^{\prime})$ be the set of all
unhappy vertices. Since $|Y_{j}^{\prime}|,|Y_{j+1}^{\prime}|\geq\sigma/2$, and
$|J^{\prime}|\geq\frac{r\log\log n}{2\log n}$, we get that:

$\displaystyle|Z|$ $\displaystyle\geq\frac{r\log\log n}{2\log
n}\cdot\frac{\sigma}{2}$ $\displaystyle\geq\frac{w\alpha^{2}(\log\log
n)^{3}}{2d^{3}\log^{4}n}\cdot 2^{14}\cdot\left\lfloor\frac{d^{3}n\log
n}{w\alpha^{2}}\right\rfloor$ $\displaystyle\geq\frac{2^{12}n(\log\log
n)^{3}}{\log^{3}n}.$

Let $Z^{\prime}=D_{1}^{\prime}$, so $|Z^{\prime}|\geq w/16$. From Claim
3.4.10, there is a path in $T_{1}^{\prime}$, connecting a vertex of $Z$ to a
vertex of $Z^{\prime}$, of length at most:

$\displaystyle\frac{32d}{\alpha}\left(\log{\left(\frac{n}{|Z|}\right)}+\log{\left(\frac{n}{|Z^{\prime}|}\right)}\right)$
$\displaystyle\leq\frac{32d}{\alpha}\left(\log\left(\frac{\log^{3}n}{2^{13}(\log\log
n)^{3}}\right)+\log{\left(\frac{16n}{w}\right)}\right)$
$\displaystyle\leq\frac{32d}{\alpha}\left(3\log\log
n+\log{\left(\frac{16n}{w}\right)}\right)$
$\displaystyle\leq\frac{\gamma\log\log n}{4},$

since $\gamma=512nd^{2}/(w\alpha)$. This completes the proof of Claim 3.4.11.
$\Box$

####  B.2.5 Proof of Lemma 3.4.12.

Recall that we are given a graph $G=(V,E)$, with $|V|\leq n$ and maximum
vertex degree at most $d$, and a parameter $0<\alpha<1$. We are also given a
collection $\left\\{C_{1},\ldots,C_{2r}\right\\}$ of disjoint subsets of $V$,
each containing $q=\left\lceil cd^{2}\log^{2}n/\alpha^{2}\right\rceil$
vertices, for some constant $c$ to be fixed later. Our goal is to either find
a set ${\mathcal{Q}}=\left\\{Q_{1},\ldots,Q_{r}\right\\}$ of disjoint paths,
such that for each $1\leq j\leq r$, path $Q_{j}$ connects $C_{j}$ to
$C_{j+r}$; or compute a cut $(S,S^{\prime})$ in $G$ of sparsity less than
$\alpha$.

We use a standard definition of multicommodity flow. A _flow_ $f$ consists of
a collection ${\mathcal{P}}$ of paths in $G$, called _flow-paths_ , and, for
each path $P\in{\mathcal{P}}$, an associated flow value $f(P)>0$. The _edge-
congestion_ of $f$ is the maximum amount of flow passing through any edge,
that is, $\max_{e\in E}\left\\{\sum_{\stackrel{{\scriptstyle
P\in{\mathcal{P}}:}}{{e\in P}}}f(P)\right\\}$. We say that the flow in $f$
causes _no edge-congestion_ iff the edge-congestion due to $f$ is at most $1$.
Similarly, the _vertex congestion_ of $f$ is the maximum flow passing through
any vertex, that is, $\max_{v\in V}\left\\{\sum_{\stackrel{{\scriptstyle
P\in{\mathcal{P}}:}}{{v\in P}}}f(P)\right\\}$. If a path $P$ does not lie in
${\mathcal{P}}$, then we implicitly set $f(P)=0$. For any pair $s,t\in V$ of
vertices, let ${\mathcal{P}}(s,t)$ be the set of all paths connecting $s$ to
$t$ in $G$. We say that $f$ _transfers $z$ flow units between $s$ and $t$_ iff
$\sum_{P\in{\mathcal{P}}(s,t)}f(P)\geq z$.

The following theorem is a consequence of Theorem 18 from [LR99] that we prove
after completing the proof of Lemma 3.4.12.

######  Theorem B.2.1.

There is an efficient randomized algorithm, that, given a graph $G=(V,E)$ with
$|V|=n$ and maximum vertex degree at most $d$, and a parameter $0<\alpha<1$,
together with a (possibly partial) matching ${\mathcal{M}}$ over the vertices
of $G$, computes one of the following:

  * •

either a collection
${\mathcal{Q}}^{\prime}=\left\\{Q(u,v)\mid(u,v)\in{\mathcal{M}}\right\\}$ of
paths, such that for all $(u,v)\in{\mathcal{M}}$, path $Q(u,v)$ connects $u$
to $v$; the paths in ${\mathcal{Q}}^{\prime}$ with high probability cause
vertex-congestion at most $\eta=O(d\log n/\alpha)$, and the length of every
path in ${\mathcal{Q}}$ is at most $L=O(d\log n/\alpha)$; or

  * •

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

We are now ready to complete the proof of Lemma 3.4.12. We construct a
matching ${\mathcal{M}}$ over the vertices of $V$, as follows. For each $1\leq
j\leq r$, we add an arbitrary matching ${\mathcal{M}}_{j}$, containing $q$
edges, between the vertices of $C_{j}$ and the vertices $C_{j+r}$. We then set
${\mathcal{M}}=\bigcup_{j=1}^{r}{\mathcal{M}}_{j}$. We apply the algorithm
from Theorem B.2.1 to the graph $G$, parameter $\alpha$ and the matching
${\mathcal{M}}$. If the algorithm returns a cut of sparsity less than
$\alpha$, we terminate the algorithm and return the cut. Therefore, we assume
from now on that the algorithm returns a set ${\mathcal{Q}}^{\prime}$ of paths
with the following properties:

  * •

For each $j\in[r]$, there is a subset
${\mathcal{Q}}^{\prime}_{j}\subseteq{\mathcal{Q}}^{\prime}$ of $q$ paths
connecting vertices of $C_{j}$ to vertices of $C_{j+r}$;

  * •

All paths in ${\mathcal{Q}}^{\prime}$ have length at most $L=O(d\log
n/\alpha)$; and

  * •

With high probability, every vertex of $G$ participates in at most
$\eta=O(d\log n/\alpha)$ paths of ${\mathcal{Q}}^{\prime}$.

If the vertex-congestion caused by the paths in ${\mathcal{Q}}^{\prime}$ is
greater than $\eta$, the algorithm terminates with a failure. Therefore, we
assume from now on that the paths in ${\mathcal{Q}}^{\prime}$ cause vertex-
congestion at most $\eta$. We use the constructive version of the Lovász Local
Lemma by Moser and Tardos [MT10] in order to select one path from each set
${\mathcal{Q}}_{j}^{\prime}$, so that the resulting paths are node-disjoint
with high probability. The next theorem summarizes the symmetric version of
the result of [MT10].

######  Theorem B.2.2 ([MT10]).

Let $X$ be a finite set of mutually independent random variables in some
probability space. Let ${\mathcal{A}}$ be a finite set of bad events
determined by these variables. For each event $A\in{\mathcal{A}}$, let
$\operatorname{vbl}(A)\subseteq X$ be the unique minimal subset of variables
determining $A$, and let $\Gamma(A)\subseteq{\mathcal{A}}$ be a subset of bad
events $B$, such that $A\neq B$, but
$\operatorname{vbl}(A)\cap\operatorname{vbl}(B)\neq\emptyset$. Assume further
that for each $A\in{\mathcal{A}}$, $|\Gamma(A)|\leq D$, $\text{\bf
Pr}\left[A\right]\leq p$, and $ep(D+1)\leq 1$. Then there is an efficient
randomized algorithm that computes an assignment to the variables of $X$, such
that with high probability none of the events in ${\mathcal{A}}$ holds.

For each $1\leq i\leq r$, we choose one of its paths
$Q_{i}\in{\mathcal{Q}}_{i}$ independently at random. We let $z_{i}$ be the
random variable indicating which path has been chosen. For every pair
$Q,Q^{\prime}\in{\mathcal{Q}}^{\prime}$ of intersecting paths, such that
$Q,Q^{\prime}$ belong to distinct sets
${\mathcal{Q}}^{\prime}_{i},{\mathcal{Q}}^{\prime}_{j}$ let
${\cal{E}}(Q,Q^{\prime})$ be the bad event that both these paths were
selected. Notice that the probability of ${\cal{E}}(Q,Q^{\prime})$ is
$1/q^{2}$. Notice also that
$\operatorname{vbl}({\cal{E}}(Q,Q^{\prime}))=\left\\{z_{i},z_{j}\right\\}$,
where
$Q\in{\mathcal{Q}}^{\prime}_{i},Q^{\prime}\in{\mathcal{Q}}^{\prime}_{j}$.
There are at most $qL\eta$ events ${\cal{E}}(\hat{Q},\hat{Q}^{\prime})$, with
$z_{i}\in\operatorname{vbl}({\cal{E}}(Q,Q^{\prime}))$: set
${\mathcal{Q}}^{\prime}_{i}$ contains $q$ paths; each of these paths has
length at most $L$, so there are at most $qL$ vertices that participate in the
paths in ${\mathcal{Q}}^{\prime}_{i}$. Each such vertex may be shared by at
most $\eta$ other paths. Similarly, there are at most $qL\eta$ events
${\cal{E}}(\hat{Q},\hat{Q}^{\prime})$, with
$z_{j}\in\operatorname{vbl}({\cal{E}}(Q,Q^{\prime}))$. Therefore,
$|\Gamma({\cal{E}}(Q,Q^{\prime}))|\leq 2qL\eta$. Let $D=2qL\eta$. It now only
remains to show that $(D+1)ep\leq 1$. Indeed,

$(D+1)ep=\frac{O(qL\eta)}{q^{2}}=\frac{O(L\eta)}{q}=O\left(\frac{d^{2}\log^{2}n}{\alpha^{2}q}\right).$

By choosing the constant $c$ in the definition of $q$ to be large enough, we
can ensure that $(D+1)ep\leq 1$ holds. Using the algorithm from Theorem B.2.2,
we obtain a collection ${\mathcal{Q}}=\left\\{Q_{1},\ldots,Q_{r}\right\\}$ of
paths in $G$, where for each $j\in[r]$, path $Q_{j}$ connects a vertex of
$C_{j}$ to a vertex of $C_{j+r}$, and with high probability the resulting
paths are disjoint. This completes the proof of Lemma 3.4.12, except for the
proof of Theorem B.2.1 that we provide next.

####  B.2.6 Proof of Theorem B.2.1.

We use a slight adaptation of Theorem 18 from [LR99].

######  Theorem B.2.3 (Adaptation of Theorem 18 from [LR99]).

There is an efficient algorithm, that, given a $n$-vertex graph $G$ with
maximum vertex degree at most $d$, together with a parameter $0<\alpha<1$
computes one of the following:

  * •

either a flow $f$ in $G$, with every pair of vertices in $G$ transferring
$\frac{\alpha}{64n\log n}$ flow units to each other with no edge-congestion,
such that every flow-path has length at most $\frac{64d\log n}{\alpha}$; or

  * •

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

We provide the proof of Theorem B.2.3 below, after completing the proof of
Theorem B.2.1 using it.

We apply Theorem B.2.3 to the graph $G$ and the parameter $\alpha$. If the
algorithm returns a cut $(S,S^{\prime})$ of sparsity less than $\alpha$, then
we terminate the algorithm and return this cut. Therefore, we assume from now
on that the algorithm returns the flow $f$. Let $f^{\prime}$ be a flow
obtained from $f$ by scaling it up by factor $64\log n/\alpha$, so that every
pair of vertices in $G$ now sends $1/n$ flow units to each other, with total
edge-congestion at most $64\log n/\alpha$.

We start by showing that there is a multi-commodity flow $f^{*}$, where every
pair $(u,v)\in{\mathcal{M}}$ of vertices sends one flow unit to each other
simultaneously, on flow-paths of length at most $128d\log n/\alpha$, with
total vertex-congestion at most $128d\log n/\alpha$. Let
$(u,v)\in{\mathcal{M}}$ be any pair of vertices. The new flow between $u$ and
$v$ is defined as follows: $u$ sends $1/n$ flow units to every vertex of $G$,
using the flow $f^{\prime}$, and $v$ collects $1/n$ flow units from every
vertex of $G$, using the flow $f^{\prime}$. In other words, the flow $f^{*}$
between $u$ and $v$ is obtained by concatenating all flow-paths in
$f^{\prime}$ originating at $u$ with all flow-paths in $f^{\prime}$
terminating at $v$. It is easy to see then that every flow-path in
$f^{\prime}$ is used at most twice: once by each of its endpoints; all flow-
paths in $f^{*}$ have length at most $128d\log n/\alpha$; and the total edge-
congestion due to flow $f^{*}$ is at most $128\log n/\alpha$. Since the
maximum vertex degree in $G$ is at most $d$, flow $f^{*}$ causes vertex-
congestion at most $128d\log n/\alpha$.

Next, for every pair $(u,v)\in{\mathcal{M}}$, we select one path
$Q(u,v)\in{\mathcal{P}}(u,v)$ at random, where a path $P\in{\mathcal{P}}(u,v)$
is selected with probability $f^{*}(P)$ – the amount of flow sent on $P$ by
$f^{*}$. We then let
${\mathcal{Q}}^{\prime}=\left\\{Q(u,v)\mid(u,v)\in{\mathcal{M}}\right\\}$.
Notice that the length of every path in ${\mathcal{Q}}^{\prime}$ is at most
$128d\log n/\alpha$. It remains to show that the total vertex-congestion due
to paths in ${\mathcal{Q}}^{\prime}$ is at most $O(d\log n/\alpha)$ with high
probability. This is done by standard techniques. Consider some vertex $x\in
V$. We say that the bad event ${\cal{E}}(x)$ happens if more than $8\cdot
128d\log n/\alpha$ paths of ${\mathcal{Q}}$ use the vertex $x$. We use the
following variation of the Chernoff bound (see [DP09]):

######  Fact B.2.4.

Let $X_{1},\ldots,X_{n}$ be independent random variables taking values in
$[0,1]$, let $X=\sum_{i}X_{i}$, and let $\mu=\text{\bf E}\left[X\right]$. Then
for all $t>2e\mu$, $\text{\bf Pr}\left[X>t\right]\leq 2^{-t}$.

It is easy to see that the expected number of paths in
${\mathcal{Q}}^{\prime}$ that contain $x$ is at most $128d\log n/\alpha$, and
so the probability of ${\cal{E}}(x)$ is bounded by $1/n^{4}$. From the Union
Bound, the probability that any such event happens for any vertex $x\in V$ is
bounded by $1/n^{3}$. Therefore, with high probability, every vertex of $G$
belongs to $2^{10}d\log n/\alpha=O(d\log n/\alpha)$ paths in
${\mathcal{Q}}^{\prime}$. This finishes the proof of Theorem B.2.1 except for
the proof of Theorem B.2.3, that we prove in the next sub-section. $\Box$

####  B.2.7 Proof of Theorem B.2.3

The proof follows closely that of [LR99]; we provide it here for completeness.
Recall that we are given a graph $G=(V,E)$ with maximum vertex-degree at most
$d$, $|V|=n$ and a parameter $0<\alpha<1$. We let $L=64d\log n/\alpha$. For
every pair $u,v$ of vertices in $V$, let ${\mathcal{P}}^{\leq L}(u,v)$ be the
set of all paths in $G$ between $u$ and $v$ that contain at most $L$ vertices.
We employ standard linear program for uniform multicommodity flow:

(LP-1) $\displaystyle\max\quad\quad f^{*}$ s.t.
$\displaystyle\sum_{P\in{\mathcal{P}}^{\leq L}(u,v)}f(P)\geq f^{*}$
$\displaystyle\forall u,v\in V$ $\displaystyle\sum_{u,v\in
V}\sum_{\stackrel{{\scriptstyle P\in{\mathcal{P}}^{\leq L}(u,v):}}{{e\in
P}}}f(P)\leq 1$ $\displaystyle\forall e\in E$ $\displaystyle f(P)\geq 0$
$\displaystyle\forall u,v\in V;\forall P\in{\mathcal{P}}^{\leq L}(u,v)$

In general, the dual of the standard relaxation of the uniform multicommodity
flow problem is the problem of assigning lengths $\ell(e)$ to the edges $e\in
E$, so as to minimize $\sum_{e}\ell(e)$, subject to the constraint that the
total sum of all pairwise distances between pairs of vertices is at least $1$,
where the distance between pairs of vertices is defined with respect to
$\ell$.

In our setting, given lengths $\ell(e)$ on edges $e\in E$, we need to use
$L$-hop bounded distances between vertices, defined as follows: for all
$u,v\in V$, if ${\mathcal{P}}^{\leq L}(u,v)\neq\emptyset$, then we let:

$D^{\leq L}_{\ell}(u,v)=\min_{P\in{\mathcal{P}}^{\leq
L}(u,v)}\left\\{\sum_{e\in P}\ell(e)\right\\};$