runs the algorithm of Lemma 4.5.2 on the level-$i$ partitions ${\mathcal{B}}$
and ${\mathcal{B}}^{\prime}$ along with parameters $Z_{0}$ and $Z_{i}$, and
reports its outcome. Indeed, ${\mathsf{AlgCase}}_{\mathsf{1}}$ is a
$O(1)$-canonical distinguisher algorithm and has space complexity
$\tilde{O}\left(\frac{X_{i}}{Z_{i}}+\frac{Z_{0}}{Z_{i}}\right)$.

We will now show that this space complexity is upper bounded by
$N^{1/2-\epsilon+o(1)}$. Indeed, in this special case, we have
$\frac{X_{i}}{Z_{i}}\leq N^{1/2-\epsilon}$. Moreover, from Observation 4.5.1,
we can assume w.l.o.g. that
$\frac{X_{i}}{Z_{i}}\leq\frac{X_{0}}{Z_{0}}=\frac{N}{Z_{0}}$, or in other
words, $\frac{Z_{0}}{Z_{i}}\leq\frac{N}{X_{i}}=\eta^{i}\leq N^{1/2-\epsilon}$.
Here, we have used the fact that $i<(1/2-\epsilon)r$ and
$r=r(N,\eta)=\left\lfloor\frac{\log N}{\log\eta}\right\rfloor$. Thus, the
space complexity of ${\mathsf{AlgCase}}_{\mathsf{1}}$ is indeed bounded by
$\tilde{O}(N^{1/2-\epsilon})\leq N^{1/2-\epsilon+o(1)}$ and the corollary now
follows.

This completes the proof of the special case $1$ where $X_{i}/Z_{i}\leq
N^{1/2-\epsilon}$ for some level $0\leq i<(1/2-\epsilon)r$. We now turn
towards proving Lemma 4.5.2. Recall that we are given a sequence $S$ of length
$N$ taking distinct values in the range $H^{*}=(1,\ldots,N)$ and level-$i$
partitions ${\mathcal{B}}$ and ${\mathcal{B}}^{\prime}$ along with parameters
$Z_{0}$ and $Z_{i}$. The central ingredient of our proof, that we will also
use in the future, is the notion of _block-processing algorithm_ that we
describe next.

###### Block-Processing Algorithm.

The input to the block-processing algorithm is a LIS problem is a stream-block
$B$ of the original input stream $S$ along with a partition
${\mathcal{B}}^{\prime}$ of the range $H^{*}$ into range-blocks. The algorithm
is given access to the elements of $B$ as they arrive as a part of the
original input stream $S$. We say that a range-block
$B^{\prime}\in{\mathcal{B}}^{\prime}$ is _$(Z,\Delta)$ -perfect for $B$_ iff
there is an increasing subsequence in $B\cap B^{\prime}$ of length $Z$ that
does not contain any of the first $\Delta Z$ elements of $B\cap B^{\prime}$.
The goal of the block-processing algorithm is to output some subset
${\mathcal{B}}^{*}\subseteq{\mathcal{B}}^{\prime}$ by reporting their
respective indices. For thresholds $Z$ and $\Delta$, and a parameter
$\alpha\geq 1$, we say that a (probabilistic) block-processing algorithm is an
$(Z,\Delta,\alpha)$-approximation algorithm iff the following guarantees hold:

  * •

_Soundness Guarantee._ With probability at least $3/4$, _every_ range-block
$B^{\prime}\in{\mathcal{B}}^{*}$ has
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(B\cap B^{\prime})\geq Z/\alpha$;

  * •

_Completeness Guarantee._ Each range-block
$B^{\prime}\in{\mathcal{B}}^{\prime}$ that is $(Z,\Delta)$-perfect for $B$ is
present in ${\mathcal{B}}^{*}$ with probability at least $3/4$.

######  Claim 4.5.4.

For each parameter $Z$ there is a block-processing algorithm with space
complexity $\tilde{O}\left({|B|/{Z}}\right)$ that achieves
$(Z,1,2)$-approximation, where $B$ is the input stream-block.

We give a sketch of the proof of the above claim here, while the complete
proof, using standard techniques, is deferred to Section C.2.1. The key idea
is to sample the elements of $B$ at the rate of roughly $1/Z$ as they appear
in the stream. We say that a range-block $B^{\prime}\in{\mathcal{B}}^{\prime}$
is ‘suspicious’ if we sample an element whose value lies in $B^{\prime}$. We
show that we will identify all range-blocks $B^{\prime}$ containing a large
number of values from $B$, which in turn are the only ones that can possibly
induce a large enough increasing subsequence in $B$. Moreover, we can also
guarantee that we will identify suspicious range-blocks early on: there is
still a large enough induced subsequence present in the subsequent elements of
$B$. We can now use algorithm $\mathsf{Alg}_{2}$ from Lemma 4.2.2 on the
sampled blocks for these subsequent elements to find ones having large enough
induced increasing subsequence. Since we mark roughly $|B|/Z$ range-blocks as
suspicious and for each suspicious block $B^{\prime}$ we use roughly $O(|B\cap
B^{\prime}|/Z)$ space, our overall space complexity is also bounded by
$O\left(|B|/Z\right)+O\left(\sum_{B^{\prime}}\left\lceil|B\cap
B^{\prime}|/Z\right\rceil\right)=O\left({|B|/Z}\right)$ as required. Here, the
summation is over all suspicious range-blocks, which in turn is a subset of
the partition ${\mathcal{B}}^{\prime}$. We are now ready to prove Lemma 4.5.2
that will complete the analysis of this case.

Proof of Lemma 4.5.2. We are given a partition
${\mathcal{B}}={\mathcal{B}}^{i}_{\Psi}(S)=\left\\{B_{1},\ldots,B_{m}\right\\}$
of $S$ into $m=\eta^{i}$ stream-blocks, each of size exactly
$X_{i}=N/\eta^{i}$. Similarly, we are given a partition
${\mathcal{B}}^{\prime}={\mathcal{B}}^{i}_{\Psi^{\prime}}(H^{*})=\left\\{B^{\prime}_{1},\ldots,B^{\prime}_{m^{\prime}}\right\\}$
of the range $H^{*}$ into a number of range-blocks.

For each stream-block $B_{k}\in{\mathcal{B}}$, when the elements of $B_{k}$
arrive as a part of the stream $S$, we apply the block-processing algorithm
$\mathsf{Alg}\mathsf{BlockProc}$ of Claim 4.5.4 with parameter $Z=Z_{i}/2$ and
the set ${\mathcal{B}}^{\prime}$ of range-blocks. Let
${\mathcal{B}}^{\prime}_{k}\subseteq\left\\{1,\ldots,m^{\prime}\right\\}$ be
the set of indices of the range-blocks returned by
$\mathsf{Alg}\mathsf{BlockProc}$. Consider now a stream ${\mathcal{S}}$ that
contains elements of the sets
${\mathcal{B}}^{\prime}_{1},\ldots,{\mathcal{B}}^{\prime}_{k^{*}}$ in the
reversed order of that elements. In other words, the stream ${\mathcal{S}}$
can be divided into $k^{*}$ chunks, one chunk corresponding to each stream-
block $B_{k}\in{\mathcal{B}}$. The chunk corresponding to $B_{k}$ contains the
elements of ${\mathcal{B}}^{\prime}_{k}$ in the decreasing order of their
values. Notice that the range of this stream ${\mathcal{S}}$ is
${\mathcal{H}}^{*}=\left\\{1,\ldots,m^{\prime}\right\\}$. We apply the
algorithm $\mathsf{Alg}_{1}$ of Lemma 4.2.1 on the stream ${\mathcal{S}}$ with
parameter $\left\lceil Z_{0}/10Z_{i}\right\rceil$ and report its answer. This
completes the description of our algorithm, and we now turn to analyze its
properties.

From the guarantees of $\mathsf{Alg}_{1}$ and Claim 4.5.4, the space
complexity of our algorithm is indeed bounded by
$\max_{B\in{\mathcal{B}}}\left(\tilde{O}\left({\frac{|B|}{Z_{i}}}\right)\right)+O\left(\frac{Z_{0}}{Z_{i}}\right)=\tilde{O}\left(\frac{X_{i}+Z_{0}}{Z_{i}}\right)$
as claimed. Furthermore, it is immediate to verify that if we report yes,
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)\geq\frac{Z_{0}}{10Z_{i}}\cdot\frac{Z_{i}}{2}=\frac{Z_{0}}{20}$
must hold with probability at least $3/4$. This completes the proof of
soundness guarantee of our algorithm.

We now show the completeness guarantee. Assume that there is a
$\Upsilon$-canonical subsequence $S^{*}$ of $S$ of length $Z_{0}$. Our goal is
to show that in this case, we report in affirmative with probability at least
$3/4$. Consider a level=$i$ yes-pair $(B_{j},B^{\prime}_{j^{\prime}})$ of
$S^{*}$. Note that $B^{\prime}_{j^{\prime}}$ is a $(Z_{i}/2,1)$-perfect range-
block for $B_{j}$. Hence, from the correctness guarantee of
$\mathsf{Alg}\mathsf{BlockProc}$ of Claim 4.5.4,
$j^{\prime}\in{\mathcal{B}}^{\prime}_{j}$ with probability at least $3/4$. We
consider an increasing subsequence ${\mathcal{S}}^{*}$ of ${\mathcal{S}}$ that
is obtained as follows. For each yes-pair
$(B_{j},B^{\prime}_{j^{\prime}})\in{\mathcal{B}}\times{\mathcal{B}}^{\prime}$
of $S^{*}$, if $B^{\prime}\in{\mathcal{B}}^{\prime}_{j^{\prime}}$, we choose
the element $j^{\prime}$ present in the chunk corresponding to $B_{j}$ of
${\mathcal{S}}$ to lie in ${\mathcal{S}}^{*}$. It is immediate to verify that
${\mathcal{S}}^{*}$ is indeed an increasing subsequence of ${\mathcal{S}}$.
Moreover, each yes-block $B_{j}\in{\mathcal{B}}$ participates in a fresh
execution of $\mathsf{Alg}\mathsf{BlockProc}$ and hence, the element
corresponding to each level-$i$ yes-pair of $S^{*}$ is present in
${\mathcal{S}}^{*}$ independently with probability at least $3/4$ each. We
first consider the case where $Z_{i}\leq Z_{0}\leq 10Z_{i}$. In this case,
with probability at least $3/4$, we correctly identify at least one yes-pair
and report yes. Thus, assume from now on that $Z_{0}>10Z_{i}$. From the above
discussion, $\text{\bf
E}\left[\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}({\mathcal{S}}^{*})\right]\geq\frac{3}{4}\cdot\frac{|S^{*}|}{Z_{i}}=\frac{3Z_{0}}{4Z_{i}}$.
From Chernoff bound (4.2.4),

$\text{\bf Pr}\left[|{\mathcal{S}}^{*}|\leq\frac{Z_{0}}{4Z_{i}}\right]\leq
e^{-\left(\frac{2}{9}\text{\bf
E}\left[\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}({\mathcal{S}}^{*})\right]\right)}\leq
e^{-\left(\frac{2}{9}\cdot\frac{3Z_{0}}{4Z_{i}}\right)}=e^{-\left(\frac{1}{6}\cdot\frac{Z_{0}}{Z_{i}}\right)}\leq
e^{-\frac{10}{6}}<\frac{1}{4}.$

Thus, with probability at least $3/4$, we have
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}({\mathcal{S}}^{*})\geq|{\mathcal{S}}^{*}|>\frac{Z_{0}}{4Z_{i}}>\left\lceil\frac{Z_{0}}{10Z_{1}}\right\rceil$
and we report yes. This completes the proof of Lemma 4.5.2. $\Box$

In this subsection, we have shown an $O(1)$-canonical distinguisher algorithm
${\mathsf{AlgCase}}_{\mathsf{1}}$ assuming that there is a level $0\leq
i<(1/2-\epsilon)r$ such that $\frac{X_{i}}{Z_{i}}\leq N^{1/2-\epsilon}$. In
the remainder of this section we can now assume:

######  Assumption 4.5.5.

For each level $0\leq i<(1/2-\epsilon)r$,
$\frac{X_{i}}{Z_{i}}>N^{1/2-\epsilon}$.

####  4.5.2 Special Case 2: Yes-pairs Share Many Common Elements

Recall that we have fixed parameters $N$ and $\eta$, both integral powers of
$2$, such that $\eta$ grows with $N$. In this subsection, we are given an LIS
problem instance $S$ in the streaming model. We assume that
$S=(a_{1},\ldots,a_{N})$ 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. From Assumption 4.5.5, $X_{i}/Z_{i}>N^{1/2-\epsilon}$ holds for
each level $0\leq i<(1/2-\epsilon)r$. In this subsection, we assume that there
is some level $3\epsilon r\leq i<(1/2-\epsilon)r$ with $\Delta_{i}\geq
Z_{i}N^{5\epsilon}$. We fix such a level $i$, and we will show an
$O(1)$-canonical distinguisher algorithm ${\mathsf{AlgCase}}_{\mathsf{2}}$
with space complexity $N^{1/2-\epsilon+o(1)}$.

As in Section 4.5.1, the core of our algorithm is a block-processing algorithm
exploiting the structure of $\Upsilon$: the fact that, $\Delta_{i}\geq
Z_{i}N^{5\epsilon}$. Unlike in Section 4.5.1 this block-processing algorithm
operates on a carefully chosen intermediate level $0\leq j<i$. We use the
following simple claim, whose proof is present in Section C.2.2.1.

######  Claim 4.5.6.

There is a level $j\geq i-3\epsilon r$ such that $2Z_{i}\leq Z_{j}\leq\eta
Z_{i}$.

We fix a level $j\geq i-3\epsilon r\geq 0$ as guaranteed by Claim 4.5.6. We
consider the collection ${\mathcal{B}}={\mathcal{B}}_{\Psi}^{j}(S)$ of
level-$j$ stream-blocks and the collection
${\mathcal{B}}^{\prime}={\mathcal{B}}_{\Psi^{\prime}}^{j}(H^{*})$ of level-$j$
range-blocks. We are now ready to state our block-processing algorithm for
this special case. The input to this algorithm is a level-$j$ stream-block
$B\in{\mathcal{B}}$ of the original input stream $S$ along with the level-$j$
partition ${\mathcal{B}}^{\prime}$ of $H^{*}$. Recall that we say a range-
block $B^{\prime}$ is $(Z,\Delta)$-perfect for $B$ iff there is an increasing
subsequence that does not use first $\Delta Z$ elements of $B\cap B^{\prime}$.
Further, recall that we say that a block-processing algorithm achieves
$(Z,\Delta,\alpha)$-approximation iff with probability at least $3/4$, every
reported range-block $B^{\prime}$ has
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(B\cap B^{\prime})\geq Z/\alpha$ and
each range-block that is $(Z,\Delta)$-perfect for $B$ is reported
independently with probability at least $3/4$. In the following claim, we show
a block-processing algorithm that is optimized for this special case.

######  Claim 4.5.7.

There is a block-processing algorithm $\mathsf{Alg}\mathsf{BlockProc}$ that
achieves $(Z_{j}/2,\Delta_{i}/8,1)$-approximation with space complexity
$N^{1/2-\epsilon+o(1)}$, where the input stream-block is a level-$j$ stream-
block and the partition of $H^{*}$ is the level-$j$ partition
${\mathcal{B}}^{j}_{\Psi^{\prime}}(H^{*})$.

The proof of Claim 4.5.7 follows closely that of Claim 4.5.4 and is deferred
to Section C.2.2.2, We are now ready to describe the main algorithm
${\mathsf{AlgCase}}_{\mathsf{2}}$ of this subsection.

######  Corollary 4.5.8.

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$,
where $\bm{Z}=(Z_{0},\ldots,Z_{r})$ and
$\bm{\Delta}=(\Delta_{0},\ldots,\Delta_{r})$. Further assume that there is a
level $3\epsilon r\leq i\leq(1/2-\epsilon)r$ with $\Delta_{i}\geq
Z_{i}N^{5\epsilon}$. Then there is a $O(1)$-canonical distinguisher algorithm
${\mathsf{AlgCase}}_{\mathsf{2}}$ with space complexity
$N^{1/2-\epsilon+o(1)}$.

###### Proof.

We proceed exactly as in the proof of Lemma 4.5.2. Recall that we have fixed a
level $j$ and level-$j$ partitions ${\mathcal{B}}$ and
${\mathcal{B}}^{\prime}$. We let
${\mathcal{B}}=\left\\{B_{1},\ldots,B_{m}\right\\}$ and
${\mathcal{B}}^{\prime}=\left\\{B^{\prime}_{1},\ldots,B^{\prime}_{m^{\prime}}\right\\}$
be their constituent blocks in their natural order.

We initialize a new LIS problem instance ${\mathcal{S}}$ with range
${\mathcal{H}}^{*}=\left\\{1,\ldots,m^{\prime}\right\\}$. We now describe the
procedure to generate elements of ${\mathcal{S}}$. We will ensure that the
sequence ${\mathcal{S}}$ can be divided into $m$ chunks, each corresponding to
a level-$j$ stream-block of ${\mathcal{B}}$. These chunks appear in the
natural order of these level-$j$ stream-blocks. Consider a stream-block
$B_{k}\in{\mathcal{B}}$. When its elements arrive as a part of the sequence
$S$, we apply the block-processing algorithm $\mathsf{Alg}\mathsf{BlockProc}$
of Claim 4.5.7 and let ${\mathcal{B}}^{\prime}_{k}$ be the indices of the
range-blocks of ${\mathcal{B}}^{\prime}$ it reports. The chunk of
${\mathcal{S}}$ corresponding to $B_{k}$ contains the elements of
${\mathcal{B}}^{\prime}_{k}$ in decreasing order of their indices. We run in
parallel algorithm $\mathsf{Alg}_{1}$ of Lemma 4.2.1 on this stream
${\mathcal{S}}$ with the parameter $\left\lceil Z_{0}/10Z_{j}\right\rceil$. At
the end of stream $S$, we terminate the stream ${\mathcal{S}}$ and report the
answer of $\mathsf{Alg}_{1}$ on ${\mathcal{S}}$. This completes the
description of our algorithm ${\mathsf{AlgCase}}_{\mathsf{2}}$.

By proceeding exactly as in Lemma 4.5.2, we verify that
${\mathsf{AlgCase}}_{\mathsf{2}}$ is indeed the desired $O(1)$-canonical
distinguisher algorithm for this case. Notice that there is at most $1$
execution of $\mathsf{Alg}\mathsf{BlockProc}$ at a time. Thus, the space
complexity of ${\mathsf{AlgCase}}_{\mathsf{2}}$ is bounded by that of
$\mathsf{Alg}\mathsf{BlockProc}$ and $\mathsf{Alg}_{1}$. From Lemmas 4.2.1 and
4.5.7 this is bounded by,

$N^{1/2-\epsilon+o(1)}+O\left(\left\lceil\frac{Z_{0}}{10Z_{j}}\right\rceil\right)\leq
N^{1/2-\epsilon+o(1)}.$

Here, the inequality follows from Observation 4.5.1 since,

$\frac{Z_{0}}{Z_{j}}\leq\frac{X_{0}}{X_{j}}=\frac{N}{N/\eta^{j}}=\eta^{j}<\eta^{i}<\eta^{(1/2-\epsilon)r}\leq
N^{1/2-\epsilon}.$

In this subsection, we have shown an $O(1)$-canonical distinguisher algorithm
${\mathsf{AlgCase}}_{\mathsf{2}}$ with space complexity
$N^{1/2-\epsilon+o(1)}$ assuming that there is a level $3\epsilon r\leq
i<(1/2-\epsilon)r$ such that $\Delta_{i}\geq N^{5\epsilon}$. In the remainder
of this section, in addition to Assumption 4.5.5, we also assume:

######  Assumption 4.5.9.

For each level $3\epsilon r\leq i<(1/2-\epsilon)r$,
$\Delta_{i}<Z_{i}N^{5\epsilon}$.

####  4.5.3 LIS Streaming Algorithm with Space Complexity
$N^{1/2+O(\epsilon)}$

Recall that we have fixed parameters $N$ and $\eta$, both integral powers of
$2$, such that $\eta$ grows 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. Recall that we denote the size of the level-$i$ stream-blocks of
the hierarchical partition ${\mathcal{B}}_{\Psi}^{i}(S)$ by $X_{i}$, for each
level $i\in{\mathcal{I}}$. Also recall that we have fixed an optimal
$\Upsilon$-canonical subsequence $S^{*}$ of $S$. In this section, we will
devise an $N^{o(1)}$-canonical distinguisher algorithm with space complexity
$N^{1/2+O(\epsilon)}$. Even though this is worse bound than that achieved by
algorithm $\mathsf{Alg}_{3}$ of Lemma 4.2.3, this algorithm will serve as an
important guiding principle in the analysis of special cases $3$ and $4$ that
we will describe and analyze in the subsequent subsections.

We fix a threshold-level $r^{*}=\left\lfloor(1/2-4\epsilon)r\right\rfloor$ and
define the set ${\mathcal{I}}^{*}=\left\\{i\>:\>0\leq i<r^{*}\text{ and
}Z_{i}>Z_{i+1}\right\\}$ of special levels. Denote
${\mathcal{I}}^{*}=\left\\{i_{0},\ldots,i_{k^{*}}\right\\}$ where
$k^{*}:=|{\mathcal{I}}^{*}|-1$ and the levels are indexed in their natural
order so that $i_{0}<i_{1}<\ldots<i_{k^{*}}$. We will need the following
consequence of Assumption 4.5.5, whose proof is deferred to Section C.2.3.1.

######  Claim 4.5.10.

$k^{*}\geq\left(\frac{1}{2}-7\epsilon\right)r\geq\frac{r}{3}$.

For each pair $i_{k}<i_{k^{\prime}}$ of levels of ${\mathcal{I}}^{*}$, we let
$\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)}$.
In other words,
$e^{\zeta(i_{k},i_{k^{\prime}})}=\eta^{2(i_{k^{\prime}}-i_{k})}\cdot\left(\prod_{k<k^{\prime\prime}\leq
k^{\prime}}\psi_{i_{k^{\prime\prime}}}\right)$. Using Property P4 of the
ensemble $\Upsilon$, we immediately obtain the following fact:

######  Fact 4.5.11.

Fix levels $i_{k},i_{k^{\prime}}\in{\mathcal{I}}^{*}$ with $0\leq
k<k^{\prime}\leq k^{*}$. Consider a level-$i_{k}$ pair $(B,B^{\prime})$ and
the sets ${\mathcal{B}}$ and ${\mathcal{B}}^{\prime}$ of
level-$i_{k^{\prime}}$ descendant-blocks of $B$ and $B^{\prime}$ respectively.
Then
$e^{\zeta(i_{k},i_{k^{\prime}})}\geq|{\mathcal{B}}|^{2}|{\mathcal{B}}^{\prime}|$.

###### Algorithm for different levels.

In this section, we will present $1+k^{*}$ different algorithms, one for each
level $i_{k}\in{\mathcal{I}}^{*}$. These algorithms will be parametrized 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}}^{*}$. The level-$i$ algorithm, that we
denote by ${\mathsf{Alg}}\mathsf{Level}{(i)}$, will be responsible for
‘classifying’ level-$i$ pairs. Formally, ${\mathsf{Alg}}\mathsf{Level}{(i)}$
takes as an input a level-$i$ pair $(B^{*},B^{*^{\prime}})$ and a subblock
$B^{**}$ of $B^{*}$. Note that $B^{*}$ is a level-$i$ block in the level-$i$
partition ${\mathcal{B}}^{i}_{\Psi}$ of the original input stream $S$ into
stream-blocks. Similarly, $B^{*^{\prime}}$ is a level-$i$ block in the
level-$i$ partition ${\mathcal{B}}^{i}_{\Psi^{\prime}}$ of the original range
$H^{*}$ into range-blocks. Thus, $B^{*}$ and $B^{*^{\prime}}$ can be
identified by their indices in ${\mathcal{B}}^{i}_{\Psi}$ and
${\mathcal{B}}^{i}_{\Psi^{\prime}}$ respectively. We assume that
${\mathsf{Alg}}\mathsf{Level}{(i)}$ is given these indices as input. On the
other hand, $B^{**}$ is an arbitrary subblock of $B^{*}$: it may not belong to
any level of the hierarchical partition ${\mathcal{B}}_{\Psi}$ of $S$. The
algorithm ${\mathsf{Alg}}\mathsf{Level}{(i)}$ is then given access to the
elements of $B^{**}$ as they arrive as a part of the block $B^{*}$, which in
turn is a part of the original input sequence $S$.

######  $(\alpha_{i},\alpha^{\prime}_{i})$-canonical distinguisher algorithm.

For parameters $\alpha^{\prime}_{i}\geq\alpha_{i}\geq 1$, we say that the
level-$i$ algorithm ${\mathsf{Alg}}\mathsf{Level}{(i)}$ is an
_$(\alpha_{i},\alpha^{\prime}_{i})$ -canonical distinguisher_ iff for each
input level-$i$ pair $(B^{*},B^{*^{\prime}})$ and the subblock $B^{**}$ of
$B^{*}$ it achieves the following guarantees:

  * •

if $(B^{*},B^{*^{\prime}})$ is a level-$i$ yes-pair for $S^{*}$ and
$|S^{*}\cap B^{**}|\geq Z_{i}/\alpha_{i}$, then it reports yes with
probability at least $3/4$; and

  * •

if $\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(B^{**}\cap
B^{*^{\prime}})<Z_{i}/\alpha^{\prime}_{i}$, then it reports no with
probability at least $3/4$.

The main result of this subsection is the existence of a level-$i_{k}$
$(\alpha_{i_{k}},\alpha^{\prime}_{i_{k}})$-canonical distinguisher algorithm
${\mathsf{Alg}}\mathsf{Level}{(i_{k})}$ with low space complexity where
$\alpha_{i_{k}}=4$ and $\alpha^{\prime}_{i_{k}}=2^{3(k^{*}-k)+2}$, for each
level $i_{k}\in{\mathcal{I}}^{*}$. We summarize this in the following lemma:

######  Lemma 4.5.12.

Consider a level $i_{k}\in{\mathcal{I}}^{*}$. Further assume that if
$k<k^{*}$, we are also given a level-$i_{k+1}$
$(\alpha_{i_{k+1}},\alpha^{\prime}_{i_{k+1}})$-canonical distinguisher
algorithm ${\mathsf{Alg}}\mathsf{Level}{(i_{k+1})}$. Then, there is a
level-$i_{k}$ $(\alpha_{i_{k}},\alpha^{\prime}_{i_{k}})$-canonical
distinguisher algorithm ${\mathsf{Alg}}\mathsf{Level}{(i_{k})}$ that achieves
the following guarantees:

  * •

Calls to ${\mathsf{Alg}}\mathsf{Level}{(i_{k+1})}$: if $k<k^{*}$, it performs
at most $\zeta^{2}(i_{k},i_{k+1})\frac{\mu_{i_{k}}}{\mu_{i_{k+1}}}$ concurrent
calls to ${\mathsf{Alg}}\mathsf{Level}{(i_{k+1})}$; and

  * •

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

We complete the proof of Lemma 4.5.12 after describing the main algorithm of
this subsection assuming it. Applying the above lemma recursively for levels
of ${\mathcal{I}}^{*}$ in their decreasing order, we obtain the level-$i_{0}$
$(\alpha_{i_{0}},\alpha^{\prime}_{i_{0}})$-canonical distinguisher algorithm
${\mathsf{Alg}}\mathsf{Level}{(i_{0})}$. In the following claim, we analyze
its space complexity.

######  Claim 4.5.13.

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

###### Proof.

The level-$i_{0}$ algorithm ${\mathsf{Alg}}\mathsf{Level}{(i_{0})}$ performs a
number of calls to the lower-level algorithms
$\left\\{{\mathsf{Alg}}\mathsf{Level}{(i_{k})}\>|\>i_{k}\in{\mathcal{I}}^{*}\text{
and }i_{k}>i_{0}\right\\}$ as subroutines. Consider some level
$i\in{\mathcal{I}}^{*}$ and a level-$i$ stream-block $B$. We denote
$\mathsf{load}(B)$ as the maximum number of concurrent calls to the level-$i$
algorithm ${\mathsf{Alg}}\mathsf{Level}{(i)}$ in which $B$ participates. We
define $\mathsf{load}(i):=\max_{B\in{\mathcal{B}}^{i}_{\Psi}}\mathsf{load}(B)$
to be the maximum ‘load’ across all level-$i$ stream-blocks
${\mathcal{B}}^{i}_{\Psi}$. To bound the space complexity of
${\mathsf{Alg}}\mathsf{Level}{(i_{0})}$, we will need the following two claims
whose proofs are deferred to LABEL:{prf:_ncm-lis-somple-load-i-k-bound} and
LABEL:{clm:_ncm-lis-simple-pi-zeta-bound} respectively.

######  Claim 4.5.14.

For each level $i=i_{k}\in{\mathcal{I}}^{*}$,
$\mathsf{load}(i_{k})\leq\frac{\mu_{i_{0}}}{\mu_{i_{k}}}\cdot\zeta^{2}(i_{0},i_{1})\cdot\ldots\cdot\zeta^{2}(i_{k-1},i_{k})$.

######  Claim 4.5.15.

$\zeta(i_{0},i_{1})\cdot\ldots\cdot\zeta(i_{k^{*}-1},i_{k^{*}})\leq N^{o(1)}$.

We are now ready to provide an upper bound for the space complexity of
${\mathsf{Alg}}\mathsf{Level}{(i_{0})}$. We consider its state when processing
some element $a_{t}\in S$. For each level $i\in{\mathcal{I}}^{*}$, we let
$B_{i}\in{\mathcal{B}}^{i}_{\Psi}$ denote the unique level-$i$ stream-block
that contains $a_{t}$. Consider now some level $i\in{\mathcal{I}}^{*}$ and
observe that $B_{i}$ participates in all active calls to the level-$i$
algorithm ${\mathsf{Alg}}\mathsf{Level}{(i)}$. Since there are at most
$\mathsf{load}(i)$ such calls and from Lemma 4.5.12, the space used by each
such run, excluding the space used by the lower level algorithms is bounded by
$N^{6\epsilon}$, we conclude that the space complexity of
${\mathsf{Alg}}\mathsf{Level}{(i_{0})}$ is at most,

$\displaystyle\sum_{i\in{\mathcal{I}}^{*}}\mathsf{load}(i)\cdot N^{6\epsilon}$
$\displaystyle\leq|{\mathcal{I}}^{*}|\cdot\max_{i\in{\mathcal{I}}^{*}}{\left(\mathsf{load}(i)\right)}\cdot
N^{6\epsilon}$ $\displaystyle\leq
r^{*}\cdot\frac{\mu_{i_{0}}}{\mu_{i_{k^{*}}}}\cdot\zeta^{2}(i_{0},i_{1})\cdot\ldots\cdot\zeta^{2}(i_{k^{*}-1},i_{k^{*}})\cdot
N^{6\epsilon}$ $\displaystyle\leq N^{o(1)}\cdot\mu_{0}\cdot
N^{6\epsilon+o(1)}$ $\displaystyle\leq N^{1/2+7\epsilon+o(1)}.$

Here, the third inequality follows from Claim 4.5.15 and the last inequality
follows from the fact that $\mu_{0}\leq N^{1/2+\epsilon}$ (see, Observation
4.5.1). This completes the proof of Claim 4.5.13.

In Section C.2.3.4, we prove the following observation.

######  Observation 4.5.16.

Suppose there is a level-$i_{0}$ $(\alpha,\alpha^{\prime})$-canonical
distinguisher algorithm $\mathsf{Alg}(i_{0})$. Then there is a
$\alpha^{\prime}$-canonical distinguisher algorithm
$\mathsf{Alg}_{\mathsf{simp}}$, that performs at most $N^{o(1)}$ concurrent
calls to $\mathsf{Alg}(i_{0})$, and whose space complexity, excluding the
space required by the calls to $\mathsf{Alg}(i_{0})$, is at most $N^{o(1)}$.

From LABEL:{clm:_ncm-simple-alglevel-0-space} and LABEL:{obs:_ncm-
alglevel-0-suffices}, and using the fact that
$\alpha^{\prime}_{i_{0}}=2^{O(r^{*})}=N^{o(1)}$, we immediately obtain the
main algorithm of this subsection.

######  Corollary 4.5.17.

There is a $N^{o(1)}$-canonical distinguisher algorithm
$\mathsf{Alg}_{\mathsf{simp}}$ with space complexity $N^{1/2+7\epsilon+o(1)}$.

In the remainder of the subsection, we prove Lemma 4.5.12. We fix an integer
$0\leq k\leq k^{*}$ and the corresponding level $i_{k}\in{\mathcal{I}}^{*}$.
We first consider the case where $k\in\left\\{k^{*}-1,k^{*}\right\\}$, that
serves as the ‘base cases’ of our algorithm.

######  ${\mathsf{Alg}}\mathsf{Level}{(i_{k})}$ with
$k\in\left\\{k^{*}-1,k^{*}\right\\}$.

The input to the algorithm ${\mathsf{Alg}}\mathsf{Level}{(i_{k})}$ is a
level-$i_{k}$ pair $(B^{*}B^{*^{\prime}})$ and a subblock $B^{**}$ of $B^{*}$.
It is given access to the elements of $B^{**}$ as they arrive as the part of
the original input stream $S$. On this input, the algorithm
${\mathsf{Alg}}\mathsf{Level}{(i_{k})}$ runs the algorithm $\mathsf{Alg}_{1}$
from Lemma 4.2.1 for the input stream $B^{**}\cap B^{*^{\prime}}$ with the
parameter $Z=Z_{i_{k}}/4$. If $\mathsf{Alg}_{1}$ reports yes, it reports yes,
and otherwise it reports no.

######  ${\mathsf{Alg}}\mathsf{Level}{(i_{k})}$ with $0\leq k\leq k^{*}-2$.

The input to the algorithm ${\mathsf{Alg}}\mathsf{Level}{(i_{k})}$ is a
level-$i_{k}$ pair $(B^{*}B^{*^{\prime}})$ and a subblock $B^{**}$ of $B^{*}$.
We consider the level $i_{k+1}$ and for the sake of readability, we denote
$i:=i_{k}$ and $j:=i_{k+1}$. Note that $j>i$ and $j\in{\mathcal{I}}^{*}$. In
this case, we have already defined the level-$j$ algorithm
${\mathsf{Alg}}\mathsf{Level}{(j)}$, and we will use it as our subroutine.

Let ${\mathcal{H}}^{*}$ be the set of indices of the level-$j$ descendant
range-blocks of $B^{*^{\prime}}$ in ${\mathcal{B}}^{j}_{\Psi^{\prime}}$. We
initialize a new LIS problem instance ${\mathcal{S}}$ in the streaming model
with the range ${\mathcal{H}}^{*}$. We populate the elements of
${\mathcal{S}}$ while processing the subblock $B^{**}$ when its elements
arrive as the part of the block $B^{*}$ of the original input sequence $S$, as
follows. We process the elements of $B^{**}$ in their natural order,
discarding the elements that do not have their values in the range-block
$B^{*^{\prime}}$. We sample the elements of $B^{**}\cap B^{*^{\prime}}$
independently at random with probability $p_{j}:=\frac{2^{6}}{Z_{j}\mu_{j}}$
each as they arrive as the part of the original input stream. For each element
$a_{t}$ that is chosen, we proceed as follows. Let
$\hat{B}\in{\mathcal{B}}^{j}_{\Psi}$ be the unique level-$j$ descendant
stream-block of $B^{*}$ containing $a_{t}$. Similarly, let
$\hat{B}^{\prime}\in{\mathcal{B}}^{j}_{\Psi^{\prime}}$ be the unique level-$j$
descendant range-block of $B^{*}$ containing its value. We denote by
$\hat{B}_{>t}$ the subblock of $\hat{B}$ consisting of its elements appearing
after $a_{t}$. We now execute $\left\lfloor 2^{5}\zeta(i,j)\right\rfloor$
parallel instances of the level-$j$ algorithm
${\mathsf{Alg}}\mathsf{Level}{(j)}$ with input level-$j$ pair
$(\hat{B},\hat{B}^{\prime})$ along with the subblock $\hat{B}_{>t}$ of
$\hat{B}$. If at any point, we sample more than
$\frac{2^{10}\mu_{i}}{\mu_{j}}$ elements from $B^{*}$, we immediately halt our
algorithm and report no. At the end of the level-$j$ stream-block $\hat{B}$,
all the calls to level-$j$ algorithms terminate. Let
$\left\\{r_{1},\ldots,r_{\ell}\right\\}$ be the indices of the level-$j$
range-blocks in ${\mathcal{B}}^{j}_{\Psi^{\prime}}$ in their natural order,
for whom at least $2^{4}\zeta(i,j)$ corresponding executions of
${\mathsf{Alg}}\mathsf{Jump}{(j)}$ reported yes. We now append the elements
$\left\\{r_{\ell},\ldots,r_{1}\right\\}$ to ${\mathcal{S}}$ in this order. At
the end of the subblock $B^{**}$, we terminate the sequence ${\mathcal{S}}$.

We run the algorithm $\mathsf{Alg}_{1}$ of Lemma 4.2.1 on this instance
${\mathcal{S}}$ with the parameter $Z=\frac{Z_{i}}{8Z_{j}}$. If
$\mathsf{Alg}_{1}$ on input ${\mathcal{S}}$ answers yes, we report yes, and
otherwise we report no. This completes the description of our algorithm
${\mathsf{Alg}}\mathsf{Level}{(i)}$. We now turn to analyze its properties,
starting with correctness.

###### Soundness.

Consider the execution of ${\mathsf{Alg}}\mathsf{Level}{(i)}$ with input
level-$i$ pair $(B^{*},B^{*^{\prime}})$ and the subblock $B^{**}$ of $B^{*}$.
Assume that $\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(B^{*}\cap
B^{*^{\prime}})<Z_{i}/\alpha^{\prime}_{i}$. Our goal is to show that we report
no with probability at least $3/4$.

We proceed by induction. We first consider the case where
$k\in\left\\{k^{*},k^{*}-1\right\\}$. In this case, $\alpha^{\prime}_{i}\geq
4$ and from the correctness guarantee of Lemma 4.2.1, if we report yes,
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(B\cap B^{*^{\prime}})\geq
Z_{i}/4\geq Z_{i}/\alpha^{\prime}_{i}$ must hold. Thus, assume from now on
that $0\leq k\leq k^{*}-2$ and the soundness guarantee holds for each level
$i_{k^{\prime}}\in{\mathcal{I}}^{*}$ with $k<k^{\prime}\leq k^{*}$. Let
$j=i_{k+1}$ and let ${\mathcal{S}}$ be the sequence as constructed by the run
of ${\mathsf{Alg}}\mathsf{Level}{(i)}$.

######  Claim 4.5.18.

With probability at least $3/4$, for every increasing subsequence
${\mathcal{S}}^{\prime}$ of ${\mathcal{S}}$, there is an increasing sequence
of size at least
$|{\mathcal{S}}^{\prime}|\cdot\frac{Z_{j}}{\alpha^{\prime}_{j}}$ in
$B^{**}\cap B^{*^{\prime}}$.

The proof of Claim 4.5.18 follows from a standard application of Chernoff
bound and is deferred to Section C.2.3.5. If we report yes, from the
correctness guarantee of Lemma 4.2.1,
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}({\mathcal{S}})\geq{Z_{i}}/{8Z_{j}}$
must hold. But then from Claim 4.5.18, with probability at least $3/4$,

$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(B^{**}\cap
B^{*^{\prime}})\geq\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}({\mathcal{S}})\cdot\frac{Z_{j}}{\alpha^{\prime}_{j}}\geq\frac{Z_{i}}{8Z_{j}}\cdot\frac{Z_{j}}{\alpha^{\prime}_{j}}=\frac{Z_{j}}{8\alpha^{\prime}_{j}}=\frac{Z_{i}}{\alpha^{\prime}_{i}}.$

Here, the inequality follows since $j>i$ and
$\alpha^{\prime}_{i}\alpha^{\prime}_{i_{k}}=8\alpha^{\prime}_{i_{k+1}}=8\alpha^{\prime}_{j}$.
This completes the proof of soundness of
${\mathsf{Alg}}\mathsf{Level}{(i_{k})}$, completing the induction step.

###### Completeness.

Consider level $i=i_{k}$ and the execution of
${\mathsf{Alg}}\mathsf{Level}{(i)}$ with input level-$i$ pair
$(B^{*},B^{*^{\prime}})$ and the subblock $B^{**}$ of $B^{*}$. Assume that
there is an $\Upsilon$-canonical increasing subsequence $S^{*}$ of $S$ of
length $Z_{0}$. Further assume that $(B^{*},B^{*^{\prime}})$ is a level-$i$
yes-pair for $S^{*}$ with $|B^{**}\cap S^{*}|\geq{Z_{i}}/\alpha_{i}$. Our goal
is to show that we report yes with probability at least $3/4$.

We proceed by induction. We first consider the case where
$k\in\left\\{k^{*},k^{*}-1\right\\}$. From the correctness guarantee of Lemma
4.2.1, if $\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(B\cap B^{*^{\prime}})\geq
Z_{i}/\alpha_{i}=Z_{i}/4$, we indeed report yes. Thus, assume from now on that
$0\leq k\leq k^{*}-2$ and the completeness guarantee holds for each level
$i_{k^{\prime}}\in{\mathcal{I}}^{*}$ with $k<k^{\prime}\leq k^{*}$. We fix
level $j=i_{k+1}$ and let ${\mathcal{S}}$ be the sequence as constructed by
the execution of ${\mathsf{Alg}}\mathsf{Level}{(i)}$. Recall that we execute
the algorithm $\mathsf{Alg}_{1}$ from Lemma 4.2.1 with parameter
$Z=\frac{Z_{i}}{8Z_{j}}$. From the correctness guarantee of Lemma 4.2.1, it
suffices to show that,
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}({\mathcal{S}})\geq\frac{Z_{i}}{8Z_{j}}$
with probability at least $\frac{3}{4}$.

We let ${\mathcal{B}}$ and ${\mathcal{B}}^{\prime}$ be the set of all
level-$j$ descendant stream-blocks of $B^{*}$ and the set of all level-$j$
descendant range-blocks of $B^{*^{\prime}}$ respectively. Consider a level-$j$
descendant yes-pair
$(B,B^{\prime})\in{\mathcal{B}}\times{\mathcal{B}}^{\prime}$ of
$(B^{*},B^{*^{\prime}})$. We say that $(B,B^{\prime})$ is a _happy pair_ iff:
(i) we sample some element $a_{t^{\prime}}\in B\cap B^{\prime}$; (ii) at least
$2^{4}\zeta(i,j)$ executions of the level-$j$ algorithm
${\mathsf{Alg}}\mathsf{Level}{(j)}$ with input level-$j$ pair $(B,B^{\prime})$
and the subblock $B_{>t^{\prime}}$ of $B$ reports in affirmative; and (iii) at
the end of processing stream-block $B$, we sample at most
$2^{10}\frac{\mu_{i}}{\mu_{j}}$ of elements of $B\cap B^{*^{\prime}}$. We use
the following claim whose proof via standard techniques is deferred to Section
C.2.3.6.

######  Claim 4.5.19.

With probability at least $0.9$, there are at least $\frac{Z_{i}}{8Z_{j}}$
happy pairs.

We assume from now on that there is a set ${\mathcal{P}}$ of at least
$\ell\geq\frac{Z_{i}}{8Z_{j}}$ happy pairs that we denote by
${\mathcal{P}}=\left\\{(B_{r_{1}},B^{\prime}_{r^{\prime}_{1}}),\ldots,(B_{r_{\ell}},B^{\prime}_{r^{\prime}_{\ell}})\right\\}$
in their natural order. Here, $\left\\{r_{1},\ldots,r_{\ell}\right\\}$ and
$\left\\{r^{\prime}_{1},\ldots,r^{\prime}_{\ell}\right\\}$ are the indices of
the underlying level-$j$ stream-blocks and level-$j$ range-blocks in
${\mathcal{B}}^{j}_{\Psi}$ and ${\mathcal{B}}^{j}_{\Psi^{\prime}}$
respectively, and $r_{1}<r_{2}<\ldots<r_{\ell}$ and
$r^{\prime}_{1}<r^{\prime}_{2}<\ldots<r^{\prime}_{\ell}$. Notice that the
corresponding elements in ${\mathcal{S}}$ with values
$\left\\{r^{\prime}_{1},\ldots,r^{\prime}_{\ell}\right\\}$ appear in this
order and form an increasing subsequence in ${\mathcal{S}}$. Hence,
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}({\mathcal{S}})\geq\ell\geq\frac{Z_{i}}{8Z_{j}}$.
This completes the proof of completeness of
${\mathsf{Alg}}\mathsf{Level}{(i)}$.

###### Calls to ${\mathsf{Alg}}\mathsf{Level}{(i_{k+1})}$.

Consider a level $i=i_{k}\in{\mathcal{I}}^{*}$. If
$k\in\left\\{k^{*},k^{*}-1\right\\}$, we do not perform any calls to lower
level algorithms and there is nothing to show. Assume from now on that $0\leq
k\leq k^{*}-2$ and fix the level $j:=i_{k+1}$. Recall that for each sampled
element $a_{t}\in B^{*}\cap B^{*^{\prime}}$, we perform either exactly
$\left\lfloor 2^{5}\zeta(i,j)\right\rfloor$ or $0$ calls to
${\mathsf{Alg}}\mathsf{Level}{(j)}$. Also recall that if we sample more than
$\frac{2^{10}\mu_{i}}{\mu_{j}}$ elements from $B^{*}$, we immediately halt our
algorithm. Thus, the number of concurrent calls to
${\mathsf{Alg}}\mathsf{Level}{(j)}$ is at most $\left\lfloor
2^{5}\zeta(i,j)\right\rfloor\cdot\frac{2^{10}\mu_{i}}{\mu_{j}}\leq\zeta^{2}(i,j)\cdot\frac{\mu_{i}}{\mu_{j}}$.
Here, the inequality follows since $\zeta(i,j)\geq\log\eta\geq 2^{15}$ since
$\eta$ is large enough.

###### Space complexity.

Consider a level $i=i_{k}\in{\mathcal{I}}^{*}$. If
$k\in\left\\{k^{*},k^{*}-1\right\\}$, from the guarantee of Lemma 4.2.1, our
space complexity is $O(Z_{i_{k}})$. It is also easy to verify that
$Z_{i_{k^{*}}}=Z_{r^{*}}$ and $Z_{i_{k^{*}-1}}\leq\eta Z_{i_{k^{*}}}=\eta
Z_{r^{*}}<\eta^{2}N^{5\epsilon}$. Here, the last inequality follows from
Assumption 4.5.5 and the facts that
$r^{*}=\left\lfloor(1/2-4\epsilon)r\right\rfloor$ and
$r=r(N,\eta)=\left\lfloor\log N/\log\eta\right\rfloor$, since,

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

Thus, the space complexity of a single execution of level-$i$ algorithms
${\mathsf{Alg}}\mathsf{Level}{(i)}$ is bounded by
$O(Z_{i})=O(\eta^{2}N^{5\epsilon})\leq N^{5\epsilon+o(1)}$, since
$\eta=N^{o(1)}$ is small enough.

Assume from now on that $0\leq k\leq k^{*}-2$, and we let $j:=i_{k+1}$ be the
corresponding level. Let ${\mathcal{S}}$ be the sequence as constructed by the
execution of ${\mathsf{Alg}}\mathsf{Level}{(i)}$. Recall that the range of
${\mathcal{S}}$ is ${\mathcal{H}}^{*}$: the indices of range-blocks in the
level-$j$ partition ${\mathcal{B}}_{\Psi^{\prime}}^{j}$ of the original range
$H^{*}$; and each element with value in ${\mathcal{H}}^{*}$ can be stored in
unit space. From the guarantee of Lemma 4.2.1, we can execute a run of
$\mathsf{Alg}_{1}$ on the stream ${\mathcal{S}}$ with values in
${\mathcal{H}}^{*}$ with parameter $Z=Z_{i}/(8Z_{j})$ in space
$O(Z_{i}/Z_{j})=O(\eta)$. We now analyze the space required to populate
elements of ${\mathcal{S}}$. Consider some level-$j$ descendant stream-block
$B$ of $B^{**}$. When we are processing $B$, we perform a number of calls to
the level-$j$ algorithm ${\mathsf{Alg}}\mathsf{Level}{(j)}$. Depending on the
outcome of these calls, we add elements to ${\mathcal{S}}$. We can charge the
space used in computing these additional elements to the space freed after the
respective calls to ${\mathsf{Alg}}\mathsf{Level}{(j)}$ terminate. Thus, the
space used by ${\mathsf{Alg}}\mathsf{Level}{(i)}$ in this case, excluding the
space used by the calls to ${\mathsf{Alg}}\mathsf{Level}{(j)}$ is bounded by
$O(\eta)\leq N^{o(1)}$.

This completes the analysis of ${\mathsf{Alg}}\mathsf{Level}{(i)}$ and Lemma
4.5.12 now follows.

In this subsection, we presented an $N^{o(1)}$-canonical distinguisher
algorithm with space complexity $N^{1/2+O(\epsilon)}$. To achieve this, we
introduced the set ${\mathcal{I}}^{*}$ of special levels and recursively
defined algorithms
$\left\\{{\mathsf{Alg}}\mathsf{Level}{(i)}\>|\>i\in{\mathcal{I}}^{*}\right\\}$.
In Section 4.5.4 we establish that the underlying ensemble $\Upsilon$ must
satisfy at least one of the two technical conditions that we define. If it
follows the first technical condition (special case $3$), we show in Section
4.5.5 that there are ‘better’ algorithms for certain levels. We can then swap
the algorithms of these respective levels in
$\left\\{{\mathsf{Alg}}\mathsf{Level}{(i)}\right\\}$ and show that the
resulting level-$i_{0}$ algorithm is an $N^{o(1)}$-canonical distinguisher
algorithm with space complexity $N^{1/2-\epsilon+o(1)}$. Otherwise, if it
follows the second technical condition (special case $4$), we show in Section
4.5.8 that exploiting the query-efficient algorithm
$\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ for the NCM problem in hybrid model
yields ‘better’ algorithms for certain levels. As before, we can then swap the
algorithms of these respective levels in
$\left\\{{\mathsf{Alg}}\mathsf{Level}{(i)}\right\\}$ and show that the
resulting level-$i_{0}$ algorithm is an $N^{o(1)}$-canonical distinguisher
algorithm with space complexity $N^{1/2-\epsilon+o(1)}$.

####  4.5.4 Processing the Ensemble

Recall that we have fixed parameters $N$ and $\eta$, both integral powers of
$2$, such that $\eta$ grows 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)$. 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$. From
Assumptions 4.5.5 and 4.5.9, we know 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\\}$ of special levels.
The goal of this section is to describe the technical conditions that will
serve as special cases $3$ and $4$. The main result of this subsection is a
dichotomy lemma that establishes that, at least one of these four special
cases must hold. Prior to stating this lemma, we require some further
definitions.

###### Weight of levels and savable levels.

For each level $0\leq i_{k}<i_{k^{*}}$ of ${\mathcal{I}}^{*}$, we define
${w_{i_{k}}:=\log_{\eta}(\mu_{i_{k}}/\mu_{i_{k+1}})}$ to be its _weight_. For
the level $i_{k^{*}}$ of ${\mathcal{I}}^{*}$, we define $w_{i_{k^{*}}}:=0$.
For a subset ${\mathcal{I}}^{\prime}\subseteq{\mathcal{I}}^{*}$ of levels, we
say that $w_{{\mathcal{I}}^{\prime}}:=\sum_{i\in{\mathcal{I}}^{\prime}}w_{i}$
is the _weight of ${\mathcal{I}}^{\prime}$_. We say that a level
$i\in{\mathcal{I}}^{*}$ is a _savable level_ if $0.9<w_{i}<100$.

###### Jumpable tuples.

Consider a tuple $\tau=(i_{k},j,\ell)$ of levels of ${\mathcal{I}}^{*}$ where
$j=i_{k^{\prime}}$ and $\ell=i_{k^{\prime\prime}}$. Consider the collection
${\mathcal{I}}(\tau):=\left\\{i_{k},i_{k+1},\ldots,i_{k^{\prime}-1}\right\\}$
of levels of ${\mathcal{I}}^{*}$ corresponding to the tuple $\tau$. We refer
to
$w_{{\mathcal{I}}(\tau)}=\log_{\eta}{\left(\frac{\mu_{i_{k}}}{\mu_{j}}\right)}$
as the _level-weight_ of $\tau$. We say that $\tau$ is a _jumpable tuple_ iff
$0\leq k<k^{\prime}<k^{\prime\prime}<k^{*}$ and
$k^{\prime\prime}=k^{\prime}+\left\lfloor
0.3w_{{\mathcal{I}}(\tau)}\right\rfloor$. We say that a jumpable tuple $\tau$
is a _perfect_ jumpable tuple if $w_{{\mathcal{I}}(\tau)}\geq 100$,
$k^{\prime}\leq k+\frac{w_{{\mathcal{I}}(\tau)}}{100}$, and
$Z_{j}\geq{Z_{\ell}}\cdot{\eta^{0.2w_{{\mathcal{I}}(\tau)}}}$.

###### Independent collection of jumpable tuples.

We say that a collection ${\mathcal{J}}$ of jumpable tuples is _independent_
iff for each pair of jumpable tuples $\tau=(i,j,\ell)$ and
$\tau^{\prime}=(i^{\prime},j^{\prime},\ell^{\prime})$ of ${\mathcal{J}}$,
either $\ell<i^{\prime}$ or $\ell^{\prime}<i$. We let
${\mathcal{I}}({\mathcal{J}})=\bigcup_{\tau\in{\mathcal{J}}}{\mathcal{I}}(\tau)$
be the collection of levels of ${\mathcal{I}}^{*}$ corresponding to the tuples
present in ${\mathcal{J}}$. We denote by
$w_{{\mathcal{I}}({\mathcal{J}})}=\sum_{\tau\in{\mathcal{J}}}w_{{\mathcal{I}}(\tau)}$
the _level-weight of the collection ${\mathcal{J}}$ of jumpable tuples_.

We are now ready to state the main dichotomy lemma of this subsection.

######  Lemma 4.5.20.

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$
with the corresponding collection ${\mathcal{I}}$ of levels that satisfies
Assumptions 4.5.5 and 4.5.9 as mentioned earlier. Then either there is an
independent collection ${\mathcal{J}}^{*}$ of perfect jumpable tuples with
level-weight $w_{{\mathcal{I}}({\mathcal{J}}^{*})}\geq\frac{r}{10^{5}}$ or
there is a collection ${\mathcal{I}}_{\mathsf{savable}}\subseteq{\mathcal{I}}$
of savable levels with weight
$w_{{\mathcal{I}}_{\mathsf{savable}}}\geq\frac{r}{10^{5}}$.

###### Proof.

We are given an ensemble
$\Upsilon=(\Psi=\Psi^{*}(N,\eta),\Psi^{\prime},\bm{Z},\bm{\Delta},\bm{\mu})$
with levels ${\mathcal{I}}=\left\\{0,\ldots,r\right\\}$, where we let
$\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})$. Recall that we have fixed a subset
${\mathcal{I}}^{*}=\left\\{i_{0},\ldots,i_{k^{*}}\right\\}\subseteq{\mathcal{I}}$
of special levels. Let
${\mathcal{I}}_{\mathsf{savable}}\subseteq{\mathcal{I}}^{*}$ be the set of all
the savable levels. We assume that
$w_{{\mathcal{I}}_{\mathsf{savable}}}<\frac{r}{10^{5}}$ since otherwise there
is nothing to show. Our objective is to construct an independent collection
${\mathcal{J}}^{*}$ of perfect jumpable tuples with level-weight
$w_{{\mathcal{I}}({\mathcal{J}}^{*})}\geq\frac{r}{10^{5}}$.

Our construction consists of two phases. In the first phase, we develop an
algorithm that processes all the levels of ${\mathcal{I}}^{*}$, while
gradually building a collection of independent jumpable tuples ${\mathcal{J}}$
with sufficiently large level-weight. Unfortunately, some of these jumpable
tuples ${\mathcal{J}}$ may not be perfect. To rectify this, in the second
phase, we refine this set of jumpable tuples to obtain a subset
${\mathcal{J}}^{*}\subseteq{\mathcal{J}}$ of perfect jumpable tuples with
large enough level-weight. Before we describe our algorithm of the first
phase, we need some additional definitions.

Consider a pair $0\leq k<k^{\prime}\leq k^{*}$ of integers and let $i_{k}$ and
$i_{k^{\prime}}$ be the corresponding levels of ${\mathcal{I}}^{*}$. We define
$\mathsf{cover}(k,k^{\prime}):=\min{\left(k^{\prime}+\left\lfloor
0.3\log_{\eta}{\left(\frac{\mu_{i_{k}}}{\mu_{i_{k^{\prime}}}}\right)}\right\rfloor,k^{*}\right)}$.

Consider an integer $0\leq k<k^{*}$ and the corresponding level
$i_{k}\in{\mathcal{I}}^{*}$. We define $\mathsf{jump}(k)>k$ to be the smallest
integer $k^{\prime}$ such that
$\log_{\eta}{\left(\frac{\mu_{i_{k}}}{\mu_{\ell}}\right)}\leq
100\log_{\eta}{\left(\frac{\mu_{i_{k}}}{\mu_{j}}\right)}$, where
$j=i_{k^{\prime}}$ and $\ell=i_{\mathsf{cover}(k,k^{\prime})}$. We first claim
that such an integer $\mathsf{jump}(k)$ exists and $\mathsf{jump}(k)\leq
k^{*}$ holds. To this end, it suffices to show that the above-mentioned
condition holds for $k^{\prime}=k^{*}$. Indeed, in this case, $j=i_{k^{*}}$,
$\mathsf{cover}(k,k^{*})=k^{*}$, and $\ell=i_{k^{*}}$, implying that the
above-mentioned condition trivially holds (see, Observation 4.5.1). We also
define $\mathsf{land}(k):=\mathsf{cover}(k,\mathsf{jump}(k))$.

We are now ready describe the first phase of our algorithm. We initialize the
set ${\mathcal{J}}=\emptyset$ and will ensure that ${\mathcal{J}}$ remains a
collection of independent jumpable tuples. We start by processing levels of
${\mathcal{I}}^{*}=\left\\{i_{0},\ldots,i_{k^{*}}\right\\}$, starting at level
$i_{0}$, in their natural increasing order.

Consider a level $i_{k}\in{\mathcal{I}}^{*}$. If $k=k^{*}$, we terminate our
process and report our current collection of independent jumpable tuples
${\mathcal{J}}$. In this case, we say that $i_{k}$ is the last level that we
processed. Otherwise, if $w_{i_{k}}<100$, we do not update ${\mathcal{J}}$ and
continue to process the subsequent level of ${\mathcal{I}}^{*}$. Assume from
now on that $w_{i_{k}}\geq 100$. Let $\mathsf{jump}(k)$ and $\mathsf{land}(k)$
be the integers as defined above. We consider the tuple
$\tau(k):=(i_{k},i_{\mathsf{jump}(k)},i_{\mathsf{land}(k)})$. If
$\mathsf{land}(k)<k^{*}$, $\tau(k)$ is indeed a jumpable tuple, and we update
our collection of jumpable tuples
${\mathcal{J}}\leftarrow{\mathcal{J}}\cup\left\\{\tau(k)\right\\}$. Also
observer that ${\mathcal{J}}$ remains an independent collection of jumpable
tuples. We now proceed to process the level $i_{1+\mathsf{land}(k)}$ of
${\mathcal{I}}^{*}$. Otherwise, if $\mathsf{land}(k)=k^{*}$, we terminate our
algorithm without updating our collection ${\mathcal{J}}$. In this case, we
say that $i_{k}$ is the last level that we processed. This completes the
description of the first phase our algorithm. Before we describe our pruning
step, we analyze the guarantees of this algorithm.

Let $i_{k^{\prime}}\in{\mathcal{I}}^{*}$ with $0\leq k^{\prime}\leq k^{*}$ be
the last level that we process before terminating our algorithm. We also let
${\mathcal{I}}^{\prime}:=\left\\{i_{0},\ldots,i_{k^{\prime}-1}\right\\}$ be
the set of levels of ${\mathcal{I}}^{*}$ appearing before $i_{k^{\prime}}$.
Recall that we say that a level $i_{k}\in{\mathcal{I}}^{*}$ is a savable level
if $0.9<w_{i}<100$. Consider an integer $0\leq k\leq k^{*}$ such that the
corresponding level $i_{k}$ is not a savable level. We say that it is a
_featherweight_ level if $w_{i}\leq 0.9$, and a _heavyweight_ level if
$w_{i}\geq 100$. We will use the following claims whose proofs are deferred to
LABEL:{prf-clm:_ncm-i-star-sep} and LABEL:{prf-clm:_ncm-large-w-star}
respectively.

######  Claim 4.5.21.

$i_{k^{\prime}}\geq k^{\prime}\geq\frac{r}{6}$.

######  Claim 4.5.22.

$w_{{\mathcal{I}}^{\prime}}>k^{\prime}-\frac{r}{1000}$.

We are now ready to show that the level-weight $w_{{\mathcal{J}}}$ of our
collection ${\mathcal{J}}$ of independent jumpable levels is sufficiently
large.

######  Claim 4.5.23.

$w_{{\mathcal{I}}({\mathcal{J}})}\geq\frac{r}{10^{4}}$.

###### Proof.

Before giving a lower bound on the level-weight of the set ${\mathcal{J}}$ of
jumpable levels, we first show that it is not an empty set.

######  Observation 4.5.24.

${\mathcal{J}}\neq\emptyset$.

###### Proof.

Assume otherwise for contradiction that ${\mathcal{J}}=\emptyset$. We claim
that there are no heavyweight levels in ${\mathcal{I}}^{\prime}$. Indeed,
assume that there is some heavyweight level $i_{k}\in{\mathcal{I}}^{\prime}$.
Then, we must have processed the level $i_{k}$ to obtain levels
$\mathsf{jump}(k)$ and $\mathsf{land}(k)$. If $\mathsf{land}(k)<k^{*}$, we
must have added a jumpable tuple $\tau(k)$ to our collection ${\mathcal{J}}$,
contradicting the fact that ${\mathcal{J}}=\emptyset$. On the other hand, if
$\mathsf{land}(k)=k^{*}$, we must have terminated our algorithm immediately,
contradicting the fact that $i_{k}$ is not the last level that we processed.
Thus, there are no heavyweight levels in ${\mathcal{I}}^{\prime}$, or in other
words, each level of ${\mathcal{I}}^{\prime}$ is either a savable level or a
featherweight level.

Next, we claim that $w_{{\mathcal{I}}^{\prime}}\leq
0.9k^{\prime}+\frac{r}{1000}$. To this end, note that
$w_{{\mathcal{I}}^{\prime}}=\sum_{i\in{\mathcal{I}}^{\prime}}w_{i}$, and we
bound the contribution of each level in ${\mathcal{I}}^{\prime}$ separately.
Since there are only $k^{\prime}$ such levels, the contribution due to
featherweight levels, each of which has weight at most $0.9$, is trivially
bounded by $0.9k^{\prime}$. On the other hand, from our assumption, the weight
of savable levels is less than $\frac{r}{10^{5}}$. Thus,
$w_{{\mathcal{I}}^{\prime}}\leq\frac{9}{10}k^{\prime}+\frac{r}{10^{5}}$. But
from Claim 4.5.22, we must have
$w_{{\mathcal{I}}^{\prime}}>k^{\prime}-\frac{r}{1000}$. Combining these two
bounds, we obtain, $\frac{1}{10}k^{\prime}<\frac{2r}{1000}$, or in other
words, $k^{\prime}<\frac{r}{50}$, a contradiction to Claim 4.5.21. This
completes the proof of Observation 4.5.24.

We now focus on showing that the level-weight $w_{{\mathcal{J}}}$ is large.
Consider a jumpable tuple $\tau(k)\in{\mathcal{J}}$. Let
$\tau(k)=(i_{k},j,\ell)$, where $j=i_{\mathsf{jump}(k)}$,
$\ell=i_{\mathsf{land}(k)}$, and
$\mathsf{land}(k)=\mathsf{cover}(k,\mathsf{jump}(k))$. We let
$\tilde{\mathcal{I}}(k):=\left\\{i_{k},\ldots,i_{\mathsf{land}(k)-1}\right\\}$
and say that the jumpable tuple $\tau(k)$ is _responsible_ for these levels.
Notice that,

$w_{\tilde{\mathcal{I}}(k)}=\log_{\eta}{\left(\frac{\mu_{i_{k}}}{\mu_{\ell}}\right)}\leq
100\log_{\eta}{\left(\frac{\mu_{i_{k}}}{\mu_{j}}\right)}=100w_{{\mathcal{I}}(\tau)}.$
(4.16)

We let
$\tilde{\mathcal{I}}({\mathcal{J}}):=\bigcup_{\tau\in{\mathcal{J}}}\tilde{\mathcal{I}}(\tau)$
be the set of all levels of ${\mathcal{I}}$ for which the jumpable tuples of
${\mathcal{J}}$ are responsible. Since the jumpable tuples of ${\mathcal{J}}$
are independent, for distinct jumpable tuples
$\tau,\tau^{\prime}\in{\mathcal{J}}$, the levels of
$\tilde{\mathcal{I}}(\tau)$ and $\tilde{\mathcal{I}}(\tau^{\prime})$ are
disjoint. Thus,

$w_{\tilde{\mathcal{I}}({\mathcal{J}})}=\sum_{\tau\in{\mathcal{J}}}w_{\tilde{\mathcal{I}}(\tau)}\leq\sum_{\tau\in{\mathcal{J}}}100w_{{\mathcal{I}}(\tau)}=100w_{{\mathcal{I}}({\mathcal{J}})}.$
(4.17)

Here, the inequality follows from Equation 4.16. We now conclude that
$w_{{\mathcal{I}}({\mathcal{J}})}\geq
w_{\tilde{\mathcal{I}}({\mathcal{J}})}/100$. Thus, to show that the level-
weight $w_{{\mathcal{I}}({\mathcal{J}})}$ of our collection ${\mathcal{J}}$ of
jumpable tuples is large, it suffices to prove that
$w_{\tilde{\mathcal{I}}({\mathcal{J}})}$ is large, which we show next.

######  Claim 4.5.25.

$w_{\tilde{\mathcal{I}}({\mathcal{J}})}\geq\frac{r}{100}$.

###### Proof.

We first claim that
$\tilde{\mathcal{I}}({\mathcal{J}})\subseteq\left\\{0,\ldots,i_{k^{\prime}-1}\right\\}$,
or in other words, each jumpable tuple
$\tau(k)=(i_{k},i_{\mathsf{jump}(k)},i_{\mathsf{land}(k)})\in{\mathcal{J}}$
has $\mathsf{land}(k)\leq k^{\prime}$. Indeed, consider the level
$i_{k^{\prime}}$. If $k^{\prime}=k^{*}$, $\mathsf{land}(k)\leq
k^{*}=k^{\prime}$ by definition and there is nothing to show. Otherwise, if
$i_{k^{\prime}}$ is not a heavyweight level, for each jumpable tuple
$\tau(k)\in{\mathcal{J}}$, we must have $\mathsf{land}(k)<k^{\prime}$ and
there is nothing to show. Thus, assume that $i_{k^{\prime}}$ is a heavyweight
level and let $\mathsf{jump}(k^{\prime})$ be the level as computed by our
algorithm. Since $i_{k^{\prime}}$ is the last level that we processed, we must
have found that $\mathsf{cover}(k^{\prime},\mathsf{jump}(k^{\prime}))=k^{*}$.
But then the jumpable tuple $\tau(k^{\prime})$ is not added to ${\mathcal{J}}$
and as a result, each jumpable tuple $\tau(k)\in{\mathcal{J}}$ has
$\mathsf{land}(k)<k^{\prime}$ as claimed.

We let
${\mathcal{I}}_{\mathsf{rem}}:={\mathcal{I}}^{\prime}\backslash\tilde{\mathcal{I}}({\mathcal{J}})$
be the levels of ${\mathcal{I}}^{\prime}$ for which no jumpable tuple of
${\mathcal{J}}$ is responsible. We claim that no level in
${\mathcal{I}}_{\mathsf{rem}}$ is heavyweight. Indeed, assume for
contradiction that there is a heavyweight level
$i_{k}\in{\mathcal{I}}_{\mathsf{rem}}$. But since $k<k^{\prime}$, level
$i_{k}$ is not the last level that we process. Hence, we must have added a
jumpable tuple $\tau(k)$ to ${\mathcal{J}}$, and we get
$i_{k}\in\tilde{\mathcal{I}}({\mathcal{J}})$, a contradiction. Thus, each
level in ${\mathcal{I}}_{\mathsf{rem}}$ is either a featherweight level or a
savable level. As in Observation 4.5.24, we can now bound the weight of levels
${\mathcal{I}}_{\mathsf{rem}}$ by, $w_{{\mathcal{I}}_{\mathsf{rem}}}\leq
0.9k^{\prime}+\frac{r}{10^{5}}$. We now conclude,

$\displaystyle w_{\tilde{\mathcal{I}}({\mathcal{J}})}$
$\displaystyle=w_{{\mathcal{I}}^{\prime}}-w_{{\mathcal{I}}_{\mathsf{rem}}}$
$\displaystyle>k^{\prime}-\frac{r}{1000}-\left(\frac{9k^{\prime}}{10}+\frac{r}{10^{5}}\right)$
$\displaystyle>\frac{k^{\prime}}{10}-\frac{r}{500}$
$\displaystyle\geq\frac{r}{100}$

Here, the first inequality follows from Claim 4.5.22 and the last inequality
follows from Claim 4.5.21. This completes the proof of Claim 4.5.25.

From LABEL:{clm:_ncm-w-tilde-iset-hat-jset-is-large} and LABEL:{eqn:_ncm-
tilde-iset-jset-to-jset}, we have,
$w_{{\mathcal{I}}({\mathcal{J}})}\geq\frac{1}{100}\cdot
w_{\tilde{\mathcal{I}}({\mathcal{J}})}\geq\frac{r}{10^{4}}$. This completes
the proof of Claim 4.5.23.

This completes the description of the first phase of our process. So far, we
have shown that the level-weight $w_{{\mathcal{I}}({\mathcal{J}})}$ of our
independent collection ${\mathcal{J}}$ of jumpable tuples is large. However,
as we previously noted, some of these jumpable tuples in ${\mathcal{J}}$ may
not be perfect. In our second phase, we will show that level-weight of such
imperfect jumpable tuples present in ${\mathcal{J}}$ is relatively small. We
can thus discard all imperfect jumpable tuples without significantly reducing
the level-weight of the surviving jumpable tuples. We now formalize this
approach.

Consider a jumpable tuple $\tau(k)\in{\mathcal{J}}$ and let
$\tau(k)=(i_{k},j,\ell)$, where $j=i_{\mathsf{jump}}(k)$,
$\ell=i_{\mathsf{land}(k)}$, and
${\mathsf{land}(k)={\mathsf{cover}(k,\mathsf{jump}(k))}}$. First we claim that
$w_{{\mathcal{I}}(\tau(k))}\geq 100$. It is immediate to verify that $i_{k}$
is a heavyweight level and $\mathsf{jump}(k)>k$, implying
$w_{{\mathcal{I}}(\tau(k))}=\log_{\eta}{\left(\frac{\mu_{i_{k}}}{\mu_{j}}\right)}\geq
w_{i_{k}}\geq 100$. We say that $\tau(k)$ is a _bad jumpable tuple_ if
$\frac{Z_{\ell}}{Z_{j}}>{\eta^{-\frac{w_{{\mathcal{I}}(\tau(k))}}{5}}}$, or
equivalently,
${\log_{\eta}{\left(\frac{Z_{j}}{Z_{\ell}}\right)}<\frac{w_{{\mathcal{I}}(\tau(k))}}{5}}$.
We say that it is a _good jumpable tuple_ otherwise. Let
${\mathcal{J}}^{\prime}\subseteq{\mathcal{J}}$ be the set of all bad jumpable
tuples. From the above discussion, the set
${\mathcal{J}}^{*}={\mathcal{J}}\backslash{\mathcal{J}}^{\prime}$ is indeed a
collection of perfect jumpable tuples of level-weight
$w_{{\mathcal{I}}({\mathcal{J}}^{*})}=w_{{\mathcal{I}}({\mathcal{J}})}-w_{{\mathcal{I}}({\mathcal{J}}^{\prime})}$,
and it now suffices to upper bound the level-weight
$w_{{\mathcal{I}}({\mathcal{J}}^{\prime})}$. We prove the following claim
after completing the proof of Lemma 4.5.20 assuming it.

######  Claim 4.5.26.

$w_{{\mathcal{I}}({\mathcal{J}}^{\prime})}\leq 30\epsilon r$.

From Claims 4.5.23 and 4.5.26, we have,

$w_{{\mathcal{I}}({\mathcal{J}}^{*})}=w_{{\mathcal{I}}({\mathcal{J}})}-w_{{\mathcal{I}}({\mathcal{J}}^{\prime})}\geq\frac{r}{10^{4}}-30\epsilon
r\geq\frac{r}{10^{5}},$

for all $\epsilon\leq 10^{-6}$. This completes the proof of Lemma 4.5.20
assuming Claim 4.5.26 that we show next.

Proof of Claim 4.5.26. If ${\mathcal{J}}^{\prime}=\emptyset$, we have
$w_{{\mathcal{I}}({\mathcal{J}}^{\prime})}=0$ and there is nothing to show.
Thus, assume from now on that ${\mathcal{J}}^{\prime}\neq\emptyset$. We will
use the following observation whose proof is deferred to Section C.2.4.3.

######  Observation 4.5.27.

$\log_{\eta}{\left(\frac{Z_{0}}{Z_{i_{k^{*}}}}\right)}<{k^{*}-0.09w_{{\mathcal{I}}({\mathcal{J}}^{\prime})}}$.

From Assumption 4.5.5, $X_{i_{k^{*}}}/Z_{i_{k^{*}}}>N^{1/2-\epsilon}$, and we
obtain,

$\displaystyle\frac{Z_{0}}{Z_{i_{k^{*}}}}>\frac{Z_{0}}{X_{i_{k^{*}}}/N^{1/2-\epsilon}}=\frac{Z_{0}\cdot
N^{1/2-\epsilon}}{X_{i_{k^{*}}}}\geq\frac{N^{1-2\epsilon}}{N/\eta^{i_{k}^{*}}}=\frac{\eta^{i_{k^{*}}}}{N^{2\epsilon}}\geq\frac{\eta^{k^{*}}}{N^{2\epsilon}},$

where the second inequality follows from the facts that $Z_{0}\geq
N^{1/2-\epsilon}$ and $X_{i_{k^{*}}}=\frac{N}{\eta^{i_{k^{*}}}}$. Combined
with Observation 4.5.27 we obtain,
$\frac{\eta^{k^{*}}}{N^{2\epsilon}}<\eta^{k^{*}-0.09w_{{\mathcal{J}}^{\prime}}}$,
or equivalently, $k^{*}-2\epsilon
r<k^{*}-0.09w_{{\mathcal{I}}({\mathcal{J}}^{\prime})}$. We now conclude
$w_{{\mathcal{I}}({\mathcal{J}}^{\prime})}<\frac{2}{0.09}\epsilon r<30\epsilon
r$, completing the proof of Claim 4.5.26. $\Box$

####  4.5.5 Special Case 3: Jumpable Tuples have Large Level-Weight

Recall that we have fixed parameters $N$ and $\eta$, both integral powers of
$2$, such that $\eta$ grows 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$. From Assumptions 4.5.5 and 4.5.9, we know 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 this special case, we are given an independent collection
${\mathcal{J}}^{*}$ of perfect jumpable tuples with level-weight
$w_{{\mathcal{I}}({\mathcal{J}}^{*})}\geq\frac{r}{10^{5}}$. Our goal is to
devise an $N^{o(1)}$-canonical distinguisher algorithm
${\mathsf{AlgCase}}_{\mathsf{3}}$ for the LIS problem with space complexity
$N^{1/2-\epsilon+o(1)}$. 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. For each level
$i\in{\mathcal{I}}^{*}$ we denote the corresponding level-$i$ algorithm by
${\mathsf{Alg}}\mathsf{Jump}{(i)}$. As in Section 4.5.3,
${\mathsf{Alg}}\mathsf{Jump}{(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$. As in Section 4.5.3, we ensure
that ${\mathsf{Alg}}\mathsf{Jump}{(i)}$ is an
$(\alpha_{i},\alpha^{\prime}_{i})$-canonical distinguisher algorithm for
$\alpha_{i}=4$ and $\alpha^{\prime}_{i}=2^{3(r^{*}-i)+2}$. Additionally,
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)}$.

Consider a level $i_{k}\in{\mathcal{I}}^{*}$ for some $0\leq k\leq k^{*}$. For
readability, we denote $i:=i_{k}$. We are now ready to describe our level-$i$
algorithm ${\mathsf{Alg}}\mathsf{Jump}{(i)}$.

######  ${\mathsf{Alg}}\mathsf{Jump}{(i)}$ for the level
$i\in{\mathcal{I}}^{*}$ such that there is no jumpable tuple $\tau=(i,j,\ell)$
in ${\mathcal{J}}^{*}$.

Our algorithm ${\mathsf{Alg}}\mathsf{Jump}{(i)}$ is identical to the algorithm
${\mathsf{Alg}}\mathsf{Level}{(i)}$ of LABEL:{lem:_ncm-simple-lis-main} from
Section 4.5.3, with one exception. Recall that if $k<k^{*}$, the algorithm
${\mathsf{Alg}}\mathsf{Level}{(i)}$ is allowed to use the level-$i_{k+1}$
algorithm ${\mathsf{Alg}}\mathsf{Level}{(i_{k+1})}$ as subroutine. In our new
algorithm ${\mathsf{Alg}}\mathsf{Jump}{(i)}$, we replace each of these calls
by the respective calls to our newly defined algorithm
${\mathsf{Alg}}\mathsf{Jump}{(i_{k+1})}$. 777Note that the algorithm
${\mathsf{Alg}}\mathsf{Jump}{(i_{k^{*}})}$ is identical to the algorithm
${\mathsf{Alg}}\mathsf{Level}{(i_{k^{*}})}$. From LABEL:{lem:_ncm-simple-lis-
main}, we immediately obtain the following observation:

######  Observation 4.5.28.

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{Jump}{(j)}$. Then, there is a level-$i$
$(4,\alpha^{\prime}_{i})$-canonical distinguisher algorithm
${\mathsf{Alg}}\mathsf{Jump}{(i)}$ that achieves the following guarantees:

  * •

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

  * •

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

This completes the description of our algorithm
${\mathsf{Alg}}\mathsf{Jump}{(i)}$ for this case. We now focus on the
remaining case.

######  ${\mathsf{Alg}}\mathsf{Jump}{(i)}$ for the level
$i\in{\mathcal{I}}^{*}$ such that there is a jumpable tuple $\tau=(i,j,\ell)$
in ${\mathcal{J}}^{*}$.

We fix such a jumpable tuple $\tau=\tau(k)=(i_{k},j,\ell)$, with
$j=i_{\mathsf{jump}(k)}$ and $\ell=i_{\mathsf{land}}(k)$. In this case, we
show the following algorithm, whose analysis is deferred to Section 4.5.6.

######  Lemma 4.5.29.

Fix a tuple of levels $i_{0}<i<j<\ell<k^{*}$ of ${\mathcal{I}}^{*}$ such that
$\frac{Z_{j}}{Z_{\ell}}\leq\sqrt{\frac{\mu_{i}}{\mu_{j}}}$. Assume that we are
given a $(4,\alpha^{\prime}_{j})$-canonical distinguisher level-$j$ algorithm
${\mathsf{Alg}}\mathsf{Jump}{(j)}$ and a
$(4,\alpha^{\prime}_{\ell})$-canonical distinguisher level-$\ell$ algorithm
${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$. Then there is a
$(4,\alpha^{\prime}_{i})$-canonical distinguisher level-$i$ algorithm
${\mathsf{Alg}}\mathsf{Jump}{(i)}$ that achieves the following guarantees:

  * •

Calls to ${\mathsf{Alg}}\mathsf{Jump}{(j)}$: it performs at most
$O\left(\zeta(i,\ell)\cdot\frac{Z_{i}}{Z_{j}}\cdot\eta^{\ell-j}\right)$
concurrent calls to ${\mathsf{Alg}}\mathsf{Jump}{(j)}$;

  * •

Calls to ${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$: it performs at most
$O\left(\zeta^{2}(i,\ell)\cdot\frac{Z_{i}\cdot
Z_{\ell}^{2}}{Z_{j}^{3}}\cdot\frac{\mu_{i}}{\mu_{\ell}}\right)$ concurrent
calls to ${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$; and

  * •

Space complexity: its space complexity, excluding the space required by the
calls to ${\mathsf{Alg}}\mathsf{Jump}{(j)}$ and
${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$, is at most
$O\left(\zeta^{3}(i,\ell)\cdot\eta^{\ell-j}\cdot\frac{Z_{i}\cdot
Z_{\ell}^{2}}{Z_{j}^{3}}\cdot\frac{\mu_{i}}{\mu_{\ell}}\right)$.

We are now ready to describe our algorithm ${\mathsf{AlgCase}}_{\mathsf{3}}$
for this special case.

##### The algorithm ${\mathsf{AlgCase}}_{\mathsf{3}}$.

Applying Observation 4.5.28 and Lemma 4.5.29 recursively for the levels of
${\mathcal{I}}^{*}$ in their decreasing order, we obtain a
$(4,\alpha^{\prime}_{0})$-canonical distinguisher level-$i_{0}$ algorithm
${\mathsf{Alg}}\mathsf{Jump}{(i_{0})}$. From LABEL:{obs:_ncm-
alglevel-0-suffices}, there is a $\alpha^{\prime}_{0}=N^{o(1)}$-canonical
distinguisher algorithm ${\mathsf{AlgCase}}_{\mathsf{3}}$ that performs at
most $N^{o(1)}$ concurrent calls to ${\mathsf{Alg}}\mathsf{Jump}{(i_{0})}$ and
whose space complexity, excluding the space required by the calls to
${\mathsf{Alg}}\mathsf{Jump}{(i_{0})}$, is at most $N^{o(1)}$. We prove the
following claim after describing the algorithm of this subsection assuming it.

######  Claim 4.5.30.

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

We immediately obtain the following corollary that is the main result of this
subsection.

######  Corollary 4.5.31.

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$
and an independent collection ${\mathcal{J}}^{*}$ of perfect jumpable tuples
with level-weight $w_{{\mathcal{I}}({\mathcal{J}}^{*})}\geq\frac{r}{10^{5}}$.
Then there is a $N^{o(1)}$-canonical distinguisher algorithm
${\mathsf{AlgCase}}_{\mathsf{3}}$ with space complexity
$N^{1/2-\epsilon+o(1)}$.

Before proving Claim 4.5.30, we need the following simple fact whose proof is
deferred to Section C.2.5.1.

######  Claim 4.5.32.

For each pair $0\leq k_{1}<k_{2}\leq k^{*}$,
$\zeta(i_{k_{1}},i_{k_{2}})\leq\prod_{k_{1}\leq
k^{\prime}<k_{2}}\zeta(i_{k^{\prime}},i_{k^{\prime}+1})$.

Proof of Claim 4.5.30. Consider a level $i\in{\mathcal{I}}^{*}$ and a
level-$i$ stream-block $B\in{\mathcal{B}}_{\Psi}^{i}$. While executing
${\mathsf{Alg}}\mathsf{Jump}{(i_{0})}$, we also execute a number of calls to
the level-$i$ algorithm ${\mathsf{Alg}}\mathsf{Jump}{(i)}$ in which $B$
participates. We denote by $\mathsf{load}(B)$ the maximum number of such
concurrent calls to ${\mathsf{Alg}}\mathsf{Jump}{(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. We need the following
additional parameters.

For each pair $0\leq i^{\prime}<i^{\prime\prime}\leq r$ of levels, we define
$\mathsf{eq}(i^{\prime},i^{\prime\prime}):=\left|\left\\{i^{\prime},\ldots,i^{\prime\prime}\right\\}\backslash{\mathcal{I}}^{*}\right|$.
For each level $i_{k}\in{\mathcal{I}}^{*}$, we have three parameters
$q_{1}(i_{k})$, $q_{2}(i_{k})$, and $q_{3}(i_{k})$ whose values are defined
recursively as follows. We let $q_{1}(i_{0})=q_{2}(i_{0})=q_{3}(i_{0})=1$.
Consider now a level $i_{k}\in{\mathcal{I}}^{*}$ with $0<k\leq k^{*}$. First
consider the case where there is a jumpable tuple
$\tau=(i,j,\ell)\in{\mathcal{J}}^{*}$ with $j=i_{k}$. In this case, we let,
$q_{1}(i_{k})=q_{1}(i)\cdot\eta^{\mathsf{eq}(i,\ell)}$,
$q_{2}(i_{k})=q_{2}(i)\cdot\eta^{0.39w_{{\mathcal{I}}(\tau)}}$, and
$q_{3}(i_{k})=q_{3}(i)\cdot\zeta^{4}(i,\ell)$. Otherwise, if there is no such
jumpable tuple, we let $q_{1}(i_{k})=q_{1}(i_{k-1})$,
$q_{2}(i_{k})=q_{2}(i_{k-1})$, and
$q_{3}(i_{k})=q_{3}(i_{k-1})\cdot\zeta^{4}(i_{k-1},i_{k})$. For each level
$i\in{\mathcal{I}}^{*}$, we also define $L^{*}(i)=\frac{q_{1}(i)\cdot
q_{3}(i)}{q_{2}(i)}\cdot\frac{\mu_{i_{0}}}{\mu_{i}}$. In LABEL:{prf-clm:_ncm-
jump-load-induction} and LABEL:{prf-clm:_ncm-load-i-small}, we prove the
following two claims.

######  Claim 4.5.33.

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

######  Claim 4.5.34.

For each level $i_{k}\in{\mathcal{I}}^{*}$,
$L^{*}(i_{k})\leq{N^{\frac{1}{2}+6\epsilon}}/{\eta^{0.39w_{{\mathcal{J}}^{*}}}}\leq
N^{\frac{1}{2}-\frac{2}{10^{6}}}$.

We are now ready to analyze the space complexity of
${\mathsf{Alg}}\mathsf{Jump}{(i_{0})}$. We consider its state when processing
some element $a_{t}\in S$. Consider a level $i\in{\mathcal{I}}^{*}$ and let
$B_{i}\in{\mathcal{B}}^{i}_{\Psi}$ be the unique level-$i$ stream-block
containing $a_{t}$. We will show that the contribution to the space complexity
of ${\mathsf{Alg}}\mathsf{Jump}{(0)}$ due to level-$i$ is at most
$N^{1/2-2\epsilon}$. We analyze this contribution differently, depending on
whether there is a jumpable tuple $\tau=(i,j,\ell)\in{\mathcal{J}}^{*}$ for
some levels $\ell>j>i$.

We first consider the case where there is no jumpable tuple
$\tau=(i,j,\ell)\in{\mathcal{J}}^{*}$. From the guarantee of Observation
4.5.28, the space complexity used by such an execution of
${\mathsf{Alg}}\mathsf{Jump}{(i)}$, excluding the space required by the calls
to lower level algorithms, is at most $N^{6\epsilon}$. Observe that $B_{i}$
participates in all the active calls to the level-$i$ algorithm
${\mathsf{Alg}}\mathsf{Jump}{(i)}$. Hence, there are at most
$\mathsf{load}(i)$ active calls to ${\mathsf{Alg}}\mathsf{Jump}{(i)}$. From
LABEL:{clm:_ncm-jump-load-induction} and LABEL:{clm:_ncm-load-i-small}, the
contribution to the space complexity of ${\mathsf{Alg}}\mathsf{Jump}{(0)}$ due
to the level $i$ is,

$\begin{split}\mathsf{load}(i)\cdot O(N^{6\epsilon})&\leq L^{*}(i)\cdot
O\left(N^{6\epsilon}\right)\\\ &\leq
O\left(N^{\frac{1}{2}-\frac{2}{10^{6}}}\cdot
N^{6\epsilon}\right)=O\left(N^{\frac{1}{2}-\frac{2}{10^{6}}+6\epsilon}\right)\\\
&\leq N^{1/2-2\epsilon},\end{split}$ (4.18)

for all $\epsilon\leq 10^{-7}$.

We now consider the remaining case and fix the jumpable tuple
$\tau=(i,j,\ell)\in{\mathcal{J}}^{*}$. Observe that $B_{i}$ participates in
all the active calls to the level-$i$ algorithm
${\mathsf{Alg}}\mathsf{Jump}{(i)}$. Hence, there are at most
$\mathsf{load}(i)$ active calls to ${\mathsf{Alg}}\mathsf{Jump}{(i)}$. From
the guarantee of Lemma 4.5.29, the space complexity used by such an execution
of ${\mathsf{Alg}}\mathsf{Jump}{(i)}$, excluding the space required by the
calls to lower level algorithms, is at most,

$O\left(\zeta^{3}(i,\ell)\cdot\eta^{\ell-j}\cdot\frac{Z_{i}\cdot
Z_{\ell}^{2}}{Z_{j}^{3}}\cdot\frac{\mu_{i}}{\mu_{\ell}}\right)\leq\frac{q_{3}(j)}{q_{3}(i)}\cdot\eta^{\ell-j}\cdot\frac{Z_{i}\cdot
Z_{\ell}^{2}}{Z_{j}^{3}}\cdot\frac{\mu_{i}}{\mu_{\ell}}.$

Since $\tau$ is a perfect jumpable tuple, we have $\ell-j=\left\lfloor
0.3w_{{\mathcal{I}}(\tau)}\right\rfloor+\mathsf{eq}(j,\ell)$,
$\frac{Z_{i}}{Z_{j}}\leq\eta^{0.01w_{{\mathcal{I}}(\tau)}}$, and $Z_{j}\geq
Z_{\ell}\cdot\eta^{0.2w_{{\mathcal{I}}(\tau)}}$. Using these relations, we can
further bound the space used by,

$\displaystyle\frac{q_{3}(j)}{q_{3}(i)}\cdot\eta^{\ell-j}\cdot\frac{Z_{i}\cdot
Z_{\ell}^{2}}{Z_{j}^{3}}\cdot\frac{\mu_{i}}{\mu_{\ell}}$
$\displaystyle\leq\frac{q_{3}(j)}{q_{3}(i)}\cdot\eta^{0.3w_{{\mathcal{I}}(\tau)}+\mathsf{eq}(j,\ell)}\cdot\frac{Z_{i}}{Z_{j}}\cdot\frac{Z_{\ell}^{2}}{Z_{j}^{2}}\cdot\frac{\mu_{i}}{\mu_{\ell}}$
$\displaystyle\leq\frac{q_{1}(j)q_{3}(j)}{q_{1}(i)q_{3}(i)}\cdot\eta^{0.3w_{{\mathcal{I}}(\tau)}+0.01w_{{\mathcal{I}}(\tau)}-0.4w_{{\mathcal{I}}(\tau)}}\cdot\frac{\mu_{i}}{\mu_{\ell}}$
$\displaystyle=\frac{q_{1}(j)q_{3}(j)}{q_{1}(i)q_{3}(i)}\cdot\eta^{-0.09w_{{\mathcal{I}}(\tau)}}\cdot\frac{\mu_{i}}{\mu_{\ell}}.$

Using the above bound along with LABEL:{clm:_ncm-jump-load-induction}, we can
bound the contribution to the space complexity of
${\mathsf{Alg}}\mathsf{Jump}{(0)}$ due to level $i$ by,

$\displaystyle\mathsf{load}(i)\cdot\frac{q_{1}(j)q_{3}(j)}{q_{1}(i)q_{3}(i)}\cdot\eta^{-0.09w_{{\mathcal{I}}(\tau)}}\cdot\frac{\mu_{i}}{\mu_{\ell}}$
$\displaystyle\leq
L^{*}(i)\cdot\frac{q_{1}(j)q_{3}(j)}{q_{1}(i)q_{3}(i)}\cdot\eta^{-0.09w_{{\mathcal{I}}(\tau)}}\cdot\frac{\mu_{i}}{\mu_{\ell}}$
$\displaystyle=\frac{q_{1}(j)\cdot
q_{3}(j)}{q_{2}(i)}\cdot\eta^{-0.09w_{{\mathcal{I}}(\tau)}}\cdot\frac{\mu_{i_{0}}}{\mu_{\ell}}$
$\displaystyle=\frac{q_{1}(j)\cdot
q_{3}(j)}{q_{2}(j)}\cdot\eta^{0.3w_{{\mathcal{I}}(\tau)}}\cdot\frac{\mu_{i_{0}}}{\mu_{\ell}}$
$\displaystyle\leq\frac{q_{1}(\ell)\cdot
q_{3}(\ell)}{q_{2}(\ell)}\cdot\eta^{0.3w_{{\mathcal{I}}(\tau)}}\cdot\frac{\mu_{i_{0}}}{\mu_{\ell}}$
$\displaystyle=L^{*}(\ell)\cdot\eta^{0.3w_{{\mathcal{I}}(\tau)}}$
$\displaystyle\leq
L^{*}(\ell)\cdot\eta^{0.3w_{{\mathcal{I}}({\mathcal{J}}^{*})}}.$

From LABEL:{clm:_ncm-load-i-small} we can further bound this contribution by,

$\begin{split}L^{*}(\ell)\cdot\eta^{0.3w_{{\mathcal{I}}({\mathcal{J}}^{*})}}&\leq\frac{N^{\frac{1}{2}+6\epsilon}}{\eta^{0.39w_{{\mathcal{I}}({\mathcal{J}}^{*})}}}\cdot\eta^{0.3w_{{\mathcal{I}}({\mathcal{J}}^{*})}}=\frac{N^{\frac{1}{2}+6\epsilon}}{\eta^{0.09w_{{\mathcal{I}}({\mathcal{J}}^{*})}}}\\\
&\leq\frac{N^{\frac{1}{2}+6\epsilon}}{\eta^{\frac{0.09r}{10^{6}}}}\leq
N^{\frac{1}{2}+6\epsilon-0.09\frac{1}{10^{6}}}\leq
N^{\frac{1}{2}-2\epsilon}.\end{split}$ (4.19)

The second-last inequality follows from the fact that
$w_{{\mathcal{I}}({\mathcal{J}}^{*})}\geq r/10^{6}$ and the last inequality
holds for all $\epsilon\leq\frac{1}{10^{8}}$.

From LABEL:{eqn:_ncm-jumpable-bound-one} and LABEL:{eqn:_ncm-jumpable-bound-
two}, for each level $i\in{\mathcal{I}}^{*}$, the contribution of
${\mathsf{Alg}}\mathsf{Jump}{(i)}$ in the space complexity of
${\mathsf{Alg}}\mathsf{Jump}{(i_{0})}$ is at most $N^{1/2-2\epsilon}$. We now
conclude that the space complexity of ${\mathsf{Alg}}\mathsf{Jump}{(i_{0})}$
is indeed bounded by,

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

This completes the analysis of the space complexity of
${\mathsf{Alg}}\mathsf{Jump}{(i_{0})}$ and Claim 4.5.30 now follows. $\Box$

####  4.5.6 ${\mathsf{Alg}}\mathsf{Jump}{(i)}$ and its Properties — Proof of
Lemma 4.5.29

The goal of this subsection is to prove Lemma 4.5.29. We are given a tuple
$(i,j,\ell)$ of levels of ${\mathcal{I}}^{*}$ with $i_{0}<i<j<\ell<i_{k}^{*}$.
We are also given an $(\alpha_{j},\alpha^{\prime}_{j})$-canonical
distinguisher level-$j$ algorithm ${\mathsf{Alg}}\mathsf{Jump}{(j)}$ and an
$(\alpha_{\ell},\alpha^{\prime}_{\ell})$-canonical distinguisher level-$\ell$
algorithm ${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$. Our goal is to devise an
$(\alpha_{i},\alpha^{\prime}_{i})$-canonical distinguisher level-$i$ algorithm
${\mathsf{Alg}}\mathsf{Jump}{(i)}$ with low space complexity that performs a
small number of calls to ${\mathsf{Alg}}\mathsf{Jump}{(j)}$ and
${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$. Recall that the input to
${\mathsf{Alg}}\mathsf{Jump}{(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^{**}$.

Observe that if $|{\mathcal{B}}|\leq 100$, we can immediately report no and
there is nothing to show. Indeed, if that is the case, $B^{**}$ may contain at
most $(2+|{\mathcal{B}}|)Z_{j}\leq 102Z_{j}<Z_{i}/\alpha_{i}$ elements of an
$\Upsilon$-canonical subsequence. Here, the last inequality follows from the
fact that $\alpha_{i}=4$ and Property P4 of $\Upsilon$-canonical subsequences.
We assume from now on that $|{\mathcal{B}}|>100$. Consider the collection
${\mathcal{B}}^{\prime}$ of level-$j$ descendant range-blocks of
$B^{*^{\prime}}$. We denote
$\tilde{\mathcal{B}}_{j}:={\mathcal{B}}^{j}_{\Psi^{\prime}}(H^{*})$ the
partition of the range $H^{*}$ into level-$j$ range-blocks. Before describing
our algorithm ${\mathsf{Alg}}\mathsf{Jump}{(i)}$, we need a notion of
_generalized subblock processing algorithm_ , that is analogous to the block
processing algorithm of Section 4.5.1. We will later show using the standard
dynamic-programming approach that it suffices to show an ‘efficient’
generalized subblock processing algorithm.

###### Region of range-blocks.

Note that the collection ${\mathcal{B}}^{\prime}$ of level-$j$ descendant-
blocks of $B^{*^{\prime}}$ is a partition of $B^{*^{\prime}}$. We view this
collection ${\mathcal{B}}^{\prime}$, ordered in the natural increasing order
of the range-block indices, as a sequence with values in the range
$\tilde{\mathcal{B}}_{j}$: the set of all level-$j$ range-blocks. We refer to
a block ${\mathcal{R}}$ of this sequence ${\mathcal{B}}$ as a _region_. It is
worth noting that a region ${\mathcal{R}}$ consists of $|{\mathcal{R}}|$
contiguous range-blocks, and it can be uniquely identified by the indices of
its first and last blocks of $\tilde{\mathcal{B}}_{j}$; and as a consequence,
stored in $O(1)$ units of space. Consider a collection $\tilde{\mathcal{R}}$
of such regions. If $\tilde{\mathcal{R}}$ constitute a partition of the
sequence ${\mathcal{B}}^{\prime}$, we refer to it as _partition of
${\mathcal{B}}^{\prime}$ into regions_.

###### Generalized Sunblock Processing Algorithm

The generalized subblock processing algorithm, that we refer to as
$\mathsf{Alg}{\mathsf{Gen}}$, is a streaming algorithm. It is initialized with
a region ${\mathcal{R}}\subseteq{\mathcal{B}}^{\prime}$ of level-$j$ range-
blocks determined by the indices of its first and last range-blocks in
$\tilde{\mathcal{B}}_{j}$. It is then provided access to the elements of $B$
as they arrive as a part of the stream $B^{**}$ of the original input stream
$S$. At the end of the stream-block $B$, $\mathsf{Alg}{\mathsf{Gen}}$ reports
a (possibly empty) region ${\mathcal{R}}^{\prime}$ of range-blocks of
${\mathcal{R}}$ by outputting the interval of their respective indices in
${\mathcal{B}}^{\prime}_{j}$. We allow $\mathsf{Alg}{\mathsf{Gen}}$ to use a
number of calls to the level-$j$ algorithm ${\mathsf{Alg}}\mathsf{Jump}{(j)}$
and the level-$\ell$ algorithm ${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$ as
subroutine.

Recall that in Section 4.5.3, we have defined, for each pair
$i_{k}<i_{k^{\prime}}$ of levels of ${\mathcal{I}}^{*}$ a parameter
$\zeta(i_{k},i_{k^{\prime}})=\ln{\left(\eta^{2(i_{k^{\prime}}-i_{k})}\cdot\psi_{i_{k+1}}\cdot\ldots\cdot\psi_{i_{k^{\prime}}}\right)}$.
We use the following lemma:

######  Lemma 4.5.35.

Consider the collections ${\mathcal{B}}$ and ${\mathcal{B}}^{\prime}$ of
level-$j$ stream-blocks and level-$j$ range-blocks respectively as mentioned
earlier. Assume that we are given an
$(\alpha_{j},\alpha^{\prime}_{j})$-canonical distinguisher level-$j$ algorithm
${\mathsf{Alg}}\mathsf{Jump}{(j)}$ and an
$(\alpha_{\ell},\alpha^{\prime}_{\ell})$-canonical distinguisher level-$\ell$
algorithm ${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$. Then there is a generalized
subblock processing algorithm $\mathsf{Alg}{\mathsf{Gen}}$ that, on input
$B\in{\mathcal{B}}$, a region ${\mathcal{R}}$ of ${\mathcal{B}}^{\prime}$, and
the set $\hat{\mathcal{B}}$ of level-$\ell$ descendants of $B$, achieves the
following guarantees:

  * •

Completeness guarantee: if there is a range-block $B^{\prime}\in{\mathcal{R}}$
such that $(B,B^{\prime})$ is a yes-pair and $|B\cap B^{*^{\prime}}|\leq
8Z_{j}\mu_{i}$, then with probability at least $1-e^{-\zeta(i,\ell)}$ over the
randomness used by $\mathsf{Alg}{\mathsf{Gen}}$, the reported region
${\mathcal{R}}^{\prime}$ is non-empty and it does not contain any range-blocks
of ${\mathcal{B}}^{\prime}$ appearing after $B^{\prime}$;

  * •

Soundness guarantee: the probability, over the randomness used by
$\mathsf{Alg}{\mathsf{Gen}}$, that it reports a non-empty region
${\mathcal{R}}^{\prime}$ such that the longest increasing subsequence of $B$
using values collectively from the range-blocks of ${\mathcal{R}}^{\prime}$
has length less than $\frac{Z_{j}}{\alpha^{\prime}_{j}}$, is at most
$e^{-\zeta(i,\ell)}$;

  * •

Calls to ${\mathsf{Alg}}\mathsf{Jump}{(j)}$: it performs at most
$O\left(\zeta(i,\ell)\cdot\eta^{\ell-j}\right)$ concurrent calls to
${\mathsf{Alg}}\mathsf{Jump}{(j)}$;

  * •

Calls to ${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$: it marks each level-$\ell$
stream-block $\hat{B}\in\hat{\mathcal{B}}$ independently randomly with
probability $O\left(\zeta(i,\ell)\cdot\frac{Z_{\ell}}{Z_{j}}\right)$ each, and
for each marked block $\hat{B}$ it performs at most
$O\left(\zeta(i,\ell)\cdot\frac{Z_{\ell}\mu_{i}}{Z_{j}\mu_{\ell}}\right)$
calls to the level-$\ell$ algorithm ${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$ in
which $\hat{B}$ participates; and

  * •

Space complexity: its space complexity, excluding the space required by the
calls to ${\mathsf{Alg}}\mathsf{Jump}{(j)}$ and
${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$ is at most
$O\left(\zeta^{3}(i,\ell)\cdot\eta^{\ell-j}\cdot\frac{Z_{\ell}^{2}}{Z_{j}^{2}}\cdot\frac{\mu_{i}}{\mu_{\ell}}\right)$.

We complete the proof of Lemma 4.5.35 in Section 4.5.7 after we prove Lemma
4.5.29 assuming it. We are now ready to describe our level-$i$ algorithm
${\mathsf{Alg}}\mathsf{Jump}{(i)}$. It is an adaptation of the algorithm
$\mathsf{Alg}_{1}$ of Lemma 4.2.1.

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

Recall that the input to the level-$i$ algorithm
${\mathsf{Alg}}\mathsf{Jump}{(i)}$ is a level-$i$ pair
$(B^{*},B^{*^{\prime}})$ and a subblock $B^{**}$ of $B^{*}$. We have also
fixed the sets ${\mathcal{B}}$ and ${\mathcal{B}}^{\prime}$ of level-$j$
descendants of $B^{*}$ and $B^{*^{\prime}}$ respectively. We fix the parameter
$\beta:=\frac{Z_{i}}{8Z_{j}}$. We will process level-$j$ stream-blocks of
${\mathcal{B}}$ as they arrive as a part of the subsequence $B^{**}$ of the
original input sequence $S$. While processing these elements, we will maintain
an ordered collection $\tilde{\mathcal{R}}$ of at most $\beta$ disjoint non-
empty regions of $B^{*^{\prime}}$. Let
$\mathsf{leftover}(\tilde{\mathcal{R}}):={\mathcal{B}}^{\prime}\backslash\bigcup_{{\mathcal{R}}\in\tilde{\mathcal{R}}}{\mathcal{R}}$
be the set of range-blocks not appearing in the regions of
$\tilde{\mathcal{R}}$. We will ensure that
$\mathsf{leftover}(\tilde{\mathcal{R}})$ is a (possibly empty) region and the
non-empty regions of
$\tilde{\mathcal{R}}\cup\left\\{\mathsf{leftover}(\tilde{\mathcal{R}})\right\\}$
constitute a partition of ${\mathcal{B}}^{\prime}$. We initialize this
collection by $\tilde{\mathcal{R}}\leftarrow\emptyset$.

Consider a level-$j$ stream-block $B\in{\mathcal{B}}$ and let
$\tilde{\mathcal{R}}$ be our collection of the regions of $B^{*^{\prime}}$
just before processing the first element of $B$. We fix the special region
$\mathsf{leftover}(\tilde{\mathcal{R}})={\mathcal{B}}^{\prime}\backslash\bigcup_{{\mathcal{R}}\in\tilde{\mathcal{R}}}{\mathcal{R}}$.
For each region
${\mathcal{R}}\in\tilde{\mathcal{R}}\cup\left\\{\mathsf{leftover}(\tilde{\mathcal{R}})\right\\}$,
we run in parallel the generalized subblock processing algorithm
$\mathsf{Alg}{\mathsf{Gen}}$ of Lemma 4.5.35 with input level-$j$ stream-block
$B$ and the region ${\mathcal{R}}$ of level-$j$ blocks of
${\mathcal{B}}^{\prime}$. At the end of stream-block $B$, all the calls to the
generalized subblock processing algorithm $\mathsf{Alg}{\mathsf{Gen}}$
terminate and we are ready to update our collection $\tilde{\mathcal{R}}$. Let
${\mathcal{R}}^{\prime}$ be the region reported by the call to
$\mathsf{Alg}{\mathsf{Gen}}$ with input $B$ and the special region
$\mathsf{leftover}(\tilde{\mathcal{R}})$. If $\tilde{\mathcal{R}}=\emptyset$
and ${\mathcal{R}}^{\prime}=\emptyset$, we do not update the regions and let
$\tilde{\mathcal{R}}=\emptyset$. Thus, assume from now on that either
${\mathcal{R}}^{\prime}\neq\emptyset$ or $\tilde{\mathcal{R}}\neq\emptyset$
(or both).

###### Case $1$: ${\mathcal{R}}^{\prime}=\emptyset$ and
$\tilde{\mathcal{R}}\neq\emptyset$.

In this case, the regions in $\tilde{\mathcal{R}}$ constitute a partition of
${\mathcal{B}}^{\prime}$. We let
$\tilde{\mathcal{R}}=({\mathcal{R}}_{1},\ldots,{\mathcal{R}}_{k})$ be these
regions in their natural order, where $k=|\tilde{\mathcal{R}}|\leq\beta$. In
this case, we will ensure that after the update, the resulting collection
$\tilde{\mathcal{B}}$ contains exactly $k$ regions. For each $1\leq
k^{\prime}\leq k$, let
${\mathcal{R}}^{\prime}_{k^{\prime}}\subseteq{\mathcal{R}}_{k^{\prime}}$ be
the region reported by the respective call to $\mathsf{Alg}{\mathsf{Gen}}$
with input stream-block $B$ and region ${\mathcal{R}}_{k^{\prime}}$. If
${\mathcal{R}}^{\prime}_{1}=\emptyset$, we do not update the first region:
${\mathcal{R}}^{(\mathsf{new})}_{1}\leftarrow{\mathcal{R}}_{1}$. Otherwise, we
set ${\mathcal{R}}^{(\mathsf{new})}_{1}\leftarrow{\mathcal{R}}^{\prime}_{1}$.
For each successive $2\leq k^{\prime}\leq k$, we obtain the new region
${\mathcal{R}}^{(\mathsf{new})}_{k^{\prime}}$ as follows. If
${\mathcal{R}}^{\prime}_{k^{\prime}}\neq\emptyset$, we let the new region
${\mathcal{R}}^{(\mathsf{new})}_{k^{\prime}}$ contain all the range-blocks
that appear after the region ${\mathcal{R}}^{(\mathsf{new})}_{k^{\prime}-1}$
until the last range-block of ${\mathcal{R}}^{\prime}_{k^{\prime}}$.
Otherwise, if ${\mathcal{R}}^{\prime}_{k^{\prime}}=\emptyset$, we let the new
region ${\mathcal{R}}^{(\mathsf{new})}_{k^{\prime}}$ contain all the range-
blocks that appear after the region
${\mathcal{R}}^{(\mathsf{new})}_{k^{\prime}-1}$ until the last range-block of
${\mathcal{R}}_{k^{\prime}}$. Finally, we update
$\tilde{\mathcal{R}}\leftarrow({\mathcal{R}}^{(\mathsf{new})}_{1},\ldots,{\mathcal{R}}^{(\mathsf{new})}_{k})$.
Let
$\mathsf{leftover}(\tilde{\mathcal{R}})\leftarrow{\mathcal{B}}^{\prime}\backslash\bigcup_{{\mathcal{R}}\in\tilde{\mathcal{R}}}{\mathcal{R}}$
be the special set of range-blocks not present in the regions of
$\tilde{\mathcal{R}}$. From our construction, it is immediate to verify that
$\mathsf{leftover}(\tilde{\mathcal{R}})$ is a region and the non-empty regions
of
$\tilde{\mathcal{R}}\cup\left\\{\mathsf{leftover}(\tilde{\mathcal{R}})\right\\}$
indeed constitute a partition of ${\mathcal{B}}^{\prime}$.

###### Case $2$: ${\mathcal{R}}^{\prime}\neq\emptyset$.

Note that in this case, we must have
$\mathsf{leftover}(\tilde{\mathcal{R}})\neq\emptyset$. Since all the regions
of
$\tilde{\mathcal{R}}\cup\left\\{\mathsf{leftover}(\tilde{\mathcal{R}})\right\\}$
are non-empty, they constitute a partition of ${\mathcal{B}}^{\prime}$. We
append
$\tilde{\mathcal{R}}\leftarrow\tilde{\mathcal{R}}\cup\left\\{\mathsf{leftover}(\tilde{\mathcal{R}})\right\\}$
and let $\tilde{\mathcal{R}}=({\mathcal{R}}_{1},\ldots,{\mathcal{R}}_{k})$ be
these regions in their natural order, for $k=|\tilde{\mathcal{R}}|$. Notice
that $1\leq k\leq\beta+1$. In this case, we will ensure that after the update,
$\tilde{\mathcal{B}}$ contains exactly $k^{*}:=\min{(k,\beta)}$ regions. We
proceed as in case $1$. For each $1\leq k^{\prime}\leq k$, let
${\mathcal{R}}^{\prime}_{k^{\prime}}\subseteq{\mathcal{R}}_{k^{\prime}}$ be
the region reported by the respective call to $\mathsf{Alg}{\mathsf{Gen}}$
with input stream-block $B$ and region ${\mathcal{R}}_{k^{\prime}}$. If
${\mathcal{R}}^{\prime}_{1}=\emptyset$, we do not update the first region:
${\mathcal{R}}^{(\mathsf{new})}_{1}\leftarrow{\mathcal{R}}_{1}$. Otherwise, we
set ${\mathcal{R}}^{(\mathsf{new})}_{1}\leftarrow{\mathcal{R}}^{\prime}_{1}$.
For each successive $2\leq k^{\prime}\leq k$, we obtain the new region
${\mathcal{R}}^{(\mathsf{new})}_{k^{\prime}}$ as follows. If
${\mathcal{R}}^{\prime}_{k^{\prime}}\neq\emptyset$, we let the new region
${\mathcal{R}}^{(\mathsf{new})}_{k^{\prime}}$ contain all the range-blocks
that appear after the region ${\mathcal{R}}^{(\mathsf{new})}_{k^{\prime}-1}$
until the last range-block of ${\mathcal{R}}^{\prime}_{k^{\prime}}$.
Otherwise, if ${\mathcal{R}}^{\prime}_{k^{\prime}}=\emptyset$, we let the new
region ${\mathcal{R}}^{(\mathsf{new})}_{k^{\prime}}$ contain all the range-
blocks that appear after the region
${\mathcal{R}}^{(\mathsf{new})}_{k^{\prime}-1}$ until the last range-block of
${\mathcal{R}}_{k^{\prime}}$. Finally, we update
$\tilde{\mathcal{R}}\leftarrow({\mathcal{R}}^{(\mathsf{new})}_{1},\ldots,{\mathcal{R}}^{(\mathsf{new})}_{k^{*}})$.
Let
$\mathsf{leftover}(\tilde{\mathcal{R}})\leftarrow{\mathcal{B}}^{\prime}\backslash\bigcup_{{\mathcal{R}}\in\tilde{\mathcal{R}}}{\mathcal{R}}$
be the set of range-blocks not present in the regions of
$\tilde{\mathcal{R}}$. From our construction, it is immediate to verify that
$\mathsf{leftover}(\tilde{\mathcal{R}})$ is a region and the non-empty regions
of
$\tilde{\mathcal{R}}\cup\left\\{\mathsf{leftover}(\tilde{\mathcal{R}})\right\\}$
indeed constitute a partition of ${\mathcal{B}}^{\prime}$. This completes the
description of case $2$, and as a result, the description of our algorithm for
processing the level-$j$ stream-block $B$.

We now proceed to process the subsequent level-$j$ stream-blocks of
${\mathcal{B}}$. Recall that $\mathsf{Alg}{\mathsf{Gen}}$ performs a number of
calls to the level-$j$ and level-$\ell$ algorithms
${\mathsf{Alg}}\mathsf{Jump}{(j)}$ and ${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$
respectively. We define $L^{*}:=c\zeta^{2}(i,\ell)\cdot\frac{Z_{i}\cdot
Z_{\ell}^{2}}{Z_{j}^{3}}\cdot\frac{\mu_{i}}{\mu_{\ell}}$, for some constant
$c$ to be fixed later. Consider a level-$\ell$ descendant stream-block
$\hat{B}$ of $B^{*}$. We denote by ${\mathcal{E}}^{*}_{\mathsf{bad}}(\hat{B})$
the event that $\mathsf{Alg}{\mathsf{Gen}}$ performs at least $L^{*}$ calls to
${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$ (excluding the calls performed while
executing level-$j$ algorithm ${\mathsf{Alg}}\mathsf{Jump}{(j)}$) in which
$\hat{B}$ participates. We let ${\mathcal{E}}^{*}_{\mathsf{bad}}$ be the event
that there is a some level-$\ell$ descendant stream-block $\hat{B}$ of $B^{*}$
for which the event ${\mathcal{E}}^{*}_{\mathsf{bad}}(\hat{B})$ occurs.
Throughout our algorithm ${\mathsf{Alg}}\mathsf{Jump}{(i)}$, if at any point
the event ${\mathcal{E}}^{*}_{\mathsf{bad}}$ occurs, we immediately stop and
report no. Once we process the last stream-block of ${\mathcal{B}}$, we are
ready to report our answer. Let $\tilde{\mathcal{R}}$ be our collection of
regions of $B^{*^{\prime}}$, just after processing the last element of the
last stream-block of ${\mathcal{B}}$. If $\tilde{\mathcal{R}}$ contains
exactly $\beta$ regions, we report yes; otherwise, we report no. This
completes the description of our level-$i$ algorithm
${\mathsf{Alg}}\mathsf{Jump}{(i)}$. We now turn to analyze its properties,
starting with an upper bound on the number of concurrent calls to
$\mathsf{Alg}{\mathsf{Gen}}$.

###### Calls to $\mathsf{Alg}{\mathsf{Gen}}$.

Recall that we process the level-$j$ stream-blocks of ${\mathcal{B}}$ in their
natural sequential order. Consider some block $B\in{\mathcal{B}}$ and let
$\tilde{\mathcal{R}}$ be our collection of regions just before processing $B$.
We also fix the special region
$\mathsf{leftover}(\tilde{\mathcal{R}})={\mathcal{B}}^{\prime}\backslash\bigcup_{{\mathcal{R}}\in\tilde{\mathcal{R}}}{\mathcal{R}}$
just before processing $B$. Since we execute the generalized subblock
processing algorithm $\mathsf{Alg}{\mathsf{Gen}}$ with input $B$ and
${\mathcal{R}}$, for each non-empty region
${\mathcal{R}}\in\tilde{\mathcal{R}}\cup\left\\{\mathsf{leftover}(\tilde{\mathcal{R}})\right\\}$,
we perform at most $1+|\tilde{\mathcal{R}}|\leq 1+\beta\leq
O\left(\frac{Z_{i}}{Z_{j}}\right)$ concurrent calls to
$\mathsf{Alg}{\mathsf{Gen}}$. In Section C.2.5.4, we prove the following
claim.

######  Claim 4.5.36.

$\text{\bf Pr}\left[{\mathcal{E}}^{*}_{\mathsf{bad}}\right]\leq
e^{-2\zeta(i,\ell)}$.

We assume from now on that the event ${\mathcal{E}}^{*}_{\mathsf{bad}}$ does
not occur. We are now ready to show the correctness guarantees of our
algorithm ${\mathsf{Alg}}\mathsf{Jump}{(i)}$.

###### Completeness.

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^{**}$ contains at least
$Z_{i}/\alpha_{i}=Z_{i}/4$ elements of $S^{*}$. Our goal is to show that we
report yes with probability at least $3/4$. As mentioned earlier, we assume
that the event ${\mathcal{E}}^{*}_{\mathsf{bad}}$ does not occur.

We let ${\mathcal{B}}_{\mathsf{yes}}$ be the set of yes-blocks of
${\mathcal{B}}$ for $S^{*}$. Since $B^{**}$ contains at least
$\frac{Z_{i}}{4}$ elements of $S^{*}$ and $S^{*}$ is an $\Upsilon$-canonical
increase subsequence, we must have
$|{\mathcal{B}}_{\mathsf{yes}}|\geq\frac{Z_{i}}{4Z_{j}}-2\geq\beta$. Here, the
last inequality follows since $i<j$ and $i,j\in{\mathcal{I}}^{*}$ implying
that $Z_{i}/Z_{j}>$ from Property P4 of the $\Upsilon$-canonical subsequence.
We arbitrarily discard additional blocks ${\mathcal{B}}_{\mathsf{yes}}$ to
ensure that $|{\mathcal{B}}_{\mathsf{yes}}|=\beta$ and let
${\mathcal{B}}_{\mathsf{yes}}=\left\\{B(1),\ldots,B(\beta)\right\\}$ in their
natural order. We also let
${\mathcal{B}}^{\prime}_{\mathsf{yes}}=\left\\{B^{\prime}(1),\ldots,B^{\prime}(\beta)\right\\}$
be the corresponding range-blocks of ${\mathcal{B}}^{\prime}$ such that
$(B(1),B^{\prime}(1)),\ldots,(B(\beta),B^{\prime}(\beta))$ are level-$j$ yes-
pairs. For each $1\leq s\leq\beta$, we let $\tilde{\mathcal{R}}^{(s)}$ be the
collection of regions of ${\mathcal{B}}^{\prime}$ just after processing the
stream-block $B(s)$. The following claim, whose proof is deferred to Section
C.2.5.5, now shows the completeness of ${\mathsf{Alg}}\mathsf{Jump}{(i)}$.

######  Claim 4.5.37.

With probability at least $9/10$, for each $1\leq s\leq\beta$, the following
holds: (i) $|\tilde{\mathcal{R}}^{(s)}|\geq s$; and (ii) the $s^{th}$ region
in $\tilde{\mathcal{R}}^{(s)}$ does not contain any range-block appearing
after $B^{\prime}(s)$.

Recall that we report yes if we have exactly $\beta$ regions in our collection
after processing the last stream-block of ${\mathcal{B}}$. From Claims 4.5.36
and 4.5.37, with probability at least $0.9-e^{-\zeta(i,\ell)}\geq 3/4$, the
collection $\tilde{\mathcal{R}}^{(\beta)}$ has $\beta$ regions, showing the
completeness guarantee of ${\mathsf{Alg}}\mathsf{Jump}{(i)}$.

###### Soundness.

Assume that $\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(B^{**}\cap
B^{*^{\prime}})<\frac{Z_{i}}{\alpha^{\prime}_{i}}$. Our goal is to show that
we report no with probability at least $3/4$. As mentioned earlier, assume
that the event ${\mathcal{E}}^{*}_{\mathsf{bad}}$ does not occur.

Consider a level-$j$ stream-block $B\in{\mathcal{B}}$ and let
$\tilde{\mathcal{R}}$ be our collection of the regions of $B^{*^{\prime}}$
just before processing the first element of $B$. We also fix the special
region
$\mathsf{leftover}(\tilde{\mathcal{R}})={\mathcal{B}}^{\prime}\backslash\bigcup_{{\mathcal{R}}\in\tilde{\mathcal{R}}}{\mathcal{R}}$.
Consider some non-empty region
${\mathcal{R}}\in\tilde{\mathcal{R}}\cup\left\\{\mathsf{leftover}(\tilde{\mathcal{R}})\right\\}$
and the execution of $\mathsf{Alg}{\mathsf{Gen}}$ with input stream-block $B$
and region ${\mathcal{R}}$. Let ${\mathcal{R}}^{\prime}$ be the region that it
reports. We let ${\mathcal{E}}_{\mathsf{bad}}(B,{\mathcal{R}})$ be the event
that ${\mathcal{R}}^{\prime}\neq\emptyset$ and there is no increasing
subsequence of $B$ of length $\frac{Z_{j}}{\alpha^{\prime}_{j}}$ using
elements with values in the range-blocks of ${\mathcal{R}}^{\prime}$. From the
correctness guarantee of $\mathsf{Alg}{\mathsf{Gen}}$ and 4.5.11, the
probability that ${\mathcal{E}}_{\mathsf{bad}}(B,{\mathcal{R}})$ occurs is at
most
$e^{-\zeta(i,\ell)}\leq\frac{1}{10|{\mathcal{B}}||{\mathcal{B}}^{\prime}|}$.
We let ${\mathcal{E}}_{\mathsf{bad}}(B)$ be the event
${\mathcal{E}}_{\mathsf{bad}}(B,{\mathcal{R}})$ occurs for some non-empty
region
${\mathcal{R}}\in\tilde{\mathcal{R}}\cup\left\\{\mathsf{leftover}(\tilde{\mathcal{R}})\right\\}$.
From union bound over at most $|{\mathcal{B}}^{\prime}|$ such non-empty
regions, the probability that ${\mathcal{E}}_{\mathsf{bad}}(B)$ occurs is at
most $\frac{1}{10|{\mathcal{B}}|}$. We let ${\mathcal{E}}_{\mathsf{bad}}$ be
the bad event ${\mathcal{E}}_{\mathsf{bad}}(B)$ occurs for some level-$j$
block $B\in{\mathcal{B}}$. From union bound over $|{\mathcal{B}}|$ such
stream-blocks, the probability that ${\mathcal{E}}_{\mathsf{bad}}$ occurs is
at most $\frac{1}{10}$. We assume from now on that the event
${\mathcal{E}}_{\mathsf{bad}}$ does not occur.

We let ${\mathcal{B}}=\left\\{B(1),\ldots,B(|{\mathcal{B}}|)\right\\}$ in
their natural order. For each $1\leq s\leq|{\mathcal{B}}|$, we let
$\tilde{\mathcal{R}}^{(s)}$ be the collection of regions of
${\mathcal{B}}^{\prime}$ just after processing the stream-block $B^{(s)}$. In
Section C.2.5.6 we prove the following claim using techniques similar those
used in proving Claim 4.5.37.

######  Claim 4.5.38.

For each $1\leq s\leq|{\mathcal{B}}|$ and $1\leq
s^{\prime}\leq|\tilde{\mathcal{R}}^{(s)}|$, there is an increasing subsequence
of length at least $\frac{s^{\prime}Z_{j}}{\alpha^{\prime}_{j}}$ using
elements in $B(1)\cup\ldots\cup B(s)$ with values in the range-blocks of the
first $s^{\prime}$ regions of $\tilde{\mathcal{R}}^{(s)}$.

Recall that ${\mathsf{Alg}}\mathsf{Jump}{(i)}$ reports yes only if there are
exactly $\beta$ regions in our collection at the end of $B^{**}$, or in other
words, $|\tilde{\mathcal{R}}^{|{\mathcal{B}}|}|=\beta$. But then from the
above claim, there must be an increasing subsequence of $B^{**}$ of length at
least $\frac{\beta
Z_{j}}{\alpha^{\prime}_{j}}=\frac{Z_{i}}{8Z_{j}}\cdot\frac{Z_{j}}{\alpha^{\prime}_{j}}\geq\frac{Z_{i}}{\alpha^{\prime}_{i}}$
with values in $B^{*^{\prime}}$. This is in contradiction with our assumption
that $\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(B^{**}\cap
B^{*^{\prime}})<\frac{Z_{i}}{\alpha^{\prime}_{i}}$, completing the proof of
soundness.

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

Consider some some level-$j$ stream-block $B\in{\mathcal{B}}$. Notice that all
the calls to the level-$j$ algorithm ${\mathsf{Alg}}\mathsf{Jump}{(j)}$ are
performed through the respective calls to $\mathsf{Alg}{\mathsf{Gen}}$ in
which $B$ participates. Consider one such call to $\mathsf{Alg}{\mathsf{Gen}}$
in which $B$ participates. From Lemma 4.5.35, each such execution of
$\mathsf{Alg}{\mathsf{Gen}}$ performs at most
$O\left(\zeta(i,\ell)\cdot\eta^{\ell-j}\right)$ calls to
${\mathsf{Alg}}\mathsf{Jump}{(j)}$. Since there are at most $O(Z_{i}/Z_{j})$
concurrent calls to $\mathsf{Alg}{\mathsf{Gen}}$, the number of concurrent
calls to ${\mathsf{Alg}}\mathsf{Jump}{(j)}$ in which $B$ participates is
bounded by,

$\displaystyle O\left(\frac{Z_{i}}{Z_{j}}\right)\cdot
O\left(\zeta(i,\ell)\cdot\eta^{\ell-j}\right)$
$\displaystyle=O\left(\zeta(i,\ell)\cdot\frac{Z_{i}}{Z_{j}}\cdot\eta^{\ell-j}\right)$

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

Recall that we immediately terminate our algorithm if the event
${\mathcal{E}}^{*}_{\mathsf{bad}}$ occurs. Thus, for each level-$\ell$
descendant-block $\hat{B}$ of $B^{*}$, the number of concurrent calls to the
level-$\ell$ algorithm ${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$ in which
$\hat{B}$ participates is at most
$L^{*}=O\left(\zeta^{2}(i,\ell)\cdot\frac{Z_{i}\cdot
Z_{\ell}^{2}}{Z_{j}^{3}}\cdot\frac{\mu_{i}}{\mu_{\ell}}\right)$.

###### Space complexity.

We first analyze the space complexity of ${\mathsf{Alg}}\mathsf{Jump}{(i)}$,
excluding the space used by the calls to $\mathsf{Alg}{\mathsf{Gen}}$.
Consider some level-$j$ stream-block $B\in{\mathcal{B}}$ and let
$\tilde{\mathcal{R}}$ be our collection of regions just before processing $B$.
The space used by ${\mathsf{Alg}}\mathsf{Jump}{(i)}$ can be divided into two
parts: (i) the space required to store these regions; and (ii) the space
required to update these regions. Recall that we can store a region
${\mathcal{R}}\in\tilde{\mathcal{R}}$ by storing the indices of its first and
last blocks in the level-$j$ partition $\tilde{\mathcal{B}}_{j}$ of range
$H^{*}$. Since there are at most $\beta$ regions in $\tilde{\mathcal{R}}$, the
space used to store them is at most $O(\beta)$. Similarly, we can store the
special region
$\mathsf{leftover}(\tilde{\mathcal{R}})={\mathcal{B}}^{\prime}\backslash\bigcup_{{\mathcal{R}}\in\tilde{\mathcal{R}}}{\mathcal{R}}$
in $O(1)$ units of space. For each region
${\mathcal{R}}\in\tilde{\mathcal{R}}\cup\left\\{\mathsf{leftover}(\tilde{\mathcal{R}})\right\\}$,
we execute $\mathsf{Alg}{\mathsf{Gen}}$ with input $B$ and ${\mathcal{R}}$.
Let ${\mathcal{R}}^{\prime}$ be the reported region, which we can store in
$O(1)$ units of space. It is immediate to verify that we can update our
collection $\tilde{\mathcal{R}}$ using $O(\beta)$ additional space. We are now
ready to analyze the space complexity of ${\mathsf{Alg}}\mathsf{Jump}{(i)}$,
excluding the space used by the calls to ${\mathsf{Alg}}\mathsf{Jump}{(j)}$
and ${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$. Recall that we perform at most
$O(Z_{i}/Z_{j})$ concurrent calls to $\mathsf{Alg}{\mathsf{Gen}}$. From Lemma
4.5.35, the space complexity of each such call, excluding the space required
by the calls to ${\mathsf{Alg}}\mathsf{Jump}{(j)}$ and
${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$ is
$O\left(\zeta^{3}(i,\ell)\cdot\eta^{\ell-j}\cdot\frac{Z_{\ell}^{2}}{Z_{j}^{2}}\cdot\frac{\mu_{i}}{\mu_{\ell}}\right)$.
Hence, the overall space complexity of ${\mathsf{Alg}}\mathsf{Jump}{(i)}$,
excluding the space required by the calls to
${\mathsf{Alg}}\mathsf{Jump}{(j)}$ and ${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$,
is

$\displaystyle O\left(\beta\right)+O\left(\frac{Z_{i}}{Z_{j}}\right)\cdot
O\left(\zeta^{3}(i,\ell)\cdot\eta^{\ell-j}\cdot\frac{Z_{\ell}^{2}}{Z_{j}^{2}}\cdot\frac{\mu_{i}}{\mu_{\ell}}\right)$
$\displaystyle=O\left(\zeta^{3}(i,\ell)\cdot\eta^{\ell-j}\cdot\frac{Z_{i}\cdot
Z_{\ell}^{2}}{Z_{j}^{3}}\cdot\frac{\mu_{i}}{\mu_{\ell}}\right).$

This completes the analysis of the properties of
${\mathsf{Alg}}\mathsf{Jump}{(i)}$ and LABEL:{lem:_ncm-jump-jump} now follows.
It now remains to prove Lemma 4.5.35, that we show next.

####  4.5.7 $\mathsf{Alg}{\mathsf{Gen}}$ and its Properties — Proof of Lemma
4.5.35

We now focus on describing our generalized subblock processing algorithm
$\mathsf{Alg}{\mathsf{Gen}}$ and completing the proof of Lemma 4.5.35. We are
given a tuple $(i,j,\ell)$ of levels of ${\mathcal{I}}^{*}$ with
${i_{0}<i<j<\ell<i_{k}^{*}}$ with
$\left(\frac{Z_{j}}{Z_{\ell}}\right)^{2}\leq\frac{\mu_{i}}{\mu_{j}}$. We are
also given an $(\alpha_{j},\alpha^{\prime}_{j})$-canonical distinguisher
level-$j$ algorithm ${\mathsf{Alg}}\mathsf{Jump}{(j)}$ and an
$(\alpha_{\ell},\alpha^{\prime}_{\ell})$-canonical distinguisher level-$\ell$
algorithm ${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$. 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 denote
$\tilde{\mathcal{B}}_{j}:={\mathcal{B}}^{j}_{\Psi^{\prime}}(H^{*})$ the
partition of the range $H^{*}$ into level-$j$ range-blocks. 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}$. If ${\mathcal{R}}=\emptyset$,
we report ${\mathcal{R}}^{\prime}=\emptyset$ and there is nothing to show.
Thus, we assume from now on that $|{\mathcal{R}}|\geq 1$. Recall that we are
given a parameter $\zeta(i,\ell)$, that we denote by $\zeta$ for readability.
Let $\hat{\mathcal{B}}$ be the set of all level-$\ell$ descendant-blocks of
$B$. Similarly, let $\hat{\mathcal{B}}^{\prime}$ be the set of all
level-$\ell$ descendant-blocks of range-blocks in ${\mathcal{R}}$. We will
need the following definition.

###### Promising pairs and suspicious blocks.

We say that a level-$\ell$ pair
$(\hat{B},\hat{B}^{\prime})\in\hat{\mathcal{B}}\times\hat{\mathcal{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}}$.
In this case, we also say that $\hat{B}$ participates in a promising pair with
$\hat{B}^{\prime}$. We say that a level-$j$ range-block
$B^{\prime}\in{\mathcal{B}}^{\prime}$ is a _suspicious block for
$\hat{\mathcal{B}}$_ iff there are at least $\frac{Z_{j}}{Z_{\ell}}$ stream-
blocks in $\hat{\mathcal{B}}$ that participate in promising pairs with
level-$\ell$ descendant range-blocks of $B^{\prime}$.

Consider a level-$j$ yes-pair $(B,B^{\prime})$ with
$B^{\prime}\in{\mathcal{R}}$. We claim that $B^{\prime}$ is a suspicious block
for $\hat{\mathcal{B}}$. Indeed, if $(B,B^{\prime})$ is a yes-pair, there are
$\frac{Z_{j}}{Z_{\ell}}$ descendant level-$\ell$ yes-pairs of
$(B,B^{\prime})$. Thus, each of the $\frac{Z_{j}}{Z_{\ell}}$ yes-blocks of
$\hat{\mathcal{B}}$ participate in a promising pair with some level-$\ell$
descendant range-block of $B^{\prime}$. For the reverse direction, we claim
that if there are sufficiently many suspicious blocks, they together
contribute to a large increasing subsequence in $B^{**}$. We summarize it in
the following observation, that follows by ‘random shift’ argument.

######  Observation 4.5.39.

Suppose there is a collection
${\mathcal{B}}^{\prime\prime}\subseteq{\mathcal{B}}^{\prime}$ of at least
$3|\hat{\mathcal{B}}|$ level-$j$ range-blocks that are suspicious for
$\hat{\mathcal{B}}$. Then there is an increasing subsequence of $B$ of length
more than $\frac{Z_{j}}{\alpha^{\prime}_{j}}$ with values in the range-blocks
of ${\mathcal{B}}^{\prime\prime}$.

###### Proof.

We denote $m=|\hat{\mathcal{B}}|$. We let
$\hat{\mathcal{B}}=\left\\{\hat{B}_{1},\ldots,\hat{B}_{m}\right\\}$ be the
stream-blocks in their natural order. We discard additional range-blocks of
${\mathcal{B}}^{\prime\prime}$ and let
${\mathcal{B}}^{\prime\prime}=\left\\{B^{\prime}_{1},\ldots,B^{\prime}_{3m}\right\\}$
in their natural order. We consider a bipartite graph ${\mathcal{H}}$ with
vertices $V(\hat{\mathcal{B}})$ on one side and
$V({\mathcal{B}}^{\prime\prime})$ on the other side. For each stream-block
$\hat{B}_{k^{\prime}}\in\hat{\mathcal{B}}$, there is a unique vertex
$u({k^{\prime}})\in V(\hat{\mathcal{B}})$. Similarly, for each range-block
$B^{\prime}_{k^{\prime\prime}}\in{\mathcal{B}}_{\mathsf{good}}$, there is a
unique vertex $v({k^{\prime\prime}})\in V({\mathcal{B}}^{\prime\prime})$.
Consider a pair $(\hat{B}_{k^{\prime}},B^{\prime}_{k^{\prime\prime}})$ of
blocks with $\hat{B}_{k^{\prime}}\in\hat{\mathcal{B}}$ and
$B^{\prime}_{k^{\prime\prime}}\in{\mathcal{B}}^{\prime\prime}$. If there is a
level-$\ell$ descendant range-block $\hat{B}^{\prime}_{k^{\prime\prime}}$ of
$B^{\prime}_{k^{\prime}}$ such that
$(\hat{B}_{k^{\prime}},\hat{B}_{k^{\prime\prime}})$ is a promising pair, we
add an edge $(u(k^{\prime}),v(k^{\prime\prime}))$ in the graph
${\mathcal{H}}$. Let ${\mathcal{F}}\subseteq V(\hat{\mathcal{B}})\times
V({\mathcal{B}}^{\prime\prime})$ be the resulting set of edges. Notice that
since each range-block
$B^{\prime}_{k^{\prime\prime}}\in{\mathcal{B}}^{\prime\prime}$ is a suspicious
block for $\hat{\mathcal{B}}$, each vertex $v(k^{\prime\prime})\in
V({\mathcal{B}}^{\prime\prime})$ has at least $\frac{Z_{j}}{Z_{\ell}}$ edges
incident on it. We now conclude that the number of edges in ${\mathcal{H}}$ is

$|{\mathcal{F}}|\geq|{\mathcal{B}}^{\prime\prime}|\cdot\frac{Z_{j}}{Z_{\ell}}=3m\frac{Z_{j}}{Z_{\ell}}.$

We divide this set of edges ${\mathcal{F}}$ into $2m+1$ equivalence classes,
where for each $-m\leq k\leq m$, the class ${\mathcal{F}}_{k}$ consists of all
the edges $(u(k^{\prime}),v({k^{\prime\prime}}))$ of ${\mathcal{F}}$ with
$k^{\prime}-k^{\prime\prime}=k$. It is immediate to verify that for each such
class ${\mathcal{F}}_{k}$, there is an increasing subsequence of $B$ with
values in the range-blocks of ${\mathcal{R}}$ of length at least
$|{\mathcal{F}}_{k}|\cdot\frac{Z_{\ell}}{\alpha^{\prime}_{\ell}}$. It now
remains to show that there is an equivalence class containing a large number
of edges. Indeed, from the pigeonhole principle, there is some class
${\mathcal{F}}_{k^{*}}$ that contains at least
$\frac{|{\mathcal{F}}|}{2m+1}>\frac{|{\mathcal{F}}|}{3m}\geq\frac{Z_{j}}{Z_{\ell}}$
edges. Thus, we obtain an increasing subsequence of size at least,

$|{\mathcal{F}}_{k^{*}}|\cdot\frac{Z_{\ell}}{\alpha^{\prime}_{\ell}}>\frac{Z_{j}}{Z_{\ell}}\cdot\frac{Z_{\ell}}{\alpha^{\prime}_{\ell}}=\frac{Z_{j}}{\alpha^{\prime}_{\ell}}\geq\frac{Z_{j}}{\alpha^{\prime}_{j}}$

with values in range-blocks of ${\mathcal{B}}^{\prime\prime}$. This completes
the proof of Observation 4.5.39.

In our generalized subblock processing algorithm $\mathsf{Alg}{\mathsf{Gen}}$,
we will use the level-$j$ algorithm ${\mathsf{Alg}}\mathsf{Jump}{(j)}$ as
subroutine a number of times. The input to each such call of
${\mathsf{Alg}}\mathsf{Jump}{(j)}$ will be some appropriately chosen level-$j$
pair $(B,B^{\prime})$ along with a subblock $\tilde{B}$ of $B$, where
$B^{\prime}\in{\mathcal{R}}$ is a level-$j$ range-block. Before describing our
algorithm, we explore the usefulness of this notion of suspicious blocks with
the help of a thought experiment.

######  $\mathsf{Alg}{\mathsf{Gen}}$ – A wishful thinking.

For simplicity, we assume that each call to ${\mathsf{Alg}}\mathsf{Jump}{(j)}$
reports correct answer with probability $1$. In other words, consider some
level-$j$ pair $(B,B^{\prime})$ along with a subblock $\tilde{B}$ of $B$. If
$(B,B^{\prime})$ is a yes-pair and $\tilde{B}$ contains at least $Z_{j}/2$
elements of $S^{*}$, we assume that ${\mathsf{Alg}}\mathsf{Jump}{(j)}$ must
answer this query in affirmative. On the other hand, if this query is indeed
answered in affirmative, $\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(\hat{B}\cap
B^{\prime})>Z_{j}/\alpha^{\prime}_{j}$ must hold. Ideally,
$\mathsf{Alg}{\mathsf{Gen}}$ should work as follows.

Assume that we have processed elements $\left\\{,\ldots,a_{t}\right\\}$ of $B$
and somehow came up with a collection
${\mathcal{B}}^{\prime\prime}\subseteq{\mathcal{R}}$ of suspicious blocks. We
discard all but lowest
$\min{(|{\mathcal{B}}^{\prime\prime}|,3|\hat{\mathcal{B}}|)}$ range-blocks
from ${\mathcal{B}}^{\prime\prime}$ and denote by
${\mathcal{B}}^{\prime\prime\prime}$ the subset of surviving suspicious
blocks. For each surviving suspicious range-block
$B^{\prime\prime}\in{\mathcal{B}}^{\prime\prime}$, we perform an independent
call to the level-$j$ algorithm ${\mathsf{Alg}}\mathsf{Jump}{(j)}$ with input
pair $(B,B^{\prime\prime})$ and the subblock $B_{>t}$888Recall that $B_{>t}$
is the subblock of $B$ containing all elements appearing after $a_{t}$ in it.
of $B$. First consider the case where at least one of these calls is answered
in affirmative. Let $B^{\prime}_{\min}\in{\mathcal{B}}^{\prime\prime\prime}$
be the lowest range-block such that the corresponding call to
${\mathsf{Alg}}\mathsf{Jump}{(j)}$ reports yes. In this case, we report the
region ${\mathcal{R}}^{\prime}=\left\\{B^{\prime}_{\min{{}}}\right\\}$
containing that single range-block. Now consider the case where
$|{\mathcal{B}}^{\prime\prime\prime}|=3|\hat{\mathcal{B}}|$ and none of the
calls to ${\mathsf{Alg}}\mathsf{Jump}{(j)}$ returned in affirmative. We then
report the smallest region ${\mathcal{R}}^{\prime}\subseteq{\mathcal{R}}$ that
encompasses all the range-blocks of ${\mathcal{B}}^{\prime\prime\prime}$.
Finally, if $|{\mathcal{B}}^{\prime\prime\prime}|<3|\hat{\mathcal{B}}|$ and
none of the calls to ${\mathsf{Alg}}\mathsf{Jump}{(j)}$ returned in
affirmative, we report the empty region ${\mathcal{R}}^{\prime}=\emptyset$.

We claim that if we report a non-empty region ${\mathcal{R}}^{\prime}$, there
must be a large enough increasing subsequence of $B$ taking values from the
range-blocks of ${\mathcal{R}}^{\prime}$. Indeed, if there is a range-block
$B^{\prime\prime}\in{\mathcal{B}}^{\prime\prime\prime}$ such that the
corresponding call to ${\mathsf{Alg}}\mathsf{Jump}{(j)}$ returned yes, then
from our correctness assumption,
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(B\cap
B^{\prime\prime})\geq\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(B_{>t}\cap
B^{\prime})>\frac{Z_{j}}{\alpha^{\prime}_{j}}$ must hold. On the other hand,
if $|{\mathcal{B}}^{\prime\prime\prime}|=3|\hat{\mathcal{B}}|$, then from
Observation 4.5.39 there is an increasing subsequence of $B$ of length more
than $\frac{Z_{j}}{\alpha^{\prime}_{j}}$ taking values from the range-blocks
of ${\mathcal{B}}^{\prime\prime\prime}$, which are in turn contained in
${\mathcal{R}}^{\prime}$.

We now examine the behavior of our fictional algorithm in the case where
$(B,B^{\prime})$ is a yes-pair with $B^{\prime}\in{\mathcal{R}}$. In this
case, we would like to ensure that with high probability,
${\mathcal{R}}^{\prime}$ is non-empty and does not contain any range-block
appearing after $B^{\prime}$. Suppose, we are guaranteed that if such
$B^{\prime}\in{\mathcal{B}}^{\prime}$ exists, then
$B^{\prime}\in{\mathcal{B}}^{\prime\prime}$ and the (yet-unseen) elements
$B_{>t}$ contain at least $\frac{Z_{j}}{2}$ elements of $S^{*}$. Under this
assumption we claim that $\mathsf{Alg}{\mathsf{Gen}}$ reports the desired
region ${\mathcal{R}}^{\prime}\subseteq{\mathcal{B}}^{\prime}$. Indeed, if
$B^{\prime}\in{\mathcal{B}}^{\prime\prime\prime}$, the level-$j$ algorithm
${\mathsf{Alg}}\mathsf{Jump}{(j)}$ with input pair $(B,B^{\prime})$ and the
subblock $B_{>t}$ of $B$ will return yes. In this case, we indeed report a
region consisting of a single range-block that is either $B^{\prime}$ or some
other one appearing before $B^{\prime}$ in ${\mathcal{R}}$. Otherwise, if
$B^{\prime}\in{\mathcal{B}}^{\prime\prime}$ is not chosen to be in
${\mathcal{B}}^{\prime\prime\prime}$, we must have had
$|{\mathcal{B}}^{\prime\prime}|>3|\hat{\mathcal{B}}|$ and $B^{\prime}$ appears
after all $|\hat{\mathcal{B}}|$ range-blocks of
${\mathcal{B}}^{\prime\prime\prime}$. In this case, we report the non-empty
region ${\mathcal{R}}^{\prime}$ encompassing
${\mathcal{B}}^{\prime\prime\prime}$, which in turn does not contain
$B^{\prime}$ and any other range-block of ${\mathcal{B}}^{\prime}$ appearing
after $B^{\prime}$.

From the above discussion, it suffices to show an algorithm that correctly
identifies the set of such suspicious blocks ${\mathcal{B}}^{\prime\prime}$
without processing too many elements of $B\cap S^{*}$. Recall that
$\mathsf{Alg}{\mathsf{Gen}}$ is allowed to use lower level algorithms
${\mathsf{Alg}}\mathsf{Jump}{(j)}$ and ${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$
as subroutines. We will then also need to ensure that we do not call such
algorithms too often, as these ‘trickle-down’ calls contribute to space
complexity of our algorithm. Unfortunately, we cannot naively find such
suspicious blocks and will have to make certain accommodations that we
describe next.

##### Description of $\mathsf{Alg}{\mathsf{Gen}}$ – Pseudo-suspicious Blocks
and How to Find Them?

We are now ready to describe the main result of this subsection: a generalized
subblock processing algorithm $\mathsf{Alg}{\mathsf{Gen}}$ for processing a
level-$j$ stream-block $B\in{\mathcal{B}}$ and a region
${\mathcal{R}}\subseteq{\mathcal{B}}^{\prime}$ of contiguous level-$j$ range-
blocks. As mentioned earlier, we cannot naively find the suspicious blocks
with desired guarantee. To get around this hurdle, we will define ‘pseudo-
suspicious’ blocks that will serve as a proxy for suspicious blocks.
Informally, our algorithm works as follows. We process elements of $B$ as they
arrive as a part of the original input stream $S$. As we process these
elements, we mark certain level-$\ell$ descendant-pairs of
$\left\\{(B,B^{\prime})\>|\>B^{\prime}\in{\mathcal{R}}\right\\}$ as pseudo-
promising. Once we determine that a level-$j$ range-block
$B^{\prime}\in{\mathcal{R}}$ has large number of level-$\ell$ descendant
pseudo-promising pairs that ‘span across a large number of level-$\ell$
stream-blocks’, we mark it as pseudo-suspicious block. When a range-block
$B^{\prime}$ is marked pseudo-suspicious, we run in parallel a level-$j$
algorithm ${\mathsf{Alg}}\mathsf{Jump}{(j)}$ with input level-$j$ pair
$(B,B^{\prime})$ and the subblock $\tilde{B}$, where $\tilde{B}$ is the yet-
unseen subblock of $B$. We might also decide to discard a pseudo-suspicious
range-block $B^{\prime}$, in which case, we also discard all the computations
of ${\mathsf{Alg}}\mathsf{Jump}{(j)}$ in which $B^{\prime}$ participates. We
now describe our algorithm in detail.

Before starting to process 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. We sample each level-$\ell$ subblock of $B$
independently with probability
$p:=\min{\left(2^{7}\zeta\cdot\frac{Z_{\ell}}{Z_{j}},1\right)}$ when it
arrives as a part of $B$; or discard it otherwise. If at any point we sample
more than $12\zeta p|\hat{\mathcal{B}}|$ stream-blocks of $\hat{\mathcal{B}}$,
we immediately terminate $\mathsf{Alg}{\mathsf{Gen}}$ and report the empty
region ${\mathcal{R}}^{\prime}=\emptyset$ as our output. Consider a sampled
level-$\ell$ subblock $\hat{B}$ of $B$. We run the following algorithm while
we process its elements arriving as a part of $B$.

We sample elements of $\hat{B}$ with values in the range-blocks of
${\mathcal{R}}$ independently with probability
$p^{\prime}=\min{\left({\frac{2^{16}\zeta}{Z_{j}\mu_{\ell}}},1\right)}$ each.
Consider an element $a_{t}\in\hat{B}$ that is sampled and let
$\hat{B}^{\prime}$ be the unique level-$\ell$ range-block containing its
value. If no element of $\hat{B}\cap\hat{B}^{\prime}$ was previously sampled,
we run in parallel the level-$\ell$ algorithm
${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$ with input level-$\ell$ pair
$(\hat{B},\hat{B}^{\prime})$ along with the subblock $\hat{B}_{>t}$ of
$\hat{B}$. If at any point, we sample more than
$E^{*}_{\ell}:=2^{6}p^{\prime}Z_{\ell}\mu_{i}$ elements of $\hat{B}$, we
discard the computation due to $\hat{B}$ and proceed to process the subsequent
level-$\ell$ stream-block of $\hat{\mathcal{B}}$. We now examine the state of
our algorithm at the end of the stream-block $\hat{B}$. At this point, all the
calls to level-$\ell$ algorithms in which $\hat{B}$ participates terminate. We
consider the subset ${\mathcal{R}}_{\mathsf{yes}}\subseteq{\mathcal{R}}$ of
level-$\ell$ range-blocks for which the corresponding run of
${\mathsf{Alg}}\mathsf{Jump}{(\ell)}$ returned yes. Let
${\mathcal{R}}^{(j)}_{\mathsf{yes}}$ be the set of level-$j$ ancestor-blocks
of these range-blocks in ${\mathcal{R}}_{\mathsf{yes}}$. Note that
${\mathcal{R}}^{(j)}_{\mathsf{yes}}$ is a set and each level-$j$ range-block
appears at most once in it. We mark these level-$j$ ancestors as _pseudo-
promising_ by appending them to the multiset
${\mathcal{B}}_{\mathsf{prom}}\leftarrow{\mathcal{B}}_{\mathsf{prom}}\cup{\mathcal{R}}^{(j)}_{\mathsf{yes}}$.
Note that ${\mathcal{B}}_{\mathsf{prom}}$ is a multiset and a level-$j$ range-
block may appear multiple times in it. If some range-block appears at least
$2^{5}\zeta$ times in ${\mathcal{B}}_{\mathsf{prom}}$, we mark it as _pseudo-
suspicious_ by moving it to ${\mathcal{B}}_{\mathsf{susp}}$. Consider the time
when some level-$j$ range-block $B^{\prime}\in{\mathcal{R}}$ is marked pseudo-
suspicious, say, after processing the element $a_{t^{\prime}}$ of the stream-
block $B$. We then run in parallel $\left\lfloor 2^{6}\zeta\right\rfloor$
independent instances of the level-$j$ subblock processing algorithm
${\mathsf{Alg}}\mathsf{Jump}{(j)}$ with input level-$j$ pair $(B,B^{\prime})$
and the subblock $B_{>t^{\prime}}$ of $B$. If at any point there are more than
$|\hat{\mathcal{B}}|$ pseudo-suspicious blocks, we discard the ones with the
highest indices and their respective computations by
${\mathsf{Alg}}\mathsf{Jump}{(j)}$. We refer to surviving pseudo-suspicious
blocks as _active_ pseudo-suspicious blocks.

Finally, at the end of the stream-block $B$, we are ready to compute our
output region ${\mathcal{R}}^{\prime}\subseteq{\mathcal{R}}$. At this point,
all our calls to the level-$j$ algorithm ${\mathsf{Alg}}\mathsf{Jump}{(j)}$
terminate. If there is an active pseudo-suspicious range-block for which at
least $2^{5}\zeta$ of the corresponding runs of
${\mathsf{Alg}}\mathsf{Jump}{(j)}$ returned in affirmative, let
$B^{\prime}_{\min{}}$ be such a range-block with the lowest index. We then
report the region
${\mathcal{R}}^{\prime}=\left\\{B^{\prime}_{\min{}}\right\\}$ consisting of
this single range-block. If there is no such range-block and there are exactly
$|\hat{\mathcal{B}}|$ active pseudo-suspicious blocks, we report the smallest
region ${\mathcal{R}}^{\prime}$ that encompasses all of these active pseudo-
suspicious range-blocks. Otherwise, we report the empty region
${\mathcal{R}}^{\prime}=\emptyset$. This completes the description of our
generalized subblock processing algorithm $\mathsf{Alg}{\mathsf{Gen}}$. We now
turn to analyze its properties, starting with completeness.

###### Completeness.

Assume that there is a range-block $B^{\prime}\in{\mathcal{R}}$ such that
$(B,B^{\prime})$ is a level-$j$ yes-pair and $|B\cap B^{*^{\prime}}|\leq
8Z_{j}\mu_{i}$. Our goal is to show that with probability at least
$1-e^{-\zeta}$, we report a non-empty region ${\mathcal{R}}^{\prime}$ that
does not contain any range-block appearing after $B^{\prime}$. We start with
the following simple observation whose proof is present in Section C.2.5.7.

######  Observation 4.5.40.

With probability $1-e^{-2\zeta}$, we sample at most $12\zeta
p|\hat{\mathcal{B}}|$ stream-blocks of $\hat{\mathcal{B}}$.

We assume from now on that this event indeed occurs and hence, we terminate
$\mathsf{Alg}{\mathsf{Gen}}$ only after processing all the elements of $B$. We
will use the following observation that is proved in Section C.2.5.8.

######  Observation 4.5.41.

With probability at least $1-e^{-2\zeta}$, the range-block $B^{\prime}$ is
marked as pseudo-suspicious while processing the first $\frac{Z_{j}}{2}$
elements of $S^{*}$ in $B$.

We assume that the event of the above observation indeed occur. Consider the
time when $B^{\prime}$ is marked pseudo-suspicious, say, after processing the
element $a_{t}$ of $B$. Recall that we execute multiple parallel runs of the
level-$j$ algorithm ${\mathsf{Alg}}\mathsf{Jump}{(j)}$ with input level-$j$
pair $(B,B^{\prime})$ and the subblock $B_{>t}$ of $t$. Since the subblock
$B_{>t}$ contains at least $\frac{Z_{j}}{2}$ elements of $S^{*}$, if
$B^{\prime}$ remains active pseudo-suspicious block throughout the run of our
algorithm, each such execution of ${\mathsf{Alg}}\mathsf{Jump}{(j)}$ returns
yes with probability at least $3/4$. We now consider the state of our
algorithm $\mathsf{Alg}{\mathsf{Gen}}$ at the end of the stream-block $B$ and
distinguish between the following two cases.

  * •

Case $1$: $B^{\prime}$ remains an active pseudo-suspicious block throughout
the processing of $B$. In this case, we have executed $\left\lfloor
2^{6}\zeta\right\rfloor$ independent instances of the level-$j$ algorithm
${\mathsf{Alg}}\mathsf{Jump}{(j)}$ with input level-$j$ pair $(B,B^{\prime})$
and the subblock $B_{>t}$ of $B$. Since $B^{\prime}$ remains an active pseudo-
suspicious block throughout the processing of $B$, from the correctness
guarantee of ${\mathsf{Alg}}\mathsf{Jump}{(j)}$, each of this instances report
yes with probability at least $3/4$. From Chernoff bound (see, 4.2.4), with
probability at least $1-e^{-2\zeta}$, more than $2^{5}\zeta$ of these calls
return yes. We assume from now on that this event indeed occurs. Let