#  Estimating the Longest Increasing Subsequence in Nearly Optimal Time

Alexandr Andoni
Columbia University
<EMAIL_ADDRESS>Research supported in part by NSF grants (CCF-1617955,
CCF-1740833, CCF-2008733), and Simons Foundation (#491119). Negev Shekel
Nosatzki
Columbia University
<EMAIL_ADDRESS>Research supported in part by NSF grants (CCF-1617955 and
CCF-1740833), and Simons Foundation (#491119). Sandip Sinha
Columbia University
<EMAIL_ADDRESS>Supported by NSF grants CCF-1714818, CCF-1822809,
IIS-1838154, CCF-1617955, CCF-1740833, and by the Simons Collaboration on
Algorithms and Geometry. Clifford Stein
Columbia University
<EMAIL_ADDRESS>Research partly supported by NSF Grants CCF-1714818 and
CCF-1822809.

###### Abstract

Longest Increasing Subsequence (LIS) is a fundamental statistic of a sequence,
and has been studied for decades. While the LIS of a sequence of length $n$
can be computed exactly in time $O(n\log n)$, the complexity of estimating the
(length of the) LIS in sublinear time, especially when LIS $\ll n$, is still
open.

We show that for any $n\in{\mathbb{N}}$ and $\lambda=o(1)$, there exists a
(randomized) _non-adaptive_ algorithm that, given a sequence of length $n$
with LIS $\geq\lambda n$, approximates the LIS up to a factor of
$1/\lambda^{o(1)}$ in $n^{o(1)}/\lambda$ time. Our algorithm improves upon
prior work substantially in terms of both approximation and run-time: (i) we
provide the first sub-polynomial approximation for LIS in sub-linear time; and
(ii) our _run-time complexity_ essentially matches the trivial _sample
complexity_ lower bound of $\Omega(1/\lambda)$, which is required to obtain
any non-trivial approximation of the LIS.

As part of our solution, we develop two novel ideas which may be of
independent interest. First, we define a new Genuine-LIS problem, in which
each sequence element may be either genuine or corrupted. In this model, the
user receives unrestricted access to the actual sequence, but does not know a
priori which elements are genuine. The goal is to estimate the LIS using
genuine elements only, with the minimal number of tests for genuineness. The
second idea, Precision Tree, enables accurate estimations for composition of
general functions from “coarse” (sub-)estimates. Precision Tree essentially
generalizes classical precision sampling, which works only for summations. As
a central tool, the Precision Tree is pre-processed on a set of samples, which
thereafter is repeatedly used by multiple components of the algorithm,
improving their amortized complexity.

###### Contents

  1. 1 Introduction
    1. 1.1 Our contributions
    2. 1.2 Related work
  2. 2 Preliminaries
  3. 3 Technical overview
    1. 3.1 Our approach
    2. 3.2 Main Algorithm
    3. 3.3 Genuine-LIS problem: overview of the algorithm EstimateGenuineLIS
    4. 3.4 Block-LIS problem: overview of the algorithm EstimateBlockLIS
    5. 3.5 Precision-Tree data structure
      1. 3.5.1 Construction of the Precision-Tree data structure
  4. 4 Main Algorithm for Estimating LIS
  5. 5 Precision-Tree Data Structure
    1. 5.1 Tree Sampling Data Structure
    2. 5.2 Decomposing Precision-Tree
  6. 6 Algorithm for Genuine-LIS: Proof of Theorem 4.1
    1. 6.1 Algorithm Description
      1. 6.1.1 Extracting pseudo-solutions
      2. 6.1.2 Partitioning the pseudo-solutions
      3. 6.1.3 Estimator Computation
    2. 6.2 Analysis
      1. 6.2.1 Upper Bound
      2. 6.2.2 Lower Bound
  7. 7 Algorithm for Block-LIS: Proof of Theorem 4.2
    1. 7.1 Extending the Genuine-LIS problem
    2. 7.2 Algorithm
      1. 7.2.1 Algorithm Overview
    3. 7.3 Main analysis
    4. 7.4 Dyadic Construction for Candidate Intervals: Proof of Lemma 7.3
    5. 7.5 Analysis of Block-LIS invariants: Proof of Lemma 7.5
  8. 8 Genuine-LIS and Block-LIS Extensions: Proof of Lemmas 7.2 and 6.3
    1. 8.1 Block-LIS extension
    2. 8.2 Genuine-LIS extensions
      1. 8.2.1 Sparse instances
      2. 8.2.2 Genuine-LIS over interval space
  9. A Proof of Theorem 4.3
    1. A.1 Recursion Analysis

##  1 Introduction

Longest Increasing Subsequence (LIS) is a fundamental measure of a sequence,
and has been studied for decades. Near linear-time algorithms have been known
for a long time, for example, the Patience Sorting algorithm [Ham72, Mal73]
finds a LIS of a sequence of length $n$ in time $O(n\log n)$. The celebrated
Ulam’s problem asks for the length of a LIS in a random permutation; see
discussion and results in [AD99]. LIS is also an important special case of the
problem of finding a Longest Common Subsequence (LCS) between two strings, as
LIS is LCS when one of the strings is monotonically increasing. Recently,
there has been significant progress in approximation algorithms for LCS of two
or more strings [RSSS19, DS21, GKLS21, BD21]. Moreover, LIS is often a
subroutine in LCS algorithms: for example, when strings are only mildly
repetitive [Gus97, Chapter 12], or more recently in approximation algorithms
[HSSS19, Nos21]. Longest increasing subsequences have multiple applications in
areas such as random matrix theory, representation theory, and physics [AD99],
and the related LCS problem also has multiple applications in bioinformatics,
and is used for data comparisons such as in the diff command.

In the quest for faster algorithms, researchers started studying whether we
can estimate the length of a LIS (denoted LIS as well) in sublinear time. An
early version of this question underpins one of the first sublinear-time
algorithms: to test whether an array is sorted, or monotonically increasing
[EKK+00] — i.e., whether the length of the LIS is $n$ or is at most
$(1-\epsilon)n$. [EKK+00] gave a $O(\log n/\epsilon)$ time algorithm, and this
running time was later shown to be tight [ACCL07, Fis04]. Since then, there
have been numerous influential results on testing monotonicity and other
similar properties; see, e.g., [DGL+99, PRR06, Fis01, CS14, BCS20, BS19,
PRW20, BCLW19, AN10, SW07] and the book [Gol17].

While monotonicity results focus on the case when $\textsc{LIS}\approx n$, the
case when $\textsc{LIS}\ll n$ has seen much less progress. The first result
for this regime [SS17] shows how to $(1+\epsilon)$-approximate the length when
the LIS is still large: they distinguish the case when
$\textsc{LIS}\geq\lambda n$ from the case when
$\textsc{LIS}\leq(\lambda-\epsilon)n$ (for any $\lambda>0$) using
$(1/\epsilon)^{O(1/\epsilon)}\log^{O(1)}n$ time, which only gives a
$(1+\epsilon)$-factor approximation in truly sublinear time if
$\lambda=\Omega(\log\log n/\log n)$. For arbitrary $\lambda<1$, assuming that
$\textsc{LIS}\geq\lambda n$ [RSSS19] gave an algorithm that achieves
$O(1/\lambda^{3})$-factor approximation of LIS in
$\tilde{O}(\sqrt{n}/\lambda^{7})$ time.111The formal definition of an
approximation algorithm here is one that has to return
$\widehat{\textsc{LIS}}$ such that $\widehat{\textsc{LIS}}\leq\textsc{LIS}$,
and the approximation factor is $\textsc{LIS}/\widehat{\textsc{LIS}}$.
Equivalently, one can conceptualize an $\alpha$-approximation algorithm (for
$\alpha\geq 1$) as one that can distinguish the case when
$\textsc{LIS}\geq\lambda n$ from the case when $\textsc{LIS}<\lambda
n/\alpha$.  Recently, [MS21] improved upon this result by presenting an
algorithm with approximation $O(1/\lambda^{\epsilon})$ and runtime
$O(n^{1-\Omega(\epsilon)}(\log n/\lambda)^{O(1/\epsilon)})$. Independently,
[NV21] obtained a non-adaptive $O(1/\lambda)$-approximation algorithm using
$\tilde{O}(\sqrt{r}/\lambda^{2})$ queries, where $r$ is the number of distinct
values. The authors of [NV21] also proved a lower bound, showing that any
_non-adaptive_ algorithm that estimates the LIS to within an additive error of
$\epsilon n$ requires $(\log n)^{\Omega(\log(1/\epsilon))}$ queries.

To put the above results into context, contrast LIS with the problem of
estimating the weight of a binary vector of length $n$: when the weight is at
least $\lambda n$, we can approximate the weight up to a factor of
$1+\epsilon$ by sampling $O_{\epsilon}(1/\lambda)$ positions, which is
optimal. So far, one cannot rule out that a similar performance is achievable
for estimating LIS too, in fact for $\lambda$ as large as $1/\log n$. The
aforementioned prior results not only have approximation factors that are
polynomial in $1/\lambda$ but also time / sample complexities that are worse
by a polynomial factor in $n$ or $1/\lambda$. Hence the following guiding
question remains open:

Can we estimate the length of LIS in essentially the time needed to estimate
the weight of a binary vector?

###  1.1 Our contributions

In this paper we come close to answering the above question in the
affirmative, by obtaining an algorithm that runs in time near-linear in
$1/\lambda$, and achieves sub-polynomial in $1/\lambda$ approximation. We show
the following:

######  Theorem 1.1 (Main theorem).

For $n\in{\mathbb{N}}$, and any $\lambda=o(1)$, there exists a (randomized)
non-adaptive algorithm that, given a sequence of length $n$ with
$\textsc{LIS}\geq\lambda n$, approximates the length of LIS up to a
$1/\lambda^{o(1)}$ factor in $O\left(\tfrac{1}{\lambda}\cdot n^{o(1)}\right)$
time with high probability.

We find this result quite surprising, as one may guess that when
$\lambda\approx 1/\sqrt{n}$ (which is the LIS length of a random permutation),
one would need to read essentially the entire sequence (implying a
$\Omega(1/\lambda^{2})$ lower bound on the number of queries needed). On the
contrary, when $\lambda\approx 1/\sqrt{n}$, our run-time (and hence sample
complexity) nearly matches the streaming complexity from [GJKK07, EJ08]
(albeit with worse approximation).

##### Technical Contributions.

Our main technical contributions are three-fold (see technical overview in
Section 3):

  * •

We define (the LIS problem in) a new sublinear computational model, which we
call Genuine-LIS and which may be of independent interest. In the Genuine-LIS
problem, we are given a sequence $y\in{\mathbb{N}}^{n}$, with a caveat that
only some of the elements of $y$ are “genuine” and the others are “corrupted”,
a property we can test an element for. The goal is to estimate the length of
LIS among the genuine elements of $y$, using as few tests as possible, while
the values of $y$ are known to the algorithm “for free”.

  * •

We show how one can efficiently reduce the LIS problem to Genuine-LIS and vice
versa. These reductions together constitute the backbone of our recursive
algorithm.

  * •

To obtain the promised query complexity, we develop a new data structure, that
we call a Precision-Tree. This data structure samples non-adaptively (but non-
uniformly) elements of the input $y$ and preprocesses them for efficient
operations on the sampled elements. This part is the only part of the
algorithm that samples the input string — the aforementioned recursive calls
of LIS and Genuine-LIS problems access this data structure only. Furthermore,
the data structure allows one to compute accurate estimations for composition
of general functions from “coarse” (sub-)estimates — a requirement for our
recursive approach.

While this paper makes progress in understanding the complexity of estimating
the LIS, the following important question remains open:

######  Open Question (($1+\epsilon$)-approximation).

Does there exist an algorithm that, given a sequence of length $n$ with
$\textsc{LIS}\geq\lambda n$, estimates the LIS up to a $1+\epsilon$ factor in
$O\left(\tfrac{1}{\lambda}\cdot n^{o(1)}\right)$ time with probability 2/3?

We believe that finding an improved approximation algorithm for the Genuine-
LIS problem above may lead to a $(1+\epsilon)$ approximation algorithm for
LIS.

We give a technical overview of our algorithm in Section 3, after setting up
preliminaries in Section 2. Section 4 contains the proof of the main theorem,
assuming results proved in subsequent sections. In Section 5, we develop the
Precision-Tree data structure that is used to improve the sample and time
complexity of the main algorithm. The guarantees of the two primary
subroutines are proved in Section 6 and Section 7. In Section 8, we extend
these algorithms in certain ways critical to our final application.

###  1.2 Related work

Computing the length of LIS has also been studied in the streaming model,
where settling its complexity is a major open problem [P44]. In this setting,
the main question is to determine the minimum space required to estimate the
length of LIS by an algorithm reading the sequence left-to-right. [GJKK07,
EJ08] gave deterministic one-pass algorithms to $(1+\epsilon)$-approximate the
LIS using $O(\sqrt{n})$ space, and matching lower bounds against deterministic
algorithms were given by [EJ08, GG07]. These lower bounds are derived using
deterministic communication complexity lower bounds and provably fail to
extend to randomized algorithms [Cha12]. However, no randomized algorithm
requiring $o(\sqrt{n})$ space is known for this problem either. We note that
our algorithm can be used in the streaming setting, yielding streaming
complexity $O(n^{1/2+\epsilon})$ for approximation $n^{o(1)}$.

There has been much more success on the “complement” problem of estimating the
distance to monotonicity, i.e., $d_{m}:=n-\textsc{LIS}$, in both the
sublinear-time and the streaming settings. In the random-access setting, the
problem was first studied in [ACCL07], and later in [SS17], who gave an
algorithm that achieves $(1+\epsilon)$-approximation in time
$\operatorname{poly}(1/d_{m},\log n)$ for any constant $\epsilon>0$. These
algorithms have been also used, indirectly, for faster algorithms for
estimating Ulam distance [AIK09, NSS17] and smoothed edit distance [AK12].

In the streaming setting, several results were obtained which achieve
$O(1)$-approximation of $d_{m}$ using $\operatorname{polylog}(n)$ space
[GJKK07, EJ08]. This culminated in a randomized $(1+\epsilon)$-approximation
algorithm using $\operatorname{polylog}(n)$ space by Saks and Seshadhri
[SS13], and a deterministic $(1+\epsilon)$-approximation algorithm using
$\operatorname{polylog}(n)$ space by Naumovitz and Saks [NS15]. [NS15] also
showed space lower bounds against $(1+\epsilon)$-approximation streaming
algorithms of $\Omega(\log^{2}n/\epsilon)$ (deterministic) and
$\tilde{\Omega}(\log^{2}n/\epsilon)$ (randomized).

The LIS problem has also been studied recently in other settings, such as the
MPC and the fully dynamic settings. [IMS17] gave a
$(1+\epsilon)$-approximation, $O(1/\epsilon^{2})$-round MPC algorithm for LIS
whenever the space per machine is $n^{3/4+\Omega(1)}$. In the dynamic setting,
a sequence of works [MS20, GJ21a] culminating in [KS21], gave the first exact
dynamic LIS algorithm with sublinear update time, and also gave a
deterministic algorithm with update time $n^{o(1)}$ and approximation factor
$1-o(1)$. [GJ21b] showed conditional lower bounds on update time for certain
variants of the dynamic LIS problem.

##### Subsequent Work.

The main result from this paper was very recently used for estimating the
Longest Common Subsequence (LCS) problem. In particular, [Nos21] gave the
first sub-polynomial approximation for LCS in linear time, invoking our
algorithm as a sub-routine.

##  2 Preliminaries

##### Sequences and intervals.

Given a set $\Omega$ and $n\in{\mathbb{N}}$, a sequence
$y=(y_{1},y_{2},\cdots,y_{n})\in\Omega^{n}$ is an ordered collection of
elements in $\Omega$. A block sequence $y\in\Omega^{n\times k}$ is a partially
ordered collection of elements in $\Omega$. Abusing notation, we will also
allow for some elements in a block to be “null” — for example, we write
$y\in{\mathbb{N}}^{n\times k}$ to also mean
$y\in\\{{\mathbb{N}},\bot\\}^{n\times k}$, where $\bot$ is “null”.

For $\ell\in[n]$, we say that $z=(z_{1},\cdots,z_{\ell})$ is a subsequence of
$y$ of length $\ell$, and denote it by $\\{y_{i_{j}}\\}_{j}$, if there exist
integers $1\leq i_{1}<i_{2}<\cdots<i_{\ell}\leq n$ such that $z_{j}=y_{i_{j}}$
for all $j\in[\ell]$. We refer to the indices $i_{j}$ as coordinates and the
values $y_{i_{j}}$ as element values. For a block sequence $y$, we say that
$z=(z_{1},\cdots,z_{\ell})$ is a subsequence of $y$ of length $\ell$, and
denote it by $\\{y_{w_{j}}\\}_{j}$, if there exist integers $1\leq
i_{1}<i_{2}<\cdots<i_{\ell}\leq n$ such that $z_{j}\in y_{i_{j},*}$ for all
$j\in[\ell]$.

Define the interval space $\mathcal{I}\triangleq\\{[a,b]\mid
a,b\in{\mathbb{N}},a\leq b\\}\cup\\{[a,b)\mid
a\in{\mathbb{N}},b\in[1,\infty],a<b\\}$. For $I\in\mathcal{I}$, we use $|I|$
to denote $|I\cap{\mathbb{N}}|$, i.e., the number of natural numbers contained
in interval $I$. We often refer to an $x$-interval $X\in\mathcal{I}\cap
2^{[n]}$ as an interval of coordinates, and a $y$-interval $Y\in\mathcal{I}$
as an interval of element values.

For a block sequence $y\in{\mathbb{N}}^{n\times k}$ and a $y$-interval
$Y\in\mathcal{I}$, we write $y\cap Y$ to denote the _multi-set_ of elements in
$y$ that are also in $Y$. Also, for $X\subseteq[n]$, $y(X)$ is the sequence
with first coordinates restricted to $X$. We also define $y(X,Y):=y(X)\cap Y$.

##### Monotonicity.

We define monotone sets as follows:

######  Definition 2.1 (Monotone sets).

Fix a (potentially partial) ordered set $(\Omega,<)$. We say that a set
$P\subseteq{\mathbb{N}}\times\Omega$ is _monotone_ if for all $(i,u),(j,v)\in
P\times P$, we have (i) $i=j\Leftrightarrow u=v$; and (ii) $i<j\Leftrightarrow
u<v$.

Note that this definition captures the notion of an increasing subsequence. In
particular, for the standard notion of an increasing subsequence over natural
numbers, we take $\Omega={\mathbb{N}}$ and $<$ as the usual “less than”
relation over ${\mathbb{N}}$ (a total order). However, we will need this more
general definition to consider increasing subsequences over other partially
ordered sets, like the space of intervals $\mathcal{I}$.

For a finite set $P\subset{\mathbb{N}}\times\Omega$, a longest increasing
subsequence (LIS) of $P$ is a monotone set $Q\subset P$ of maximum
cardinality. We often use OPT to refer to a particular LIS, and use
$|\textsf{OPT}|$ to denote its length.

##### Distributions.

For $p\in[0,1]$, we use $\operatorname{\mathtt{Ber}}(p)$ to denote the
Bernoulli distribution with success probability $p$, and
$\operatorname{\mathtt{Bin}}(n,p)$ to denote the binomial distribution with
parameters $n$ and $p$. By convention, we project $p$ to the range $[0,1]$
whenever $p>1$ or $p<0$.

We use “i.i.d. random variables” to mean that a collection of random variables
is independent and identically distributed, and use “sub-sampling i.i.d. with
probability $p$” to mean that each element is sampled independently with equal
probability $p$.

##### Operations on Vectors, Sets, Functions.

For a set $A\subset{\mathbb{R}}$ and a number $\alpha$, we define
$A+\alpha:=\\{a+\alpha:a\in A\\}$ and $\alpha A:=\\{\alpha\,a:a\in A\\}$. We
write $\log$ to denote binary logarithm.

The notation $\circ$ is used for function composition (i.e., $g\circ
f(x)=g(f(x))$, and $\oplus$ is used for direct sum. We use the notation $*$ as
argument of a function, by which we mean a vector of all possible entries. For
example, $f(*)$ is a vector of $f(i)$ for $i$ ranging over the domain of $f$
(usually clear from the context).

We use $E_{b}(k)$ for $b,k\in{\mathbb{N}}\cup\\{\infty\\}$ to denote the set
of powers of $b$ bounded by $k$, i.e., $E_{b}(k)\triangleq\\{b^{i}\mid
i\in{\mathbb{N}}\\}\cap[1,k]$. We also define $E_{b}\triangleq E_{b}(\infty)$.
We use ${\mathbb{R}}_{+}$ to denote the set of non-negative real numbers.

##### Approximations.

Our constructions generate approximations which contain both multiplicative
and additive terms. We use the following definition:

######  Definition 2.2 ($(\alpha,\beta)$-Approximation).

For $\alpha\geq 1$ and $\beta>0$, an $(\alpha,\beta)$-approximation $\hat{q}$
of a quantity $q$ is an $\alpha$-multiplicative and $\beta$ additive
estimation of $q$, i.e., $\hat{q}\in[q/\alpha-\beta,q]$.

The following fact shows that to obtain a multiplicative approximation which
is a function of the LIS, it suffices to show $(\alpha,\beta)$-approximation.

######  Fact 2.3.

Suppose we have an algorithm $\mathcal{A}$ that for any
$n\in{\mathbb{N}},\lambda\in(0,1)$, for some $q\in(0,1)$, outputs a
$(1/\lambda^{q},\lambda n)$-approximation for some unknown quantity
$\ell\in[0,n]$ in time $t$. Then there exists an algorithm that outputs
$\widehat{\ell}\in[\Omega(\delta^{p}),1]\cdot\ell$ in time $t+O(1)$, where
$p\triangleq\tfrac{q}{1-q}$, as long as $\ell\geq 2\delta n$.

###### Proof.

The algorithm calls $\mathcal{A}$ with parameter $\lambda=\delta^{1+p}$, and
returns the same output. Then, the upper bound is immediate by definition of
$(\alpha,\beta)$-approximation. For the lower bound, as long as $\ell\geq
2\delta n$, we have that:

$\widehat{\ell}\geq\delta^{q(1+p)}\cdot\ell-\delta^{1+p}\cdot
n\geq\delta^{p}\cdot\ell-\tfrac{1}{2}\delta^{p}\cdot\ell\geq\tfrac{1}{2}\delta^{p}\ell$

∎

##### Other notation.

Notation $\tilde{O}(\cdot)$ hides $\operatorname{polylog}(n)$ factors, while
$O^{*}(\cdot)$ hides a factor of $n^{o(1)}$.

##  3 Technical overview

Our starting point is the algorithm of [RSSS19] which achieves
$O(1/\lambda^{3})$ approximation in time $\tilde{O}(\sqrt{n}/\lambda^{7})$.
Let OPT be (the coordinates of) an optimum solution (LIS) with length
$|\textsf{OPT}|\geq\lambda n$. Their algorithm consists of 2 main steps:

  1. 1.

Partition $[n]$ into $\sqrt{n}$ disjoint contiguous x-intervals
$X_{1},X_{2},\ldots,X_{\sqrt{n}}$ of length $\sqrt{n}$ each. For
$i\in[\sqrt{n}]$, let $y(X_{i})$ be the restriction of the input sequence $y$
to $x$-interval $X_{i}$. The goal is to approximate the $y$-interval
$Y_{i}\triangleq[s_{i},\ell_{i}]$, where $s_{i}$ and $\ell_{i}$ are,
respectively, the minimum and maximum values in $y(X_{i}\cap\textsf{OPT})$. To
do this, one samples $O(1/\lambda)$ elements in $X_{i}$, and generates
$O(1/\lambda^{2})$ _candidate $y$-intervals_ (using pairs of sampled element
values).

  2. 2.

Generate a set of mutually disjoint _pseudo-solutions_ , each of which is a
sequence of $\Omega(\lambda\sqrt{n})$ candidate $y$-intervals that are
monotone, i.e., all values in a candidate interval in x-interval $X_{i}$ are
less than all values in a candidate interval in x-interval $X_{j}$ for all
$i<j$. Estimate the quality of each pseudo-solution (the sum of LIS of the
candidate intervals in it) by simply sampling $O(\log^{O(1)}n/\lambda^{4})$
x-intervals and computing the LIS within relevant candidate intervals. Output
the largest quality.

Their analysis proceeds as follows. For each x-interval $X_{i}$, some
candidate $y$-interval is a good approximation of the interval $Y_{i}$ w.h.p.,
so the union of the LIS in all pseudo-solutions covers a large fraction of
OPT. Since there are $O(1/\lambda^{3})$ pseudo-solutions, the output is a
$O(1/\lambda^{3})$-approximation of OPT. The runtime of
$\tilde{O}(\sqrt{n}/\lambda^{7})$ is dominated by the time required to
evaluate the quality of pseudo-solutions to sufficient accuracy. One can also
apply this technique recursively to improve the runtime, at the cost of worse
approximation.

In [MS21], this result is improved by giving an algorithm for LIS with
approximation factor $O(1/\lambda^{\epsilon})$ and runtime
$O(n^{1-\Omega(\epsilon)}\cdot(\log n/\lambda)^{1/\epsilon})$ for any constant
$\epsilon>0$. The polynomial dependence on $1/\lambda$ seems essential since
the algorithm in [RSSS19] is used as a sub-routine. In [NV21], a _non-
adaptive_ algorithm is presented with sample complexity
$\tilde{O}(\sqrt{r}/\lambda^{2})$ and approximation $O(1/\lambda)$, where $r$
is the number of distinct values. Again, the polynomial dependence of the
sample complexity on $r$ and $1/\lambda$ seems intrinsic.

There are several fundamental obstacles in improving these bounds, and in
particular, getting the runtime down all the way to $1/\lambda$ while
improving the approximation. One such obstacle is that the straight-forward
approach (as in prior work) of independent recursions cannot obtain better
than $1/\lambda^{2}$ run-time in the worst-case. The issue is that even if one
is able to isolate all possible $y$-interval ranges efficiently, there must
still be at least $1/\lambda$ such ranges (optimally), and recusing of each
such $y$-interval without knowing a priori which coordinates contain the
relevant $y$-values would require $1/\lambda$ samples just to find a single
sample of relevance in each (sub-)instance (i.e. for each $y$-interval). We
will return to this obstacle later and show how we improve the amortized
complexity for it.

###  3.1 Our approach

Similarly to [RSSS19], we generate candidate $y$-intervals based on random
samples, and generally look for increasing sequences of intervals, each with a
large local LIS. Beyond this general similarity, our algorithm develops a few
new ideas, in particular in how we work with these candidate intervals, and
especially how we find LIS’s among these candidate intervals. In particular,
our contribution can be seen through three main components.

First, we introduce a new problem, termed Genuine-LIS, which captures the
problem of estimating the longest (sub-)sequence of increasing intervals, each
with a large “local LIS”. This problem is a new model for sublinear-time
algorithms, which has not appeared in prior literature to the best of our
knowledge.

The Genuine-LIS problem is defined as follows. The input is a sequence $g$
where each element is associated with an additional flag signifying whether it
is _genuine_ or not, i.e., $g\in({\mathbb{N}}\times\\{0,1\\})^{n}$. One
receives unrestricted access to the elements (i.e., the first coordinates)
which is denoted by $g(*)_{1}\in{\mathbb{N}}^{n}$. However, one must “pay” to
test whether an element is genuine; this is determined by the second
coordinates $g(*)_{2}\in\\{0,1\\}^{n}$, referred to as genuineness flags. The
goal is to compute the length of the longest increasing subsequence of
$g(*)_{1}$ restricted to genuine elements, i.e., of
$g((g(*)_{2})^{-1}(1))_{1}$, using as few tests for genuineness as possible.

Second, we show how to efficiently reduce the LIS problem to a (smaller)
instance of the Genuine-LIS problem, where the “genuineness” flag of an
element corresponds to LIS of an $x$-interval being large enough. In
particular, this is where we generate the aforementioned candidate
$y$-invervals. The algorithm reduces the problem to finding a (global) LIS
amongst a set of candidate intervals, each with a large (local) LIS. We solve
this via a composition of 2 sub-problems: the Genuine-LIS problem takes care
of the “global LIS” of candidate-intervals, while the standard LIS problem
recursively estimates the “local LIS” (these ideas and terms will be made
precise later). The main challenge here is to generate candidate intervals in
a succinct manner: we manage to reduce the number of sampled anchor needed to
$\approx 1/\lambda$, as well as limiting the number of candidate intervals to
be near-linear in the number of sampled points.

Third, to optimize the sampling of the string, we use a novel sampling scheme
endowed with a data structure, termed Precision-Tree. At preprocessing, the
structure samples a number of positions in the input string (non-adaptively),
which are not uniform but rather correspond to a tree with non-uniform leaf
levels (hence the name). We then build a global data structure on these
samples for efficient access. In particular, we develop a tree decomposition
procedure (to be discussed later), and repeatedly use sub-trees across
different sub-instances we generate, improving the overall sample complexity.
We highlight the fact that we reuse both the samples (and hence randomness)
across different (sub-)instances for both of the LIS and Genuine-LIS problems.
In addition, the Precision-Tree data structure provides a quick way to narrow
down on all samples in some $x$-interval whose value is in given $y$-interval
$Y$.

Before continuing this overview, we formally define a slightly generalized
version of the LIS problem, termed Block-LIS, as well as the aforementioned
Genuine-LIS problem. Following that, we provide an overview of the algorithms
to solve these two problems. The high-level flow of our algorithm is described
in Figure 1.

Figure 1: High level flow of the main algorithm (Theorem 1.1). Each arrow
represents one or more calls to the corresponding algorithm.

##### The Block-LIS problem.

This problem extends standard LIS problem in two ways. First, the main input
is a sequence of $n$ blocks, each containing (at most) $k$ elements, and at
most one element in each block may participate in a sequence. Second, we are
also given a range of values $Y\in\mathcal{I}$, such that each element of a
subsequence must be in $Y$.

Formally, we define the Block-LIS as follows: given a sequence
$y\in{\mathbb{N}}^{n\times k}$ and a range of values $Y\in\mathcal{I}$,
compute the length of a maximal sub-sequence
$\textsf{OPT}\subseteq[n]\times[k]$, such that
$\\{(w_{1},y_{w})\\}_{w\in\textsf{OPT}}$ is monotone and
$\\{y_{w}\\}_{w\in\textsf{OPT}}\subseteq Y$. Sometimes, we also restrict the
set of blocks to an interval $X\subseteq[n]$, and define the quantity
${\textsf{Block-LIS}}(y,X,Y)$ as the longest increasing subsequence of
$y\in{\mathbb{N}}^{X\times[k]}$ using elements in $Y$.

The standard LIS problem can be seen as the Block-LIS problem with $k=1$ and
$Y={\mathbb{N}}$ — which is how we instantiate the original input sequence
$y\in{\mathbb{N}}^{n}$ in our Block-LIS algorithm. The main advantage of this
generalization appears when the sequence is sparse in $Y$, i.e. most elements
cannot participate in any LIS. Then, we show the multiplicative approximation
factor for Block-LIS is not only a function of the additive error $\lambda n$,
but also of the total number of elements of $y$ in range $Y$ (i.e.,
$|y(X,Y)|$). In particular, we show that this approximation is a function of
$\tfrac{\lambda n}{|y(X,Y)|}$.

While the generalization to blocks is not a core necessity of the algorithm
(in fact, one can consider the values in each block in descending manner,
yielding an equivalent problem with no blocks required), its main use comes
from our need to instantiate several overlapping instances using the same
Precision-Tree data structure (to be discussed later).

Finally, we note that we similarly generalize the Genuine-LIS to work over
blocks: input $g\in({\mathbb{N}}\times\\{0,1\\})^{n\times k}$ and the LIS is
allowed to use only one (genuine) element per block.

###  3.2 Main Algorithm

The main algorithm for estimating the LIS is merely the following (see
Algorithm 1):

  1. 1.

Preprocess Precision-Tree $T=T_{\delta}(y)$ of the input sequence with
parameter $\delta\triangleq\lambda/n^{o(1)}$ (the exact $o(1)$ parameter will
be made precise later).

  2. 2.

Run the Block-LIS algorithm that has access only to the data structure $T$.
(we note that this algorithm itself recursively runs the algorithms for
Genuine-LIS and Block-LIS.)

###  3.3 Genuine-LIS problem: overview of the algorithm EstimateGenuineLIS

Recall that in the Genuine-LIS problem with input
$g\in({\mathbb{N}}\times\\{0,1\\})^{n}$, one receives unrestricted access to
the elements (i.e., the first coordinates), but must “pay” to test whether an
element is genuine (determined by the second coordinates). The goal is to
compute the length of the longest increasing subsequence of $g(*)_{1}$
restricted to genuine elements, while minimizing the number of genuiness
tests.

We derive two complementary solutions to the Genuine-LIS problem: one direct
(without further recursion), and the other by reducing the problem to standard
sublinear-time LIS estimation. To highlight our novel contribution, we
contrast it with the framework of [RSSS19], that implicitly gives a solution
to the Genuine-LIS problem, albeit with sub-optimal approximation. In
particular, the following algorithm for Genuine-LIS is analogous to the
algorithm in [RSSS19] based on generating pseudo-solutions (maximal sequences
of candidate intervals).

  1. 1.

Using the first coordinates only, look for a maximal increasing subsequence
$P_{1}$ containing $\gtrapprox\lambda n$ elements and remove $P_{1}$ from the
sequence.

  2. 2.

Repeat step (1) until there are no more sequences of length $\gtrapprox\lambda
n$. This generates (disjoint) solutions $P_{1},\ldots,P_{t}$ for some
$t\lessapprox 1/\lambda$.

  3. 3.

Sub-sample $\approx 1/\lambda$ elements from the union $P=\cup_{i\in t}P_{i}$
and check if each one is genuine. Let $\kappa$ be the number of Genuine
elements in this sampled set.

  4. 4.

Output $\lambda^{2}n\cdot\kappa$.

It is easy to see that this algorithm yields, with constant probability, a
$(2/\lambda,\lambda^{2}n)$-approximation with approximately $1/\lambda$ tests
for genuineness. First, if the Genuine-LIS is at most $2\lambda n$, then the
output (being greater than $0$) is already a
$(2/\lambda,\lambda^{2}n)$-approximation, as

$\tfrac{\textsf{Genuine-LIS}}{2/\lambda}-\lambda^{2}n\leq\tfrac{2\lambda
n}{2/\lambda}-\lambda^{2}n=0\leq\textsf{Genuine-LIS}.$

Otherwise, $P$ contains most of the Genuine-LIS elements, and since
$t\lessapprox 1/\lambda$, the Genuine-LIS is at least $\lambda/2$ times the
number of genuine elements in $P$.

Thus, by the sampling mechanism above, we can estimate the proportion of
genuine elements to sufficient accuracy with constant probability. Observe
that the approximation is in fact proportional to $1/\lambda\kappa$, and that
the worst approximation happens when $P$ is “sparse”, i.e., when only
approximately $\lambda n$ elements in $P$ are genuine. For such a sparse case,
however, one can instantiate the Genuine-LIS algorithm as a Block-LIS one,
restricted to the genuine elements. In fact, this “sparse” case is precisely
where the approximation factor is minimal, i.e., $\tfrac{\lambda n}{|y|}=1$
where $y$ is the genuine-elements-only subsequence. Our improved approximation
stems, in part, from balancing between the dense and sparse cases as above.

##### Speeding up LIS extraction using dynamic LIS.

The Genuine-LIS instances we generate are of size $\lessapprox 1/\lambda$, and
our goal is to obtain overall run-time that is near-linear in $1/\lambda$ as
well. The standard, dynamic-programming solution for finding and extracting
the optimal LIS each time for step (1) above can potentially incur an overhead
that is quadratic in the instance size (each LIS extraction would take linear
time, and we need to greedily extract up to a near-linear number of
solutions), leading to a polynomially-worse time. To ensure near-linear time,
we adopt a fast dynamic LIS data structure from [GJ21a], and use it to
iteratively extract near-maximal pseudo-solutions.

##### Extensions to the Genuine-LIS algorithm.

Our complete algorithm needs three further extensions to the algorithm for the
Genuine-LIS problem, as follows.

  * •

Block version: just like for Block-LIS, we define the block version of
Genuine-LIS, where the input is a sequence
$g\in({\mathbb{N}}\times\\{0,1\\})^{n\times k}$, and we need to find the LIS
among the genuine elements, while using at most one element per size-$k$
block.

  * •

Sparse (unbalanced) instances: some encountered Genuine-LIS instances are
sparse, with many “null” elements, i.e., some blocks have less than $k$
elements (note that a “null” element is different from a “non-genuine” one, in
that it does not need to be tested). When the instance $g$ consists of $m\ll
nk$ non-null elements, we would like the approximation and runtime bounds to
be a function of $m/n$ (average block size) instead of $k$ (maximum block
size). To obtain the improved bound, we partition the blocks based on an
exponential discretization of the number of non-null elements, and output the
maximum over all instances, where each instance consists only of blocks
containing a similar number of non-null elements.

  * •

Genuine-LIS over intervals: the first coordinates of the Genuine-LIS instances
we generate apriori consist of intervals rather than integers. The challenge
is that we then need to find LIS over the partial order of intervals
$\mathcal{I}$. To illustrate why this poses an additional challenge, note that
the dynamic LIS data-structures from [MS20, GJ21a, KS21] (used to speed up our
algorithm) cannot immediately handle partial order sequences. An ideal
solution here would be a mapping $\varphi:\mathcal{I}\rightarrow{\mathbb{N}}$
that approximately preserves the overall LIS over all subsequences, and
therefore also preserves the overall LIS over the genuine elements. While we
are unable to show a single mapping that works for all intervals, we partition
the space of intervals into $\log(k/\lambda)$ sets $\mathcal{I}_{\ell}$ —
intervals in $\mathcal{I}$ whose length is in $[\ell,2\ell)$ — based on an
exponential discretization of the interval length $\ell$, and provide a
mapping $\varphi_{\ell}:\mathcal{I}_{\ell}\rightarrow{\mathbb{N}}$ for each
set of intervals $\mathcal{I}_{\ell}$. We eventually output the maximal
Genuine-LIS result over all such maps. This costs us merely another
$\log(k/\lambda)$-factor approximation, and a small additive error.

The formal statement for the algorithm to solve Genuine-LIS, named
EstimateGenuineLIS, is presented in Section 4, and its description and
analysis are in Section 6. The pseudo-code is presented in Algorithm 5. The
Genuine-LIS extensions are presented and analyzed in Section 8.

###  3.4 Block-LIS problem: overview of the algorithm EstimateBlockLIS

For the problem $\textsf{Block-LIS}(y,X,Y)$, we develop the algorithm
EstimateBlockLIS. Fundamentally, we reduce the instance to a Genuine-LIS
instance, where each genuineness flag is set to 1 if and only if the LIS of a
certain (smaller) sequence (which is itself a Block-LIS problem) is large
enough.

Our reduction starts by partitioning $X$ into consecutive intervals
$X_{1},\ldots,X_{\tau}$ of equal length, where $\tau$ is a dynamic, carefully
chosen branching factor, and is usually sub-polynomial in the instance size
(here think $\tau=n^{\epsilon}$). Next, we sample approximately $\tau/\lambda$
blocks $w_{j}\in X$ (termed _anchors_), and, for each $i\in[\tau]$, we collect
all the $y$-values across all the blocks $w_{j}\in X_{i}$ that are also in
$Y$, and generate a set of $y$-values $\mathcal{S}_{i}\subseteq Y$.

Using each set of $y$-values $\mathcal{S}_{i}$, we construct _candidate
intervals_ $\mathcal{Y}_{i}$. While this part is similar to the construction
from [RSSS19], we note that we need a more efficient construction to obtain
the near-optimal sample complexity. In particular, we require the number of
candidate intervals to be near-linear in $|\mathcal{S}_{i}|$, and hence we
construct a small candidate interval set
$|\mathcal{Y}_{i}|\approx|\mathcal{S}_{i}|$, while still ensuring that this
set covers all “relevant options” with only an extra logarithmic factor loss
in approximation. In particular, instead of looking for all possible pairs of
endpoints, we choose the endpoints in dyadic fashion (in particular, their
distance in the set $\mathcal{S}$ must be a power of 2).

Finally, we reduce the Block-LIS problem to a Genuine-LIS instance over $\tau$
blocks, where each block $i$ contains all the candidates intevals
$\mathcal{Y}_{i}$ — this Genuine-LIS instance thus captures “global” LIS (over
the candidate intervals). The first coordinates of the Genuine-LIS instance
are the candidate intervals $\mathcal{Y}_{i}$ themselves, while the second
coordinates (i.e., the genuineness flags) indicate whether the corresponding
“local” ${\textsf{Block-LIS}}(y,X_{i},Y^{\prime})$ estimated values are above
a certain threshold $\kappa$, for each $Y^{\prime}\in\mathcal{Y}_{i}$.

This threshold $\kappa$ itself depends on a parameter $\rho>1$, which
characterizes the relation between the “global” Genuine-LIS instance and the
“local” Block-LIS instances. Intuitively, $\rho$ is such that (roughly)
$1/\rho$ fraction of the $X_{i}$ intervals each have a $\lambda\rho$ fraction
of them participating in the LIS. Consider two extreme cases, one where the
LIS is uniformly distributed among all $X_{i}$ ($\rho=1$), and one where the
LIS is maximally concentrated among a small subset of the $x$-intervals
($\rho=1/\lambda$). Then, it is more difficult to certify an increasing
subsequence in the latter case, when the LIS is sparse. But in this case
testing the genuineness of a local LIS (inside a block $X_{i}$) is much
easier, since we only need to establish that it is $\Omega(|X_{i}|)$. In
general, there is a precise trade-off between the complexity of certifying the
global LIS versus the complexity of certifying the local Block-LIS. A priori,
we do not know $\rho$, so we simply iterate over all possible magnitudes
(again, by exponential discretization).

Once we formulate the overall Block-LIS problem as a composition of a “global”
Genuine-LIS over multiple “local” Block-LIS instances, we decompose the
problem through a procedure called Precision-Tree decomposition which will be
described next.

The formal statement for the EstimateBlockLIS algorithm is presented in
Section 4, and the algorithm description and analysis are in Section 7. The
pseudo-code (including sub-routines) are presented in Algorithms 6, 7 and 8.

###  3.5 Precision-Tree data structure

We note that a direct instantiation of the above algorithm yields the right
approximation, but will require at least $\approx 1/\lambda^{2}$ queries into
the input string $y$ (and hence run-time), and, moreover, require the
algorithm to be adaptive. The source of this inefficiency is precisely the
“small slopes” obstacle discussed earlier, which would lead to “wasting
samples” in any naïve rejection sampling mechanism. To improve the complexity,
and to allow our sampling algorithm to be non-adaptive, we introduce the
Precision-Tree data structure (Section 5). While based on the precision
sampling tool introduced in [AKO10, AKO11], the main development here is that
we augment the resulting tree for special operations described henceforth.

Intuitively, the Precision-Tree data structure can be thought of as a global
data structure holding enough information for simulating random samples for
multiple non-uniform (sub-)instances, specifically ones arising from
recursion. In particular, the data structure is an (incomplete) tree, where
(lowest-level) leafs correspond to samples of some input
$e\in\mathcal{E}^{n}$. The initial tree is defined over the input string
(i.e., $\mathcal{E}={\mathbb{N}}$), but we also consider Precision-Trees over
other domains $\mathcal{E}^{n}$ as described later (which are simply a
recasting the original single tree). The initial tree for the string
$y\in{\mathbb{N}}^{n}$ is constructed at random, using precision sampling, and
this is the only time when we access the string $y$ (in the entire LIS
algorithm). Overall, the Precision-Tree data-structure (the initial one as
well as the other trees we generate) supports several important properties we
need:

  * •

Since our algorithm is recursive (composition of Genuine-LIS and Block-LIS
algorithms), we need to provide samples for potentially very small contiguous
subsequences of $y$ (depending on what was sampled higher up in the
recursion). In other words, we need to be able to “zoom into” different
location of the input string with the right precision.

Our precision tree is sampled such that any sub-tree under any “sampled” node,
is another Precision-Tree instantiation (with potentially different
“precision” parameter).

  * •

In contrast to the original precision sampling tool that was designed for the
simple addition function (over elements), our application at hand requires
more complicated functions (indeed, the sub-linear Block-LIS and Genuine-LIS
algorithms).

We show how we can decompose the tree in a van Emde Boas-like layout: by
cutting it to obtain a number of different “lower sub-trees”, together with a
“top tree” whose domain are the lower sub-trees (as mentioned, all lower/top
sub-trees are themselves a precision tree). Then we can run algorithms on each
sub-tree, as well as a final algorithm recomposing the results from the sub-
trees, using the top tree.

  * •

Another crucial challenge is the following: as our overall algorithm recurses,
we may be “zooming in” on the same part of $y$ multiple times, but focusing on
different $y$-range intervals $Y$. Naïvely, one would use rejection sampling
here (rejecting samples with value not in $Y$), which however would yield a
polynomially worse sample complexity. In addition, our recursion happens not
only down the tree (i.e., on the lower sub-trees) but also on the top portion
of the tree (top tree above).

We augment our precision tree to allow us to reuse the randomness over
independent recursive calls into the same $x$-intervals, each focusing on a
different $y$-value ranges. In particular, for such an $x$-interval we will
have processed all the sampled entries to directly report samples with values
in a desired $y$-interval $Y$ (note that this is essentially a 2D range
reporting). In addition, the randomness is reused when computing the global
function on the top portion of the tree as described above.

####  3.5.1 Construction of the Precision-Tree data structure

We now describe the formal construction of Precision-Tree. Original precision
sampling from [AKO10, AKO11] is designed to estimate a summation function
$a=\sum_{i=1}^{n}a_{i}$, for unknown $a_{i}\in[0,1]$, from “coarse” estimates
for $a_{i}$. In our application, we need to generalize precision sampling from
a simple addition to general functions, allowing one to approximate $g\circ f$
where $g$ is a general function over $m$ coordinates and
$f=(f_{1},\ldots,f_{n})$ consists of $n$ independent functions on different
parts of the input, sharing the same co-domain.

We define Precision-Tree with parameter $\delta<1$, for a given vector of
elements $e=(e_{1},\ldots,e_{n})\in\mathcal{E}^{n}$, denoted $T_{\delta}(e)$,
as follows. The tree $T$ is a trimmed version of the full $\beta$-ary tree of
$\ell=\log_{\beta}n+1$ levels, with $n=\beta^{\ell}$ leafs, where parameter
$\beta>1$ is fixed; in particular, all nodes of $T$ have fan-out of either
$\beta$ or 0. Each leaf at level $\ell$ 222By convention, the level of the
root is 0. is associated with an integer representing its location in the
input string. Each internal node $v$ is associated with an interval
representing the unions of its leaf descendants (in the full tree); for
example, the root of $T$ is associated with the entire interval $[1,n]$, and
its children with $[1,n/\beta]$, $[n/\beta+1,2n/\beta]$, etc). For a node $v$
in the tree, we use $\mathcal{E}_{v}$ or $\mathcal{E}(v)$ to denote the set of
elements under $v$.

Given $n,\lambda$, and $\beta$, we construct the trimmed Precision-Tree
$T_{\lambda}(e)$ as follows. We assign a (random) precision score
${\mathcal{P}}_{v}$ to each node $v$ by the following recursive procedure. We
set ${\mathcal{P}}_{\text{root}(T)}=\delta$. Recursively we define the
precision score of a node $v$ by

${\mathcal{P}}_{v}=\mathbf{Z}_{v}\cdot{\mathcal{P}}_{\operatorname{parent}(v)}\text{
where
}\mathbf{Z}_{v}\sim_{i.i.d.}\operatorname{\mathtt{Uniform}}(\\{1,2,3,\ldots,\beta/4\\})\
.$ (1)

Most importantly, for a node $v$, we recurse into its children only if
${\mathcal{P}}_{v}\leq 1$; otherwise we stop the recursion for $v$ with
${\mathcal{P}}_{v}>1$ ($v$ has 0 children). If $v$ is a leaf (at level
$\ell$), with the associated integer $i\in[n]$, then we sample the
corresponding element $e_{i}$ of the input string $e$. One should think of the
“precision score” ${\mathcal{P}}_{v}$ of some internal node $v$ as the degree
to which the sub-tree rooted at $v$ is sampled: the lower ${\mathcal{P}}_{v}$,
the higher precision and the amount at which the sub-tree is sampled. One can
prove that the sample complexity (into $y$) is bounded by
$1/\delta\cdot\log^{O(\log_{\beta}n)}(\beta)$ (see Lemma 5.1).

At the beginning, we generate one such tree $T_{1/c}(y)$ for the input string
$y\in{\mathbb{N}}^{n}$, where $\delta=1/c$ for some $c=c(n,\lambda)\geq 1$
that we refer to as the “precision tree complexity”. After obtaining these
samples, the rest of the algorithm has no further access to $y$, and hence the
sampling is non-adaptive. Most importantly, using this single tree
$T_{1/c}(y)$, we will simulate Precision-Tree access for different trees over
different inputs and parameters in our algorithms using a certain procedure
which we call the Trim-Tree algorithm (see Algorithm 2).

We preprocess the sampled positions so that we can quickly retrieve all
samples in some $x$-interval $X\subseteq[n]$ and some $y$-interval $Y$ through
an ancillary data-structure which we call SODS. The SODS is used for a
“rejection sampling”-type operations where we need a number of samples from a
substring of input $y$ (or later on for some intervals of blocks), but care
only about values in a certain range $Y$. Below, we abuse notation to use $T$
to denote both the conceptual Precision-Tree and the data structure
implementing it. The resulting preprocessing time and space is
$O^{*}(1/\lambda)$.333The notation $O^{*}(\cdot)$ hides a $n^{o(1)}$ factor.

##  4 Main Algorithm for Estimating LIS

Our main algorithm is composed of two algorithms, for solving Block-LIS and
Genuine-LIS. These algorithms recursively call each other, with access to a
Precision-Tree data structure. This data structure queries the input sequence
at the beginning (non-adaptively and non-uniformly), and our algorithms access
the sequence only via this data structure. We describe the details of
Precision-Tree in Section 5, and for now refer to it as a tree
$T_{\lambda}(y)$ for some parameter $\lambda<1$ and an input string $y$.

We now state the main guarantees of the two algorithms, whose descriptions and
proofs will appear in later sections. The statements below are built to
support mutual recursion and might be challenging to parse at first read. At
high-level, the idea is to create mutual inductive hypotheses which can be
instantiated with different parameters, in a way that enables concurrent
optimization of the approximation, sample complexity and run-time complexity.
We then show how careful recursive instantiations of these two algorithms
yield our main algorithm for estimating LIS.

Below, for an instance $g\in({\mathbb{N}}\times\\{0,1\\})^{n\times k}$, let
$g$ restricted to first/second coordinate be $g(*)_{1}\in{\mathbb{N}}^{n\times
k}$ and $g(*)_{2}\in\\{0,1\\}^{n\times k}$ respectively.

######  Theorem 4.1 (EstimateGenuineLIS algorithm; Section 6).

Fix integers $n,k$ and $\lambda\in(1/n,1)$. Fix an instance
$g\in({\mathbb{N}}\times\\{0,1\\})^{n\times k}$. For some monotone functions
$a_{s}:{\mathbb{R}}^{3}_{+}\rightarrow[1,\infty)$ and
$c_{s}:{\mathbb{R}}_{+}^{4}\rightarrow[1,\infty)$, suppose there exists a
randomized algorithm $\mathcal{A}_{BL}$ that, given
$X\subseteq[n],Y\subseteq{\mathbb{N}}$, parameter $\tau_{s}$, and a Precision-
Tree
$T_{1/c_{s}\left(|X|,\tau_{s},\lambda,\tfrac{\lambda\cdot|X|}{|y(X,Y)|}\right)}(y)$
for some $y\in{\mathbb{N}}^{n\times k}$, can produce an
$(\alpha_{s},\lambda|X|)$-approximation for ${\textsf{Block-LIS}}(y,X,Y)$
where
$\alpha_{s}=a_{s}\left(|X|,\tau_{s},\tfrac{\lambda\cdot|X|}{|y(X,Y)|}\right)$
w.h.p. in time $t_{s}$.

Fix any parameter $\gamma,\tau\geq 1$, and let
$c\geq\tilde{O}(1/\lambda)+c_{s}\left(n,\tau,\lambda,\gamma\lambda/k\right)$.
Then, there exists an algorithm $\mathcal{A}$, that, given free access to
$g(*)_{1}$ and Precision-Tree access to $g(*)_{2}$, $T_{1/c}(g(*)_{2})$,
produces a $\left(\alpha_{g},\lambda n\right)$-approximation for
$\textsf{Genuine-LIS}(g)$ w.h.p., where
$\alpha_{g}=\log(k/\lambda)\cdot\max\\{\gamma,a_{s}(n,\tau,\gamma\lambda/k)\\}$.
The algorithm $\mathcal{A}$ runs in time $\tilde{O}(nk)+O(t_{s})$.

######  Theorem 4.2 (EstimateBlockLIS algorithm; Section 7).

Fix monotone functions
$t_{s},a_{g}:{\mathbb{R}}_{+}^{2}\rightarrow[1,\infty)$,
$a_{s},c_{g}:{\mathbb{R}}_{+}^{3}\rightarrow[1,\infty)$ and
$c_{s}:{\mathbb{R}}_{+}^{4}\rightarrow[1,\infty)$, satisfying, for all
$r,\tau\in E_{\beta}$, $m\in{\mathbb{N}}$, $\lambda<1$,
$\lambda_{1},\lambda_{2}\in[\lambda,1]$, and $k^{\prime}\in[1,1/\lambda]$ with
$\lambda_{1}\lambda_{2}=\Omega(\lambda k^{\prime})$:

  * •

$a_{s}\left(r,\tau,\tfrac{\lambda}{m}\right)\geq\operatorname{polylog}\left(\frac{k}{\lambda}\right)\cdot
a_{g}\left(\tau,\frac{\lambda_{2}}{k^{\prime}}\right)\cdot
a_{s}\left(\frac{r}{\tau},\tau,\frac{\lambda_{1}}{m}\right)$;

  * •

$c_{s}\left(r,\tau,\lambda,\tfrac{\lambda}{m}\right)\geq\beta^{O(1)}\cdot\frac{\tau}{\lambda}+c_{g}(\tau,\lambda_{2},k^{\prime})\cdot
c_{s}\left(\frac{r}{\tau},\tau,\Theta(\lambda_{1}/k^{\prime}),\frac{\lambda_{1}}{m}\right)$;
and,

  * •

$t_{s}\left(r,\tau\right)\geq\log^{O(\log_{\beta}(\tau))}(\beta)\cdot
t_{s}\left(\tfrac{r}{\tau},\tau\right)$.

Suppose there exists and algorithm $\mathcal{A}_{GL}$ with the following
guarantee: given Genuine-LIS instance
$g\in({\mathbb{N}}\times\\{0,1\\})^{n_{g}\times k_{g}}$ with $\beta$-ary
Precision-Tree $T_{1/c_{g}(n_{g},\lambda_{g},k_{g})}(g(*)_{2})$ access,
$\mathcal{A}_{GL}$ outputs
$\left(a_{g}\left(n_{g},\tfrac{\lambda_{g}}{k_{g}}\right),\lambda_{g}n_{g}\right)$-approximation
to $\textsf{Genuine-LIS}(g)$ in time $\tilde{O}(n_{g}\cdot k_{g})$ w.h.p.

Now fix input $y\in{\mathbb{N}}^{n\times k}$, a block interval
$X\subseteq[n]$, value range interval $Y\subseteq{\mathbb{N}}$, parameters
$\lambda\in(0,1)$, $\beta\in{\mathbb{N}}$, $\tau\in E_{\beta}$. Then, given a
$\beta$-ary Precision-Tree $T_{1/c}(y)$, we can produce a
$(\alpha,\lambda|X|)$-approximation for ${\textsf{Block-LIS}}(y,X,Y)$ w.h.p.,
as long as $\alpha\geq
a_{s}\left(|X|,\tau,\tfrac{\lambda|X|}{|y(X,Y)|}\right)$ and $c\geq
c_{s}\left(|X|,\tau,\lambda,\tfrac{\lambda|X|}{|y(X,Y)|}\right)$.

The algorithm’s expected run-time is at most $c\cdot
t_{s}(|X|,\tau)\cdot\tfrac{|y(X,Y)|}{|X|}$.

The proofs are deferred to Section 6 and Section 7. Combining the two
algorithms from above, we obtain the following theorem.

######  Theorem 4.3.

Fix any $\lambda=o(1)$ and $\epsilon<1$. There exists a randomized non-
adaptive algorithm that solves the LIS problem with $(\alpha,\lambda
n)$-approximation, where $\alpha=(1/\lambda)^{\sqrt{\epsilon}}\cdot(\log
1/\lambda)^{2^{O(\log^{2}(1/\epsilon)/\sqrt{\epsilon})}}$ using
$\tfrac{1}{\lambda}\cdot n^{O(\sqrt{\epsilon}\log 1/\epsilon)}$ time (and
hence samples from the input).

The algorithm for Theorem 4.3 (see Algorithm 1) follows the outline from
Figure 1. In particular, we first build a $\beta$-ary precision tree $T_{1/c}$
for $\beta=\Theta(\log n)$, and
$c=c_{s}(n,n^{\epsilon},\lambda,\lambda)=\tfrac{1}{\lambda}\cdot
n^{O(\sqrt{\epsilon}\log 1/\epsilon)}$. We then apply the algorithm of Theorem
4.2 by interpreting the string as a Block-LIS instance with $k=1$. The proof
follows from recursive implementation of Theorems 4.1 and 4.2 with carefully
chosen parameters. Most importantly $\tau$ and $\gamma$ are carefully chosen,
as a function of the other parameters, to balance approximation and
complexity. Informally, we pick $\tau\approx|X|^{\epsilon}$ in each Block-LIS
instance, and $\gamma\approx(k/\lambda)^{\sqrt{\epsilon}}$ for a recursion of
depth $\approx 1/\sqrt{\epsilon}$, then we stop and use the dense estimator
only by setting $\gamma$ to be maximal. The formal proof involves tedious
calculations, and is deferred to Appendix A. We now complete Theorem 1.1, by
instantiating the LIS problem with the parameters above set suitably.

Input: A sequence $y\in{\mathbb{N}}^{n}$, error parameter $\lambda\in(1/n,1)$,
and $\epsilon<1$.

Output: An integer $\widehat{L}\in\left[0,\textsc{LIS}(y)\right]$.

1 $T\leftarrow\textsc{PreprocessPrecisionTree}(y,\lambda\cdot
n^{-\epsilon},\beta)$, where $\beta\leftarrow\Theta(\log n)$.

return
$\widehat{L}\leftarrow\textsc{EstimateBlockLIS}(T,n^{\epsilon},\lambda)$.

Algorithm 1 EstimateLISMain Figure 2: Description of the algorithm
EstimateLISMain.

###### Proof of Theorem 1.1.

Let $y\in{\mathbb{N}}^{n}$ be an input of the LIS problem. We solve the
problem using the algorithm of Theorem 4.3 with inputs $y,\lambda$, and
$\epsilon=1/\log\log 1/\lambda$, noting that $\alpha=\lambda^{o(1)}$ and
runtime complexity is $\tfrac{1}{\lambda}n^{O(1/\sqrt[3]{\log\log
1/\lambda})}=\tfrac{1}{\lambda}n^{o(1)}$. Finally, we invoke 2.3 with $q=o(1)$
to obtain the claimed approximation (as $q=o(1)$, $p=q/(1-q)=o(1)$).∎

##  5 Precision-Tree Data Structure

In this section we present the Precision-Tree data structure used to improve
our bounds, and establish the properties of this data structure. In
particular, we describe how to decompose the tree so that we can run various
sampling-based algorithms on sub-trees of the tree, and recompose these
results using yet another sampling-based algorithm.

The basic construction of the $\beta$-ary tree $T_{\delta}(e)$ was introduced
in Section 3.5.1. In particular, each node $v$ has a precision score
${\mathcal{P}}_{v}$, defined as follows. For the root, we define
${\mathcal{P}}_{\text{root}(T)}=\delta$. The precision score of a node $v$ is
defined recursively as a function of the parent:

${\mathcal{P}}_{v}=\mathbf{Z}_{v}\cdot{\mathcal{P}}_{\operatorname{parent}(v)}\text{
where
}\mathbf{Z}_{v}\sim_{i.i.d.}\operatorname{\mathtt{Uniform}}(\\{1,2,3,\ldots,\beta/4\\})\
.$ (2)

For a node $v$, we recurse into its children only if ${\mathcal{P}}_{v}\leq
1$; otherwise we stop the recursion for $v$ with ${\mathcal{P}}_{v}>1$ (i.e.,
$v$ has 0 children in the precision tree). If $v$ is a leaf, with the
associated integer $i\in[n]$, then we sample the corresponding element $e_{i}$
of the input string $e$.

We first establish the sample complexity of the Precision-Tree. In the below,
we use $V_{\ell}$ to denote the set of nodes at level $\ell$.

######  Lemma 5.1 (Sample complexity).

The expected number of coordinates in $[n]$ that are sampled is
$\tfrac{O(\log\beta)^{\log_{\beta}n}}{\delta}$.

###### Proof.

Let $s_{v}=1/\mathcal{P}_{v}$. Since we only sample leaves with $s_{v}\geq 1$,
then the total sampled leaves is at most $\sum_{v\in
V_{\log_{\beta}(n)}}s_{v}$.

Now, since $\mathbf{Z}_{v}$ are chosen i.i.d. uniformly in
$\\{1,\ldots,\Omega(\beta)\\}$, then we deduce the recursive relation:

$\operatorname{{\mathbb{E}}}[s_{v}]\leq\operatorname{{\mathbb{E}}}\left[\tfrac{1}{\mathcal{P}_{v}}\right]=\tfrac{O(\log\beta)}{\beta}\cdot\operatorname{{\mathbb{E}}}\left[\tfrac{1}{\mathcal{P}_{\operatorname{parent}(v)}}\right]$
(3)

Let $\tau_{\ell}\triangleq\sum_{v\in V_{\ell}}s_{v}$. Then
$\tau_{0}=1/\delta$, and for level $\ell$, summing and using Equation 3, we
obtain

$\operatorname{{\mathbb{E}}}\left[\tau_{\ell}\right]=\operatorname{{\mathbb{E}}}\left[\sum_{v\in
V_{\ell}}s_{v}\right]\leq\beta\cdot\operatorname{{\mathbb{E}}}\left[\sum_{v\in
V_{\ell-1}}\tfrac{O(\log\beta)}{\beta}\cdot s_{v}\right]\leq
O(\log\beta)\operatorname{{\mathbb{E}}}\left[\sum_{v\in
V_{\ell-1}}s_{v}\right]=O(\log\beta)\tau_{\ell-1}.$

Then $\operatorname{{\mathbb{E}}}[\tau_{\ell}]\leq
O(\log\beta)^{\ell}/\delta$, and we conclude
$\operatorname{{\mathbb{E}}}\left[\sum_{v\in
V_{\log_{\beta}(n)}}s_{v}\right]=O(\log(\beta))^{\log_{\beta}n}/\delta$ as
needed. ∎

###  5.1 Tree Sampling Data Structure

We equip the Precision-Tree with a Sampling Oracle Data Structure (denoted
SODS) that should be seen as a data structure wrapper with access to
Precision-Tree, allowing efficient sampling of leaves.

First, we show one can simulate uniform samples of elements given a Precision-
Tree access.

######  Lemma 5.2 (Simulating Random Samples).

Fix $\delta\leq 1$ and Precision-Tree $T=T_{\delta}(e_{1},\ldots,e_{n})$, as
well as arbitrary $\delta^{\prime}\geq\delta$, with
$1/\delta^{\prime}\in{\mathbb{N}}$. Using access to $T$ only, we can generate
a set of elements $S\subseteq\\{e_{1},\ldots,e_{n}\\}$ such that the
distribution of $S$ is identical to the distribution where each $e_{i}$ is
included i.i.d. with probability $1/\delta^{\prime}n$. The runtime to generate
$S$ is $O(\log\beta)^{\log_{\beta}n}/\delta$.

We remark that, while two subsequent invocations of the above lemma may give
different sets $S,S^{\prime}$, each with the above distribution, they are
dependent between each other.

###### Proof.

The main task here is to show independence, i.e., that we can choose a set of
i.i.d. samples by reusing the randomness of the Precision-Tree. We prove by
induction on the tree height, starting with single node trees, that for any
node with $\mathcal{P}_{v}\leq 1$, for any
$\delta^{\prime}\geq\mathcal{P}_{v}$ we can generate a subset of the leaves
where each leaf is included with probability at least
$1/\delta^{\prime}n_{v}$, where $n_{v}$ to be the number of leaves in the
subtree rooted at $v$.

For leaves, if $\mathcal{P}_{v}\leq 1$, the node is included in the Precision-
Tree, and we can subsample it with any required probability as needed. Now
consider a non-leaf node $v$; by induction the statement holds for its
children.

If $\delta^{\prime}\leq\tfrac{4}{\beta}$, we are basically done since any
child $u$ of $v$, has score
$\mathcal{P}_{u}\leq\tfrac{\mathcal{P}_{v}\beta}{4}\leq\tfrac{\delta^{\prime}\beta}{4}\leq
1$, while the number of elements $n_{u}=\tfrac{n_{v}}{\beta}$, so we can
simply subsample leaves in $u$’s tree, each with probability
$\tfrac{1}{\delta^{\prime}n_{v}}=\tfrac{1}{\delta^{\prime}\beta
n_{u}}\leq\tfrac{1}{\mathcal{P}_{u}n_{u}}$ as needed (note that
$\delta^{\prime}n_{v}/n_{u}=\beta\delta^{\prime}\geq\mathcal{P}_{u}$ as
required by the inductive hypothesis).

It remains to show this for $\delta^{\prime}>\tfrac{4}{\beta}$. For this case
we claim we would like to use the tree-randomness to generate the samples.

For distributions $P,Q$, we say that $P$ stochastically dominates $Q$ (also
denoted $P\succ Q$) if $\mathcal{F}_{P}(t)\leq\mathcal{F}_{Q}(t)$ for all $t$,
with strict inequality for some $t$, where $\mathcal{F}_{P}$ and
$\mathcal{F}_{Q}$ are the cumulative distribution functions (CDFs) of $P$ and
$Q$ respectively. We first claim the following:

######  Claim 5.3.

Fix $k\in{\mathbb{N}}$, $0<p<1$ and $F\geq 1$ such that $F\cdot pk<1/4$. Let
$\mathbf{X}_{1},\ldots,\mathbf{X}_{k}\sim_{i.i.d.}\operatorname{\mathtt{Ber}}(p)$
(i.e., i.i.d. Bernoulli random variables with bias $p$) and let
$\mathbf{X}=\sum_{i}\mathbf{X}_{i}$. Let
$\mathbf{Y}_{1},\ldots,\mathbf{Y}_{k}\sim_{i.i.d.}\operatorname{\mathtt{Ber}}(2\,p\,F)$
and let $\mathbf{Y}=\mathbf{Y}^{*}\cdot\sum_{i}\mathbf{Y}_{i}$ where
$\mathbf{Y}^{*}\sim\operatorname{\mathtt{Ber}}(1/F)$, independent of the other
variables. Then, $\mathbf{Y}$ stochastically dominates $\mathbf{X}$.

###### Proof.

$\mathbf{X}$ and $\mathbf{Y}$ are both supported on $\\{0,1,\cdots,k\\}$. So,
it suffices to show that $\Pr[\mathbf{Y}\geq i]>\Pr[\mathbf{X}\geq i]$ for all
$i\in[k]$. Note that $2pF\leq 2pFk<1/2$, so $2pF$ is a valid probability. For
$i\in[k]$, let

$f(i):=\frac{\Pr[\mathbf{Y}=i]}{\Pr[\mathbf{X}=i]}=\frac{\binom{k}{i}\cdot(2\,p\,F)^{i}\cdot(1-2\,p\,F)^{k-i}}{F\cdot\binom{k}{i}\cdot
p^{i}\cdot(1-p)^{k-i}}=2^{i}\cdot
F^{i-1}\cdot\left(\frac{1-2\,p\,F}{1-p}\right)^{k-i}.$

To show that $\Pr[\mathbf{Y}\geq i]>\Pr[\mathbf{X}\geq i]$ for all $i\in[k]$,
it suffices to show that $f(i)>1$ for all $i\in[k]$. Using the conditions that
$2pF<1/2$, $pFk<1/4$ and $F\geq 1$, along with the fact that $1-x\geq 2^{-2x}$
for all $x\in[0,1/2]$, we obtain:

$f(i)>2(1-2\,p\,F)^{k}\geq 2\cdot 2^{-4pFk}>2\cdot 2^{-1}=1,$

for all $i\in[k]$. This concludes the proof. ∎

We show that one can simulate sub-sampling of each leaf of $u$ i.i.d. with
probability $1/\delta^{\prime}n_{v}$ by the following process. If
$\mathcal{P}_{u}>1$, then output no elements. Otherwise, we can (by the
inductive hypothesis) sub-sample each leaf of $u$ i.i.d. with probability
$1/n_{u}$.

Now, let

$F\triangleq\tfrac{1}{\left\lfloor
1/\delta^{\prime}\right\rfloor}\tfrac{\beta}{4}\geq\tfrac{1}{\left\lfloor
1/\mathcal{P}_{v}\right\rfloor}\tfrac{\beta}{4}\stackrel{{\scriptstyle
Eq.~{}\ref{eq:precision-tree}}}{{\geq}}\tfrac{1}{\Pr_{T}[\mathcal{P}_{u}\leq
1]}.$

This process generates $\mu$ i.i.d. leaves of $u$ with distribution

$\mu\sim\operatorname{\mathtt{Ber}}(\Pr_{T}[\mathcal{P}_{u}\leq
1])\cdot\sum_{l\text{ leaf of
}u}\operatorname{\mathtt{Ber}}(\tfrac{1}{n_{u}})\succ\operatorname{\mathtt{Ber}}(\tfrac{1}{F})\cdot\sum_{l\text{
leaf of }u}\operatorname{\mathtt{Ber}}(\tfrac{1}{n_{u}}).$

Noting that $n_{u}=\tfrac{n_{v}}{\beta}\geq\tfrac{\delta^{\prime}n_{v}}{2F}$
and $\tfrac{n_{u}F}{\delta^{\prime}n_{v}}\leq\tfrac{1}{4}$, we invoke 5.3 to
obtain that the distribution $\mu$ stochastically dominates the required
sample-size distribution $\sum_{l\text{ leaf of
}u}\operatorname{\mathtt{Ber}}(\tfrac{1}{\delta^{\prime}n_{v}})$, and hence we
can simulate the distribution we need over leaves of each child, and hence
also for $v$.

For run-time, we note that this process takes time (at most) proportional to
the size of the tree. For the latter, by Lemma 5.1, the time is
$O(\log\beta)^{\log_{\beta}n}/\delta$.

∎

Next, we show that if each element of the tree is a block of integers, then
one can construct a data structure that sub-samples with interval range
restriction, in time proportional to the sample size.

######  Corollary 5.4 (Conditional sub-sampling data structure).

Fix Precision-Tree $T=T_{\delta}(y)$ with $y\in{\mathbb{N}}^{n\times k}$.
There exists a data structure, that given any interval $Y\in\mathcal{I}$ and
sub-sampling probability $\eta\leq 1/\delta n$ with $1/\eta\in E_{2}(n)$, sub-
sample block-coordinates $X^{\prime}\subseteq[n]$ i.i.d. with probability
$\eta$ and outputs a set of all coordinates $W\subseteq X^{\prime}\times[k]$
such that $y_{W}\in Y$, i.e. $W\triangleq\cup_{i\in X^{\prime}}\\{(i,j)\mid
y_{i,j}\in Y\\}$, in time $\tilde{O}(|W|)$. The preprocessing time is, in
expectation, $\tilde{O}\left(\tfrac{n+\left\lVert m\right\rVert_{1}}{\delta
n}\right)$, where $m_{i}\leq k$ is the number of non-null elements in $y_{i}$.

###### Proof.

To preprocess, we prepare for each possible $\eta\leq 1/\delta n$ with
$1/\eta\in E_{2}(n)$ by sub-sampling each block i.i.d. with probability $\eta$
using Lemma 5.2. Then we compute a set of coordinates $Z_{\eta}\subset[n]$ by
combining all coordinates from all sampled blocks. Let
$U_{\eta}\triangleq\cup_{w\in Z_{\eta}\times[k]}\\{y_{w}\\}$. Compute
$U_{\eta}$ and store it as a sorted array with a pointer to
$y^{-1}(j)\cap(Z_{\eta}\times[k])$ for each $j\in U_{\eta}$. Now, for each
$(\eta,Y)$ query, locate the range of elements in $U_{\eta}$ containing
precisely the elements in $Y$ using binary search of $\min(Y),\max(Y)$. This
will be our output $W$.

The correctness follows immediately from the construction. Preprocessing
runtime is as claimed as, in expectation, we need to sort $\|m\|_{1}/\delta n$
elements, and there are $O(\log n)$ different values of $\eta$ to consider.
Runtime is only $O(\log n)$ plus the size of the output (as it is stored as
contiguous block). ∎

###  5.2 Decomposing Precision-Tree

We now show how to use the Precision-Tree for recursive sampling-based
algorithms via decomposing the tree. In particular, consider the setting where
a top-level/global algorithm decomposes the input string into intervals, and
recurses on a sample of these intervals to solve a “local” problem on each. If
one can compute a local function over each such (sampled) interval given a
local Precision-Tree access to such an interval, then we can solve the overall
problem by recasting the overall precision tree as a small global precision
tree where each leaf is a precision tree by itself. One can observe we can do
this for any size intervals, as long as the precision score of local tree
$\eta$ and precision score of global tree $\delta$ are such that the original
tree has precision score $\eta\delta$ (i.e., it is $T_{<\eta\delta}$).

The algorithm follows the following steps (the full algorithm is described in
Algorithm 2):

  1. 1.

Identify the “correct” level $\ell$ in $T$ where each node corresponds to the
right number of elements.

  2. 2.

Find all nodes $v$ at level $\ell$ with enough precision to compute the local
function $f_{v}$ and compute the local function on these nodes by “detaching”
the sub-trees rooted at each $v$.

  3. 3.

Consider the global tree $T$, trimmed to levels $\leq\ell$ (i.e., the top of
the tree). Augment the precision parameters by dividing each score with the
precision we need to use for the local computation. This creates another
“simulated” precision tree where we have access to the value at all leaves
with $\mathcal{P}_{v}\leq 1$.

  4. 4.

Compute the global function $g$ with tree access to the locally computable
values.

Overall, we constructively show the following. Below, we assume that $n$ is an
integral power of $\beta$, but the results extend to general tree sizes (for
example by padding the input).

######  Lemma 5.5 (Tree Decomposition).

Fix $\beta,\tau,n\in{\mathbb{N}}$ such that $n,\tau$ are each a power of
$\beta$. Fix a domain of elements
$e\triangleq\\{e_{1},\ldots,e_{n}\\}\in\mathcal{E}^{n}$ and let
$X_{1},\ldots,X_{\tau}$ be a partition of $[n]$ into disjoint intervals of
equal width. Fix $\delta,\eta\in(0,1)$ and (possibly randomized) functions
$g:T_{\delta}(\mathcal{F}^{\tau})\rightarrow\mathcal{G}$ and
$\\{f_{i}:T_{\eta}(e(X_{i}))\rightarrow\mathcal{F}\\}_{i\in[\tau]}$ for some
spaces $\mathcal{G}$ and $\mathcal{F}$. Then, algorithm TrimTree (see
Algorithm 2), given a Precision-Tree $T_{\delta\eta}(e)$, outputs
$g(T_{\delta}(f_{1}(T_{\eta}(e(X_{1}))),\ldots,f_{\tau}(T_{\eta}(e(X_{\tau})))))$.
The algorithm’s expected run-time is
$\tilde{O}(\tau+t_{g}+\tfrac{1}{\delta\tau}\cdot\left\lVert
t_{f}\right\rVert_{1}\cdot\log^{O(\log_{\beta}(\tau)}(\beta))$, where $t_{g}$
is the time to compute $g$, and $(t_{f})_{i}$ is the expected time to compute
$f_{i}$.

###### Proof of Lemma 5.5.

Consider the full Precision-Tree $T_{\delta\eta}(e)$. Take the top
$\log_{\beta}\tau$ levels of the tree to get to the level where each node $v$
has $n/\tau$ leaves in its subtree. This top portion (trimmed tree) can be
seen as $T_{\delta}$ as follows: the precision ${\mathcal{P}}^{\prime}_{v}$ in
$T_{\delta}$ is simply defined to be ${\mathcal{P}}_{v}/\eta$. Hence for leaf
$v$ in $T_{\delta}$, we have that ${\mathcal{P}}^{\prime}_{v}\leq 1$ iff
${\mathcal{P}}_{v}\leq\eta$. Hence for each such $v$, if
${\mathcal{P}}^{\prime}_{v}\leq 1$, we have another $T_{\eta}$ rooted at $v$
(in the full Precision-Tree), allowing us to compute the corresponding
$f_{i}(T_{\eta}(e(X_{i})))$. Hence we will be able to also compute
$g(T_{\delta}(f_{1}(T_{\eta}(e(X_{1}))),\ldots,f_{\tau}(T_{\eta}(e(X_{\tau})))))$
as required.

For runtime, we note that by Lemma 5.1, we have
$\tfrac{1}{\delta}\cdot\log^{O(\log_{\beta}(\tau)}(\beta)$ leaves $v$ with
$\mathcal{P}_{v}^{\prime}\leq 1$. We only preprocess SODS and compute the
function $f_{i}$ on those leaves, and all $f_{i}$ have the same probability to
be computed. Also, we note from the independence of $\mathbf{Z}_{i}$’s, once
we fix precision parameter $\eta$, the time to compute each
$f_{i}(T_{\eta}(e(X_{i})))$ is independent of the random choice of $i$ where
$f_{i}$ is computed, hence we have the expected runtime is the product of
expectations. Finally, computing the function $g$ takes $t_{g}$ time.

∎

Input: Disjoint consecutive intervals of $[n]$: $\\{X_{i}\\}_{i\in[\tau]}$ of
length $r$ each, global function
$g:T_{\delta}(\mathcal{F}^{\tau})\rightarrow\mathcal{G}$, functions
$\\{f_{i}:T_{\eta}(e(X_{i}))\rightarrow\mathcal{F}\\}_{i\in[\tau]}$,
Precision-Tree $T$, local precision parameter $\eta$.

Output: $g([f_{i}(T_{\eta}(e(X_{i})))]_{i\in[\tau]})$

1 Let $\ell=\log_{\beta}\tau$ be the level in $T$ such that for $v\in
V_{\ell}$, $|X_{v}|=r$.

2

3$T_{g}\leftarrow$ the induced sub-tree of $V_{\leq\ell}$.

4 for  _${v\in V_{\ell}}$_ do

5 if  _$\mathcal{P}_{v}\leq\eta$_ then

6 Preprocess SODS for the precision tree rooted at $v$ using Corollary 5.4.

7 Compute $f_{i}(T_{\eta}(e(X_{i})))$ using the sub-tree rooted at $v$ and
store the result in $v$.

8

9$\mathcal{P}_{v}\leftarrow\mathcal{P}_{v}/\eta$ for all $v\in T_{g}$.

10 Preprocess SODS for $T_{g}$ using Corollary 5.4.

11 Compute $q\leftarrow g([f_{i}(T_{\eta}(e(X_{i}))]_{i\in[\tau]})$ using
$T_{g}$.

return $q$.

Algorithm 2 TrimTree Figure 3: Algorithm TrimTree for decomposing Precision-
Tree (Lemma 5.5). Define level $\ell_{v}$ of a node $v$ as its distance to the
root. We define $V_{\ell}$ as the set of nodes of level $\ell$, i.e.,
$V_{\ell}\triangleq\\{v\in T\mid\ell_{v}=\ell\\}$. We use the shorthand
$V_{\leq\ell}\triangleq\cup_{m\leq\ell}V_{m}$ and similarly for
$V_{<\ell},V_{>\ell},V_{\geq\ell}$.

Input: An input $e\in\mathcal{E}^{n}$, precision parameter $\delta$, and
branching parameter $\beta\in{\mathbb{N}}$.

Output: Precision-Tree data-structure $T_{\delta}(e)$.

1 $T\leftarrow\textsc{PreprocessNode}(e,[|e|],\delta,\beta)$.

2 Preprocess SODS for $T$ using Corollary 5.4.

return $T$.

Algorithm 3 PreprocessPrecisionTree

Input: An input $e\in\mathcal{E}^{n}$, an interval $I\subseteq[|e|]$,
precision parameter $\delta$, and branching parameter $\beta\in{\mathbb{N}}$.

Output: Precision-Tree data-structure $T_{\delta}(e)$.

1 $v\leftarrow$ a new node associated with $e_{I}$.

2 if  _$\delta\leq 1$_ then

3 if  _$|I|=1$_ then

4 Store $e_{I}$ in $v$.

5 else

6 $I_{1},\ldots,I_{\beta}\leftarrow$ a partition of $I$ into $\beta$ disjoint,
equal length intervals.

7 for  _$i\in[\beta]$_ do

8
$\mathbf{Z}_{i}\sim\operatorname{\mathtt{Uniform}}(\\{1,2,3,\ldots,\beta/4\\})$.

9 $\mathcal{P}_{i}\leftarrow\delta\cdot\mathbf{Z}_{i}$.

10 $u_{i}\leftarrow\textsc{PreprocessNode}(e,I_{i},\mathcal{P}_{i},\beta)$.

11 Add $u_{i}$ as a child of $v$.

12

13

return $v$.

Algorithm 4 PreprocessNode

Figure 4: Description of the algorithm PreprocessPrecisionTree.

##  6 Algorithm for Genuine-LIS: Proof of Theorem 4.1

In this section we describe and analyze the algorithm for the Genuine-LIS
problem, which is called EstimateGenuineLIS.

First, we introduce an extension to the Block-LIS algorithm, which we use for
our algorithm. In particular, we allow it to ignore a few “heavy blocks” which
will not affect the approximation or complexity guarantees of Theorem 4.1. We
use the following definition:

######  Definition 6.1.

Fix block sequence $y\in{\mathbb{N}}^{X\times[k]}$, parameter $\delta<1$ and
value range interval $Y\in\mathcal{I}$. Let $X^{\delta}$ be the $\delta|X|$
blocks in $X$ for which the quantity $|y(X^{\delta})\cap Y|$ is maximized. The
_$\delta$ -heavy trimmed input_ $y_{-\delta,Y}\in{\mathbb{N}}^{X\times[k]}$ is
$y$ after setting $y_{-\delta,Y}(X^{\delta})=\emptyset$ (i.e., removing all
integers from $y(X^{\delta})$).

For $X^{\prime}\subseteq X$ and a range of $y$-values $Y^{\prime}$, we also
define $y_{-\delta}(X^{\prime},Y^{\prime})\triangleq
y(X^{\prime})_{-\delta,Y^{\prime}}\cap Y^{\prime}$ (i.e., the multiset of
values in $y(X^{\prime})_{-\delta,Y^{\prime}}$ restricted to $Y^{\prime}$).

The stronger version of Theorem 4.1 is as follows:

######  Lemma 6.2 (EstimateGenuineLIS algorithm, extended).

Fix integers $n,k$ and $\lambda\in(1/n,1)$. Fix an instance
$g\in({\mathbb{N}}\times\\{0,1\\})^{n\times k}$. For some monotone functions
$a_{s}:{\mathbb{R}}^{3}_{+}\rightarrow[1,\infty)$ and
$c_{s}:{\mathbb{R}}_{+}^{4}\rightarrow[1,\infty)$, suppose there exists a
randomized algorithm $\mathcal{A}_{BL}$ that, given
$X\subseteq[n],Y\subseteq{\mathbb{N}}$, parameter $\tau_{s}$, and a Precision-
Tree
$T_{1/c_{s}\left(|X|,\tau_{s},\lambda,\tfrac{\lambda\cdot|X|}{|y_{-\lambda/2}(X,Y)|}\right)}(y)$
for some $y\in{\mathbb{N}}^{n\times k}$, can produce an
$(\alpha_{s},\lambda|X|)$-approximation for ${\textsf{Block-LIS}}(y,X,Y)$
where
$\alpha_{s}=a_{s}\left(|X|,\tau_{s},\tfrac{\lambda\cdot|X|}{|y_{-\lambda/2}(X,Y)|}\right)$
in time $t_{s}$, w.h.p.

Fix any parameter $\gamma,\tau\geq 1$. Then, there exists an algorithm
$\mathcal{A}$ that, given complete direct access to
$g(*)_{1}\in{\mathbb{N}}^{n\times k}$ and Precision-Tree access to
$g(*)_{2}\in\\{0,1\\}^{n\times k}$, termed $T_{1/c}(g(*)_{2})$, produces a
$\left(\alpha_{g},\lambda n\right)$-approximation for $\textsf{Genuine-
LIS}(g)$ w.h.p., where
$c\geq\tilde{O}(1/\lambda)+c_{s}\left(n,\tau,\lambda,\gamma\lambda/k\right)$
and
$\alpha_{g}=\log(k/\lambda)\cdot\max\\{\gamma,a_{s}(n,\tau,\gamma\lambda/k)\\}$.
The algorithm $\mathcal{A}$ runs in time $\tilde{O}(nk)+O(t_{s})$.

To prove Lemma 6.2, we use the following reduction:

######  Lemma 6.3.

Suppose there exists an algorithm $\mathcal{A}$ that
$\left(a\left(\tfrac{\lambda|X|}{|y(X,Y)|}\right),\lambda
n\right)$-approximates Block-LIS w.h.p. given tree access $T_{1/c}(g)$, in
time $t=t\left(\tfrac{\lambda|X|}{|y(X,Y)|}\right)$, where
$c=c\left(\tfrac{\lambda|X|}{|y(X,Y)|}\right)$ and $a,c,t$ are some functions.
Then there exists an algorithm $\mathcal{A}^{\prime}$ that
$\left(O\left(a\left(\tfrac{\lambda|X|}{|y_{-\lambda/2}(X,Y)|}\right)\right),\lambda
n\right)$-approximates Block-LIS with tree access
$T_{1/c\left(\tfrac{\lambda|X|}{|y_{-\lambda/2}(X,Y)|}\right)}$ in time
$O(t)+\tilde{O}(1/\lambda)$ w.h.p.

The proof of Lemma 6.3 is deferred to Section 8.

###### Proof of Theorem 4.1 using Lemmas 6.2 and 6.3.

The proof is immediate since the extended algorithm assumed in Lemma 6.2
reduces to the standard versions using Lemma 6.3. ∎

The rest of this section is devoted to prove Lemma 6.2.

###  6.1 Algorithm Description

The algorithm EstimateGenuineLIS is presented in Algorithm 5. It consists of
the following high-level steps. First, we perform some preprocessing by
extracting pseudo-solutions, longest increasing subsequences, ignoring the
genuineness flags. Then we partition these sequences according to their
lengths. Next we estimate the proportion of genuine elements amongst the union
of above subsequences; this gives our first (dense) estimator. We also employ
a second (sparse) estimator, when the proportion of genuine elements is too
low, to reduce the instance to Block-LIS with improved parameters. We now
describe these steps in detail.

####  6.1.1 Extracting pseudo-solutions

For this step, we treat all elements the same, whether they are genuine or
not, and greedily compute and extract disjoint increasing subsequences, each
of length $\gtrapprox\lambda n$, denoted $\\{P_{i}\\}_{i}$ (which are called
pseudo-solutions), until there is no longer an increasing subsequence of
length $\lambda n$ remaining. For reasons that will become clear later, we
also need to guarantee that each time we extract a sequence, such a sequence
is approximately proportional to the longest one at that time, i.e., after
removing all previous sequences, and therefore we use a greedy algorithm.

We note that we cannot afford to use the standard dynamic-programming solution
for finding an optimal LIS each time, as the resulting runtime is too large
for us. To improve the runtime, we use instead a fast data-structure for
approximate greedy extraction, based on the fully dynamic data-structure in
[GJ21a].

######  Theorem 6.4.

[GJ21a] Given an input $x\in{\mathbb{N}}^{n}$, for any $\epsilon>0$, there
exists a dynamic data-structure $\mathcal{D}$ with the following operations:
1) inserting/deleting an element, in time $(\log n/\epsilon)^{O(1)}$, and 2)
finding an approximate longest increasing sub-sequence of length within
$(1+\epsilon)$-factor of the optimum, OPT, in time $O(|\textsf{OPT}|)$.

This theorem with $\epsilon=1$ leads to the following corollary for Block-LIS.

######  Corollary 6.5 (Extracting Pseudo-solution, approximate).

There exists a data-structure that given a sequence of integer blocks
$y\in{\mathbb{N}}^{n\times k}$, extracts (i.e., finds and removes) an
increasing sequence of length at least $|\textsf{OPT}|/2$, where OPT is the
current LIS. The pre-processing time is $\tilde{O}(n\cdot k)$.

###### Proof.

To preprocess the data-structure, we insert all elements to $\mathcal{D}$ one
by one, where elements of each block are inserted in non-increasing order.
This takes time $\tilde{O}(nk)$. Finally, we answer the extraction queries by
LIS-querying $\mathcal{D}$, and remove all elements in the $2$-approximate LIS
solution one by one from $\mathcal{D}$. ∎

####  6.1.2 Partitioning the pseudo-solutions

Next, we partition $\\{P_{i}\\}_{i}$ into $\log(1/\lambda)$ disjoint buckets
denoted $\\{\mathcal{P}_{\ell}\\}_{\ell}$, where for $\ell\in
E_{2}(1/\lambda)$, each $P\in\mathcal{P}_{\ell}$ is an increasing sub-sequence
of length $\approx\ell\lambda n$ (again, ignoring the genuineness of the
elements). Our algorithm generates an estimator for Genuine-LIS for each scale
$\ell$, based purely on the elements of the subsequences $\\{P\mid
P\in\mathcal{P}_{\ell}\\}$, and outputs the maximal estimator. Clearly, one of
the buckets must contain a significant fraction of the Genuine-LIS; we focus
on that bucket $\mathcal{P}_{\ell}$ henceforth.

####  6.1.3 Estimator Computation

We next describe our estimator for each bucket as above, which by itself is
generated by taking the maximum of 2 estimators, denoted Dense Estimator and
Sparse Estimator. The Dense Estimator is a fairly straightforward one. Here,
we consider the union of all pseudo-solutions
$U_{\ell}\triangleq\cup_{P\in\mathcal{P}_{\ell}}P$, and estimate the rate of
genuine elements in $U_{\ell}$ by checking the genuineness of a random sample
of elements in $U_{\ell}$. The dense estimator is then proportional to the
estimated rate of genuine elements in $U_{\ell}$. The main idea is that, if
$U_{\ell}$ has many genuine elements, then the aforementioned sampling
procedure gives a high-fidelity estimate.

The sparse estimator handles the opposite situation: when the genuine elements
are sparse within the union $U_{\ell}$ of subsequences. Then, if the Genuine-
LIS itself is quite large, it must be the case that a high fraction of the
genuine elements participate in the LIS. Here, we invoke the algorithm for
Block-LIS, restricted to genuine elements only. Using the fact that Block-LIS
approximation is a function of the proportion of LIS elements among all the
“relevant” elements (in this case, genuine elements), we make progress in the
sparse case by reducing the number of relevant elements, resulting in improved
approximation. The overall estimator for length $\ell$ is the maximum of the
$2$ estimators.

We highlight the fact that the sparse estimator calls the assumed algorithm
${\mathcal{A}_{\text{BL}}}$ on the input string $g$, restricted only to the
genuine elements. In this call, we do not compute the genuineness flags
explicitly, but rather compute them as needed, i.e., only for the elements
that are “read” by the ${\mathcal{A}_{\text{BL}}}$ algorithm, and if an
element turns out to be non-genuine it becomes a “null” entry. Since we are
using Precision-Tree to access samples, the algorithm will perform computation
in a different (but equivalent) order: first computing the genuineness of the
right samples, and then run the ${\mathcal{A}_{\text{BL}}}$ algorithm on those
samples.

Input: $g\in({\mathbb{N}}\times\\{0,1\\})^{n\times k},\lambda\in[1/n,1]$
Precision-Tree $T=T_{1/c}(g(*)_{2})$ for the parameter $c$ defined in Lemma
6.2.

Output: A number $\widehat{G}\in\left[0,n\right]$.

1

2Greedily and iteratively extract 2-approximate maximal increasing sequences
from $g(*)_{1}$, as long as they contain at least $\lambda n/4$ elements using
Corollary 6.5, generating pseudo-solutions $P_{1},\ldots,P_{t}$ for some
$t=O(k/\lambda)$, where each $P_{i}\subseteq[n]\times[k]$ is a set of
coordinates.

3

4Sample blocks $S\subseteq[n]$ i.i.d. with probability
$10\zeta\cdot\tfrac{1}{\lambda}\cdot\tfrac{1}{n}$ each, for $\zeta=O(\log n)$,
using Corollary 5.4 and $T$.

5 Compute $W\leftarrow\\{(i,j)\in S\times[k]\mid g(i,j)_{2}=1\\}$ the set of
genuine (sampled) coordinates.

6

7for  _$\ell\in E_{2}(4/\lambda)/4$_ do

8 Let
$\mathcal{P}_{\ell}\triangleq\\{P_{i}\,:\,|P_{i}|\in(\lambda\,n\,\ell/2,\lambda\,n\,\ell]\\}$,
and let $U_{\ell}\triangleq\cup_{P\in\mathcal{P}_{\ell}}P$.

9 Compute $B_{\ell}\subseteq S\leftarrow$ the $\zeta$ blocks in $S$ for which
$|(B_{\ell}\times[k])\cap W\cap U_{\ell}|$ is maximized.

10 $\kappa_{\ell}\leftarrow|W\cap U_{\ell}\cap((S\setminus
B_{\ell})\times[k])|$.

11

return
$\widehat{G}\triangleq\max_{\ell}\max\left\\{\tfrac{\lambda^{2}\,\ell\,n\,\kappa_{\ell}}{100\cdot
k\cdot\zeta}-\tfrac{\lambda
n}{4},{\mathcal{A}_{\text{BL}}}\left(g(*)_{1}\mid_{U_{\ell}\cap(g(*)_{2})^{-1}(1)},{\mathbb{N}},\lambda,T\right)\right\\}.$

Algorithm 5 EstimateGenuineLIS Figure 5: Description of the algorithm
EstimateGenuineLIS. $g(*)_{1}\mid_{U_{\ell}\cap(g(*)_{2})^{-1}(1)}$ denotes
the sequence $g(*)_{1}$ restricted to positions in $U_{\ell}$ for which
$g(\cdot)_{2}=1$. Recall that $E_{2}(k)\triangleq\left\\{2^{i}\mid
i\in\\{0,\ldots,\lfloor\log k\rfloor\\}\right\\}$. $\mathcal{A}_{BL}$ is the
assumed algorithm for Block-LIS.

###  6.2 Analysis

We now analyze the algorithm, proving Lemma 6.2.

###### Proof of Lemma 6.2.

Let OPT be the coordinates of an optimal solution of length $\textsf{Genuine-
LIS}(g)$. Let $U\triangleq\cup_{\ell}U_{\ell}$, and
$\overline{U}\triangleq[n]\times[k]\setminus U$. Define
${\widehat{\textsf{OPT}}}\triangleq\textsf{OPT}\cap U$ (i.e., restricted to
elements in $U$). Since $\overline{U}$ does not contain an increasing sequence
of length $\tfrac{1}{2}\lambda n$, we have that
$|{\widehat{\textsf{OPT}}}|\geq|\textsf{OPT}|-|\textsf{OPT}\cap\overline{U}|\geq|\textsf{OPT}|-\tfrac{1}{2}\lambda
n$. For $\ell\in E_{2}(4/\lambda)$, let us also define
${\widehat{\textsf{OPT}}}_{\ell}\triangleq\textsf{OPT}\cap U_{\ell}$.

To bound our estimators, we first bound the quantity $\kappa_{\ell}$. For this
task, we introduce more notation. Let $M\subset[n]$ be the $\lambda n/2$
blocks containing the highest number of genuine elements. We also define the
following:

$\displaystyle\widehat{\kappa_{\ell}}$ $\displaystyle\leftarrow|W\cap
U_{\ell}|.$ $\displaystyle q^{(\ell)}$
$\displaystyle\triangleq\tfrac{1}{nk}\cdot|U_{\ell}\cap(g(*)_{2})^{-1}(1)|.$
$\displaystyle q_{-\lambda/2}^{(\ell)}$
$\displaystyle\triangleq\tfrac{1}{nk}\cdot|U_{\ell}\cap(g(*)_{2})^{-1}(1)\cap(([n]\setminus
M)\times[k])|.$ $\displaystyle m_{-\lambda/2}^{(\ell)}$
$\displaystyle\triangleq\tfrac{1}{k}\cdot\min_{i\in
M}\\{|U_{\ell}\cap(g(*)_{2})^{-1}(1)\cap(i,*)|\\}.$ $\displaystyle G_{\ell,1}$
$\displaystyle\triangleq\tfrac{\lambda^{2}\,\ell\,n\,\kappa_{\ell}}{100\cdot
k\cdot\zeta}-\tfrac{\lambda n}{4}.$ $\displaystyle G_{\ell,2}$
$\displaystyle\triangleq\text{ the output of
}{\mathcal{A}_{\text{BL}}}\left(g(*)_{1}\mid_{U_{\ell}\,\cap\,(g(*)_{2})^{-1}(1)},{\mathbb{N}},\lambda,T\right).$

We have

$\operatorname{{\mathbb{E}}}\left[\widehat{\kappa_{\ell}}\right]=q^{(\ell)}\cdot
k\cdot\tfrac{1}{\lambda}\cdot
10\zeta=q^{(\ell)}\cdot\tfrac{10k\cdot\zeta}{\lambda}.$

We need to have a good estimator w.h.p. and therefore use the following
statistical fact:

######  Fact 6.6.

Fix $\zeta\in{\mathbb{N}}$. Let $\mathbf{X}_{1},\ldots,\mathbf{X}_{m}$ be non-
negative independent random variables and let
$\mathbf{X}=\sum_{i}\mathbf{X}_{i}$. Let $\mathbf{Y}$ be the sum of the
$\zeta$ largest (empirical) $\mathbf{X}_{i}$. Then, $\mathbf{X}-\mathbf{Y}\leq
2\operatorname{{\mathbb{E}}}[\mathbf{X}]$ with probability
$1-\exp(-\Omega(\zeta))$.

###### Proof.

Define
$p_{i}\triangleq\Pr[\mathbf{X}_{i}>2\operatorname{{\mathbb{E}}}[\mathbf{X}]/\zeta]$,
and notice that $\sum_{i}p_{i}<\zeta/2$ using Markov’s inequality. Define also
$\mathbf{Z}_{i}\triangleq\max\\{0,\mathbf{X}_{i}-2\operatorname{{\mathbb{E}}}[\mathbf{X}]/\zeta\\}$,
and $\mathbf{Z}=\sum_{i}\mathbf{Z}_{i}$. Then $\mathbf{X}-\mathbf{Z}$ is a sum
of non-negative independent random variables bounded by
$2\operatorname{{\mathbb{E}}}[\mathbf{X}]/\zeta$, and hence, by the Chernoff
bound (multiplicative form), with probability at most $\exp(-\Omega(\zeta))$,
we have
$\mathbf{X}-\mathbf{Z}>2\operatorname{{\mathbb{E}}}[\mathbf{X}]\geq\left(1+\tfrac{\operatorname{{\mathbb{E}}}[\mathbf{X}]}{\operatorname{{\mathbb{E}}}[\mathbf{X}-\mathbf{Z}]}\right)\cdot\operatorname{{\mathbb{E}}}[\mathbf{X}-\mathbf{Z}]$.
Also, notice that $\Pr[\mathbf{Z}_{i}>0]=p_{i}$, and hence, with probability
at most $\exp(-\Omega(\zeta))$,
$\sum_{i}{\mathbf{1}}[\mathbf{Z}_{i}>0]>\zeta\geq\sum_{i}p_{i}+\zeta/2$,
implying that $\mathbf{Z}>\mathbf{Y}$ with this probability as well. By the
union bound, we conclude that $\mathbf{X}-\mathbf{Y}\leq
2\operatorname{{\mathbb{E}}}[\mathbf{X}]$ with probability
$1-\exp(-\Omega(\zeta))$ as needed. ∎

Now, notice that $\widehat{\kappa_{\ell}}$ is a sum of independent random
variables and hence from 6.6, w.h.p. we have

$\kappa_{\ell}\leq
2\operatorname{{\mathbb{E}}}[\widehat{\kappa_{\ell}}]=20q^{(\ell)}\cdot\tfrac{k\cdot\zeta}{\lambda}.$

For the lower bound, we derive a lower bound for $\kappa_{\ell}$ using
$q_{-\lambda/2}^{(\ell)}$. Notice that each $i\in M$ gets sampled i.i.d. with
probability $\tfrac{10\zeta}{\lambda n}$. Hence $|S\cap M|>2\zeta$ w.h.p,
which implies that $|(S\setminus B_{\ell})\cap M|>\zeta$. This means that the
contribution of blocks in $M$ to $\kappa_{\ell}$ is at least $\zeta\cdot
k\cdot m_{-\lambda/2}^{(\ell)}$. Next, consider the contribution $\psi_{\ell}$
of blocks in $[n]\setminus M$ to $\kappa_{\ell}$. Then $\psi_{\ell}$ is a sum
of independent random variables in $k\cdot[0,m_{-\lambda/2}^{(\ell)}]$ and
hence, using the Chernoff bound, we have w.h.p.

$\psi_{\ell}\geq
0.9\operatorname{{\mathbb{E}}}\left[\psi_{\ell}\right]-\zeta\cdot k\cdot
m_{-\lambda/2}^{(\ell)}=\tfrac{9\zeta}{\lambda}\cdot k\cdot
q_{-\lambda/2}^{(\ell)}-\zeta\cdot k\cdot m_{-\lambda/2}^{(\ell)}.$

Therefore $\kappa_{\ell}\geq\psi_{\ell}+\zeta\cdot k\cdot
m_{-\lambda/2}^{(\ell)}\geq\tfrac{9\zeta}{\lambda}\cdot k\cdot
q_{-\lambda/2}^{(\ell)}$ w.h.p. as well. Hence we can finally bound
$G_{\ell,1}$, w.h.p., as follows:

$G_{\ell,1}=\tfrac{\lambda^{2}\,\ell\,n\,\kappa_{\ell}}{100\cdot
k\cdot\zeta}-\tfrac{\lambda n}{4}\in\left[\tfrac{9}{100}\lambda n\ell\cdot
q_{-\lambda/2}^{(\ell)}-\tfrac{\lambda n}{4},\,\tfrac{1}{4}\lambda n\ell\cdot
q^{(\ell)}\right].$

For the second estimator, we have that $G_{\ell,2}$ is a
$\Big{(}a_{s}\Big{(}n,\tau,\tfrac{\lambda
n}{|U_{\ell}\setminus(M\times[k])\,\cap\,g(*)^{-1}(1)|}\Big{)},\lambda
n\Big{)}$-approximation of
$\textsf{Genuine-LIS}(g(U_{\ell}))$.

We now bound the maximum over these quantities.

####  6.2.1 Upper Bound

W.h.p., for all $\ell$, we have
$G_{\ell,1}\leq\tfrac{1}{4}\cdot\lambda\,n\,\ell\,q^{(\ell)}$. Now, by
construction, all pseudo-solutions $P\in\mathcal{P}_{\ell}$ are of length
$|P|\geq\lambda\,n\,\ell/4$, and hence
$|\mathcal{P}_{\ell}|\leq\tfrac{4k}{\lambda\ell}$. Therefore, there must exist
some increasing sub-sequence $P^{*}\in\mathcal{P}_{\ell}$ such that
$|P^{*}\cap(g(*)_{2})^{-1}(1)|\geq\tfrac{1}{4}\cdot\lambda\,n\,\ell\,q^{(\ell)}$,
i.e., that contains at least that many genuine elements. This implies
$|{\widehat{\textsf{OPT}}}_{\ell}|\geq G_{\ell,1}$.

Similarly, for $G_{\ell,2}$, the Block-LIS approximation algorithm outputs a
lower bound on the LIS, and hence
$G_{\ell,2}\leq|{\widehat{\textsf{OPT}}}_{\ell}|$.

We conclude that
$\max_{\ell}\max\\{G_{\ell,1},G_{\ell,2}\\}\leq\max_{\ell}|{\widehat{\textsf{OPT}}}_{\ell}|\leq|\textsf{OPT}|$.

####  6.2.2 Lower Bound

Since ${\widehat{\textsf{OPT}}}=\cup_{\ell}{\widehat{\textsf{OPT}}}_{\ell}$,
there exists $\ell^{*}\in E_{2}(4/\lambda)$ such that
$|{\widehat{\textsf{OPT}}}_{\ell^{*}}|\geq\tfrac{|{\widehat{\textsf{OPT}}}|}{\log(4/\lambda)}$.
Fix $U^{*}\triangleq U_{\ell^{*}}\setminus(M\times[k])$,
$q^{*}=q^{(\ell^{*})}_{-\lambda/2}$,
${\widehat{\textsf{OPT}}}^{*}\triangleq{\widehat{\textsf{OPT}}}_{\ell^{*}}$,
$G^{*}_{1}=G_{1,\ell^{*}}$ and $G^{*}_{2}=G_{2,\ell^{*}}$.

Consider the following two cases:

##### Dense Case:

First, suppose $q^{*}\geq\tfrac{1}{\gamma}$. Observe that from Corollary 6.5,
we may only extract a solution of length at most $\lambda n\ell^{*}$ once the
remaining LIS is at most $2\lambda n\ell^{*}$ (i.e., after extracting longer
subsequences). Hence $|\textsf{OPT}_{\ell^{*}}|\leq 2\lambda n\ell^{*}$.
Therefore,

$G^{*}_{1}\geq\tfrac{\lambda n\ell^{*}}{20\gamma}-\tfrac{1}{4}\lambda
n\geq\tfrac{|{\widehat{\textsf{OPT}}}^{*}|}{40\gamma}-\tfrac{1}{4}\lambda
n\geq\tfrac{|{\widehat{\textsf{OPT}}}|}{40\gamma\log(4/\lambda)}-\tfrac{1}{4}\lambda
n>\tfrac{|\textsf{OPT}|}{40\gamma\log(4/\lambda)}-\lambda n.$

##### Sparse Case:

Now, suppose $q^{*}<\tfrac{1}{\gamma}$. Then
$|U^{*}\cap(g(*)_{2})^{-1}(1)\cap(([n]\setminus
M)\times[k])|<\tfrac{nk}{\gamma}$ and hence for any $\tau=\tau_{s}$ such that
$T=T_{1/c}(g(*)_{2})$, we have

$G^{*}_{2}\geq\tfrac{|\textsf{OPT}^{*}|}{\alpha}-\lambda
n\geq\tfrac{|\textsf{OPT}|}{\alpha\log(4/\lambda)}-\lambda n,$

where

$\displaystyle\alpha$ $\displaystyle=a_{s}\left(n,\tau,\tfrac{\lambda
n}{|U^{*}\,\cap\,g(*)^{-1}(1)\,\cap\,(([n]\setminus M)\times[k])|}\right)\leq
a_{s}\left(n,\tau,\tfrac{\lambda\gamma}{k}\right).$ $\displaystyle c$
$\displaystyle=c_{s}\left(n,\tau,\lambda,\tfrac{\lambda
n}{|U^{*}\,\cap\,g(*)^{-1}(1)\,\cap\,(([n]\setminus M)\times[k])|}\right)\leq
c_{s}\left(n,\tau,\lambda,\tfrac{\lambda\gamma}{k}\right).$

Since we are either in the dense or sparse case as described above, we obtain
that

$\max\\{G^{*}_{1},G^{*}_{2}\\}\geq\tfrac{|\textsf{OPT}|}{A\log(1/\lambda)}-\lambda
n,$

where
$A=\max\left\\{O(\gamma),a_{s}\left(n,\tau,\tfrac{\lambda\gamma}{k}\right)\right\\}$.

We conclude that $\widehat{G}=\max_{\ell}\\{G_{\ell,1},G_{\ell,2}\\}$ is a
$(A\log(1/\lambda),\lambda n)$-approximation for $|\textsf{OPT}|$, as needed.

##### Runtime Complexity:

The algorithm’s runtime is dominated by the first step, i.e., generating
increasing subsequences, which requires $\tilde{O}(nk)$ time using Corollary
6.5. In addition, we require $t_{s}$ time for computing the second estimator.
Thus, the overall algorithm for EstimateGenuineLIS runs in time
$\tilde{O}(nk)+t_{s}$. ∎

##  7 Algorithm for Block-LIS: Proof of Theorem 4.2

We now present our construction for the Block-LIS problem, and prove Theorem
4.2. Recall that we are given an interval $X\subseteq[n]$, a sequence
$y\in{\mathbb{N}}^{X\times[k]}$ and a range of values $Y\subset{\mathbb{N}}$,
and the goal is to approximate ${\textsf{Block-LIS}}(y,X,Y)$, i.e., the length
of a maximal sub-sequence OPT, specified by a set of indices
$w_{1},w_{2},\ldots,w_{\ell}\subseteq X\times[k]$ such that the set of (first
coordinate, value) pairs $\\{((w_{i})_{1},y_{w_{i}})\\}_{i\in[\ell]}$ is a
subset of $X\times Y$, and is a monotone set.

Our construction, at a high level, reduces the Block-LIS problem above to a
Genuine-LIS instance over $\tau$ blocks, where $\tau$ is the branching factor
of Theorem 4.2, whose value is given as input and controls the delicate
balance between approximation and complexity. The first coordinates of the
Genuine-LIS instance are computed directly, while each genuineness flag
corresponds to a Block-LIS instance of a block interval $X_{i}$ of some
smaller size $r\triangleq|X|/\tau$, and restricted to a $y$-interval
$Y^{\prime}\subseteq Y$. We consider the pair $X_{i},Y^{\prime}$ as genuine
only if the (recursive) approximation of ${\textsf{Block-
LIS}}(y,X_{i},Y^{\prime})$ is above a certain threshold $\kappa$. For each
$x$-interval $X_{i}$, we compute a set of $y$-intervals $\mathcal{Y}_{i}$
(called _candidate intervals_), which together form a _block_ in the Genuine-
LIS instance. Intuitively, one can think of the Genuine-LIS instance as
solving the global LIS, while each Block-LIS instance is solving some local
LIS over (sub-)interval $X_{i}$, over some range of $y$-values. Overall, we
will show that such a formulation is equivalent to a composition of functions,
and use the Tree Decomposition Lemma to obtain our correctness and complexity
guarantees.

###  7.1 Extending the Genuine-LIS problem

Before describing our construction for proving Theorem 4.2, we introduce a
slightly stronger version of it, which will be easier to work with. In
particular, we introduce 2 extensions of the requirements of the Genuine-LIS
algorithm. First, we allow the input $y$-values to be intervals rather than
integers, and second, we require the approximation to improve if there are
many “null” elements, i.e., if most blocks have much less than $k$
elements.444We highlight that “null” is different from “not genuine”; while we
need to test to determine that an element is “not genuine”, “null” elements
can be determined “for free”. In particular, to account for the latter, we
note that the input size is $y(X)\cap Y$, which can be much less than
$|X|\cdot k$.

Overall, the stronger version is the following:

######  Lemma 7.1 (Theorem 4.2, extended).

Fix monotone functions $a_{g}:{\mathbb{R}}_{+}^{2}\rightarrow[1,\infty)$,
$a_{s},c_{g}:{\mathbb{R}}_{+}^{3}\rightarrow[1,\infty)$ and
$c_{s}:{\mathbb{R}}_{+}^{4}\rightarrow[1,\infty)$, satisfying, for all
$r,\tau\in E_{\beta}$, $m\in{\mathbb{N}}$, $\lambda<1$,
$\lambda_{1},\lambda_{2}\in[\lambda,1]$, and $k^{\prime}\in[1,1/\lambda]$ with
$\lambda_{1}\lambda_{2}=\Omega(\lambda k^{\prime})$:

  * •

$a_{s}\left(r,\tau,\tfrac{\lambda}{m}\right)\geq\operatorname{polylog}\left(\frac{k}{\lambda}\right)\cdot
a_{g}\left(\tau,\frac{\lambda_{2}}{k^{\prime}}\right)\cdot
a_{s}\left(\frac{r}{\tau},\tau,\frac{\lambda_{1}}{m}\right)$; and

  * •

$c_{s}\left(r,\tau,\lambda,\tfrac{\lambda}{m}\right)\geq\operatorname{polylog}(n)\cdot\frac{\tau}{\lambda}+c_{g}(\tau,\lambda_{2},k^{\prime})\cdot
c_{s}\left(\frac{r}{\tau},\tau,\Theta(\lambda_{1}/k^{\prime}),\frac{\lambda_{1}}{m}\right)$.

Fix input $y\in{\mathbb{N}}^{n\times k}$, a block interval $X\subseteq[n]$,
value range interval $Y\subseteq{\mathbb{N}}$, parameters $\lambda\in(0,1)$,
$\beta\in{\mathbb{N}}$, $\tau\in E_{\beta}$. Suppose there exist the following
algorithms:

  1. $\mathcal{A}_{GL}$:

Given Genuine-LIS instance $g\in({\mathbb{N}}\times\\{0,1\\})^{n_{g}\times
k_{g}}$, with $m_{g}$ non-null elements total, and $\beta$-ary Precision-Tree
$T_{1/c_{g}(n_{g},\lambda_{g},m_{g}/n_{g})}(g(*)_{2})$ access,
$\mathcal{A}_{GL}$ outputs
$\left(a_{g}\left(n_{g},\tfrac{\lambda_{g}n_{g}}{m_{g}}\right),\lambda_{g}n_{g}\right)$-approximation
to $\textsf{Genuine-LIS}(g)$ in time $\tilde{O}(n_{g}+m_{g})$ w.h.p.

  2. $\mathcal{A}_{BL}$:

Fix $t>1$. For any interval $X^{\prime}\subset X$, value range
$Y^{\prime}\subset Y$, and any $\lambda_{s}<1$, given a $\beta$-ary Precision-
Tree
$T_{1/c_{s}\left(|X^{\prime}|,\tau,\lambda_{s},\tfrac{\lambda_{s}|X^{\prime}|}{|y_{-\lambda/2}(X^{\prime},Y^{\prime})|}\right)}(y(X^{\prime}))$,
$\mathcal{A}_{BL}$ outputs
$\left(\alpha_{s},\lambda_{s}|X^{\prime}|\right)$-approximation to
${\textsf{Block-LIS}}(y,X^{\prime},Y^{\prime})$ w.h.p., where
$\alpha_{s}\triangleq
a_{s}\left(|X^{\prime}|,\tau,\tfrac{\lambda_{s}|X^{\prime}|}{|y_{-\lambda/2}(X^{\prime},Y^{\prime})|}\right)$.
The expected run-time is at most $t_{BL}=t\cdot
c_{s}\left(|X^{\prime}|,\tau,\lambda_{s},\tfrac{\lambda_{s}|X^{\prime}|}{|y_{-\lambda/2}(X^{\prime},Y^{\prime})|}\right)\cdot\tfrac{|y(X^{\prime},Y^{\prime})|}{|X^{\prime}|}$.

Then, given a $\beta$-ary Precision-Tree $T_{1/c}(y)$, we can produce a
$(\alpha,\lambda|X|)$-approximation for ${\textsf{Block-LIS}}(y,X,Y)$ w.h.p.,
as long as $\alpha\geq
a_{s}\left(|X|,\tau,\tfrac{\lambda|X|}{|y(X^{\prime},Y^{\prime})|}\right)$ and
$c\geq
c_{s}\left(|X|,\tau,\lambda,\tfrac{\lambda|X|}{|y(X^{\prime},Y^{\prime})|}\right)$.

The algorithm’s expected run-time is at most $c\cdot
t\cdot\log^{O(\log_{\beta}(\tau))}(\beta)\cdot\tfrac{|y(X,Y)|}{|X|}$.

To prove Theorem 4.2, we use the reduction from Lemma 6.3, along with the
following reduction:

######  Lemma 7.2.

Suppose the algorithm EstimateGenuineLIS $(a(\lambda/k),\lambda
n)$-approximates Genuine-LIS for some function $a$ in time $t(n\cdot k)$ over
integers, then there exists an algorithm $\mathcal{A}^{\prime}$ that
$(O(a(\lambda n/m)\log(1/\lambda)),\lambda n)$-approximates Genuine-LIS over
intervals with $m$ non-null elements.The run-time is $t(m)+O(n+m)$.

The proof of Lemma 7.2 is deferred to Section 8.

###### Proof of Theorem 4.2 using Lemmas 7.1, 7.2 and 6.3.

The proof follows by induction. We assume Theorem 4.2 holds for
$X^{\prime}\subset X$, setting $t=t_{s}(|X^{\prime}|,\tau)$ (noting that for
the base case, we have $a_{s}(1,\cdot,\cdot)=1$ and
$c_{s}(1,\cdot,\cdot,\cdot)=1$, simply by outputting 1 if and only if the
block is not empty). Also note that the extended algorithms assumed in Lemma
7.1 reduce to the standard version using Lemma 7.2, with $O(\log
1/\lambda_{g})$ additional approximation (which can be absorbed into the
$\operatorname{polylog}(k/\lambda)$-approximation of parameter $\alpha$).
Finally, one can observe that the additive time of $\tilde{O}(n_{g}+m_{g})$
does not change the asymptotic time complexity.∎

The rest of this section is devoted to proving Lemma 7.1.

###  7.2 Algorithm

The algorithm for the Block-LIS problem, named EstimateBlockLIS, is described
in Algorithm 8 and uses routines that we describe next.

We first provide some intuition underlying the algorithm. The algorithm is
based on a reduction to a Genuine-LIS instance, where checking whether a item
is genuine takes one Block-LIS call. We view the Genuine-LIS instance as the
“global LIS” and the Block-LIS instances as “local LIS”.

Consider the case when $k=1$, in which case the problem becomes a standard LIS
problem. In this case, one visualize the instance as a set of points on a
standard two-dimensional grid, with $X$ being an interval on the $x$-axis, and
the element $(i,y_{i})$ being represented by the point with $x$-coordinate $i$
and $y$-coordinate $y_{i}$. In this equivalent formulation, the objective is
to determine the maximum length of a subsequence that is increasing with
respect to both axes.

Assume that the longest increasing subsequence OPT is of length approximately
$\lambda|X|$. Note that OPT can be distributed arbitrarily with respect to
$X$. We split $X$ into sub-intervals: for some length $r>1$, use the standard,
in-order partitioning of $X$ into $\tau=|X|/r$ mutually disjoint and covering
intervals $X_{1},\cdots,X_{\tau}$ of length $r$ each. There are two potential
extreme scenarios for the distribution of elements from OPT:

  1. 1.

All elements in OPT belong to approximately $\lambda|X|/r$ intervals $X_{i}$,
and each such interval consists entirely of elements in OPT; the other
intervals do not contribute at all.

  2. 2.

OPT is uniformly distributed across all intervals, i.e., each interval $X_{i}$
contributes approximately $\lambda r$ elements to OPT.

Intuitively speaking, the problem of certifying a “close to optimal” monotone
sequence is more difficult when fewer elements participate in an optimal
sequence. Therefore, in the first case above, one has to “work harder” on the
global LIS to find the participating intervals $X_{i}$; however, little effort
is required to verify the local LIS in each interval of interest, i.e., to get
a lower bound on the LIS within each interval. In contrast, in the second
case, it should be easier to determine the global LIS, but it is more
difficult to approximate the local LIS (within each interval $X_{i}$).

Of course, the distribution of OPT among the intervals $X_{i}$ can be
arbitrary, between these extreme scenarios. However, one can show that there
must exist some $\rho\in[1,1/\lambda]$, such that there are approximately
$1/\rho$ fraction of intervals $X_{i}$, each having approximately $\lambda\rho
r$ “local” contribution to OPT.

####  7.2.1 Algorithm Overview

Now we describe the algorithm for the general Block-LIS problem. Before
describing the main algorithm, we describe its main subroutines and mechanism,
setting up some concepts and notation along the way. The notation is
summarized in Table 1. The algorithm assumes no element repeats itself in the
sequence. To remove such assumption, one can reconfigure the element values
setting $y_{i,j}\leftarrow n\cdot y_{i,j}-i$.

##### Sampling.

The algorithm starts by sampling uniformly random blocks $(w_{j},y_{w_{j}})$
and then accumulating all $y_{w_{j}}$-samples in $Y$ within the sampled blocks
(we note that sampling is accomplished via the SODS over the input Precision-
Tree). The main idea is to generate a set $\mathcal{S}_{i}$ of sampled values,
such that the “distance in $\mathcal{S}_{i}$” between any 2 values in
$\mathcal{S}_{i}$ is approximately proportional to the number of integers in
the range over the entire $y(X_{i})$. To obtain such a guarantee, we simply
use members of $\mathcal{S}_{i}$ whose rank is a multiple of $O(\log n)$. We
also want to make sure there are not too many total samples in all blocks,
i.e., that $\sum_{i}|\mathcal{S}_{i}|$ is close to its expectation. To control
the tail bounds of such a quantity, we also discard the $\Theta(\log n)$
blocks with the largest number of samples in $Y$. The sampling algorithm is
presented in Algorithm 6, and the guarantees are formally stated in 7.7, as
part of the analysis.

Input: A Precision-Tree $T=T_{1/c}(y)$, where $y\in{\mathbb{N}}^{X\times[k]}$
consists of $|X|$ blocks with at most $k$ integers each, value range
$Y\in\mathcal{I}$, branching parameter $\tau$, and sample size $s$.

Output: Partition of $X$ with sampled $y$-values of each part.

1 $\zeta\leftarrow O(\log n)$.

2 $X_{1},\ldots,X_{\tau}\leftarrow$ a partition of $X$ into $\tau$ consecutive
intervals, each consisting of $r\triangleq|X|/\tau$ blocks.

3Using Corollary 5.4 and $T$, sub-sample blocks $S\subseteq X$ i.i.d. with
probability $\zeta\tfrac{s}{|X|}$, and let $W\leftarrow\\{(i,j)\in
S\times[k]\mid y_{i,j}\in Y\\}$.

4 Let $B\subseteq S$ be the $\zeta$ largest blocks in $S$, i.e., for which
$|B\times[k]\cap W|$ is maximized.

5

6for  _$i\in[\tau]$_ do

7 $\\{p^{i}_{1},p^{i}_{2},\ldots\\}\leftarrow y\left(W\cap((X_{i}\setminus
B)\times[k])\right)$ where $p^{i}_{m}\leq p^{i}_{m+1}$ for all $m$.

8
$\mathcal{S}_{i}\leftarrow\\{p^{i}_{m}\\}_{m\in[|p^{i}_{*}|]\cap\zeta{\mathbb{N}}}$.

9

return $(X_{*},\mathcal{S}_{*})$.

Algorithm 6 SampleAndPartition Figure 6: Description of the sampling and
partitioning subroutine.

##### Generation of Candidate Intervals.

Now we describe our construction of the candidate intervals $\mathcal{Y}_{i}$
using the sampled $y$-values $\mathcal{S}_{i}$, for some fixed $i$. The high-
level goal, as in [RSSS19], is to cover an optimal LIS solution using a small
number of monotone interval sequences denoted as _pseudo-solutions_ , so that
the largest LIS within all pseudo-solutions would be a good approximation to
the optimum. However, we need to choose such candidates more carefully, since,
in addition to “capturing the local LIS”, we would like to ensure the
following efficiency guarantees, for our delicate bounds:

  1. 1.

There are not too many candidate intervals, i.e.,
$|\mathcal{Y}_{i}|\lessapprox\tfrac{|y(X_{i},Y)|}{\lambda|X|}$; and more
importantly,

  2. 2.

The total number of integers in range over all candidate intervals do not
cause significant overhead. In particular:
$\sum_{Y^{\prime}\in\mathcal{Y}_{i}}|y(X_{i},Y^{\prime})|\lessapprox|y(X_{i},Y)|$.

In particular, we argue that given a value set $\mathcal{S}$ (corresponding to
the sampled values in each $X_{i}$) and a sub-additive set function $\psi$, we
can generate a near-linear set of candidate intervals which approximates, up
to a logarithmic factor, all candidate intervals. Here we note that the set
function $\psi_{X_{i},y}(Y^{\prime})\triangleq{\textsf{Block-
LIS}}(X_{i},Y^{\prime},y)$ is sub-additive in $Y^{\prime}$. While we did not
manage to create a single set of intervals $\mathcal{Y}_{i}$ as above, we are
able to create a small family of sets $\\{\mathcal{Y}_{i,\Delta}\\}_{\Delta\in
E_{2}(|\mathcal{S}_{i}|)}$ with similar guarantees. We show the following:

######  Lemma 7.3.

Fix a finite set of values $\mathcal{S}\subseteq{\mathbb{N}}$ of size $m$.
There exist sets of intervals
$\\{\mathfrak{C}^{\mathcal{S}}_{\Delta}\\}_{\Delta\in
E_{2}(m)}\subseteq\mathcal{I}$ such that:

  1. 1.

For all $\Delta$ and all $I\in\mathfrak{C}^{\mathcal{S}}_{\Delta}$:
$|I\cap\mathcal{S}|=\Delta$.

  2. 2.

For all $\Delta$:
$|\mathfrak{C}^{\mathcal{S}}_{\Delta}|=|\mathcal{S}|/\Delta$.

  3. 3.

Fix a sub-additive set function $\psi:\mathcal{I}\rightarrow{\mathbb{R}}$. For
any $I\in\\{[a,b]\in\mathcal{I}\mid a,b\in\mathcal{S}\\}$, there exists some
$J\in\cup_{\Delta}\mathfrak{C}^{\mathcal{S}}_{\Delta}$ with $J\subset I$ such
that $\psi(I)=O(\log|\mathcal{S}|)\cdot\psi(J)$.

We prove Lemma 7.3 in Section 7.4. For now, for each set
$\mathcal{S}_{i}=\\{p_{1}^{i},p_{2}^{i},\ldots\\}$, we construct, on average,
$O(\log(k/\lambda))$ _candidate interval sets_
$\\{\mathcal{Y}_{i,\Delta}\\}_{\Delta}$ where $\Delta\in
E_{2}(|\mathcal{S}_{i}|)$ and each $\mathcal{Y}_{i,\Delta}$ contains precisely
$\Delta$ (consecutive) elements of $\mathcal{S}_{i}$. In particular,
$\mathcal{Y}_{i,\Delta}$ are the dyadic intervals of $\mathcal{S}_{i}$, i.e.,
$\mathcal{Y}_{i,\Delta}$ is the set of all the intervals
$[p^{i}_{k\Delta+1},p^{i}_{(k+1)\Delta}]$ for all possible integer $k\geq 0$.

##### Discretization.

The algorithm performs exponential discretization over the following
parameters:

  1. $\rho$:

inverse of the fraction of intervals participating in OPT. This parameter
characterizes the relation between the “global” and “local” LIS. In
particular, for the two extreme scenarios outlined above, the parameter $\rho$
would be $1/\lambda$ and $1$ respectively.

  2. $\Delta$:

a quantity proportional to the “candidate interval size” of the local-LIS
(namely, to $|y_{-\lambda/2}(y,X_{i},Y^{\prime})|$) and inversely proportional
to the “average block size” of the global-LIS problem (namely, to
$m_{g}/n_{g}$555Recall from Lemma 7.1 that $m_{g}$ is the total number of non-
null elements of the instantiated Genuine-LIS problem and $n_{g}$ is the
number of blocks.).

##### Decomposition and Recursion.

The next step is to determine, for each choice of parameters $(\rho,\Delta)$,
the largest set of monotone candidate intervals
$\\{(i,Y^{\prime}):Y^{\prime}\in\mathcal{Y}_{i,\Delta}\\}_{i}$ such that each
candidate interval has local LIS at least $\kappa_{\rho}\triangleq r/\rho$.
For this purpose, the algorithm defines the pair $(i,Y^{\prime})$ as “genuine”
iff the local LIS is long enough (determined via recursive call to Block-LIS).
Then the problem becomes to solve a “global” Genuine-LIS instance over all
genuine $(X_{i},Y^{\prime})$ pairs. In other words, we formulate the problem
as a composition of a Genuine-LIS problem over many smaller Block-LIS
problems, where the Precision-Tree decomposition algorithm (Lemma 5.5) is used
to access the sequence question.

##### Optimization.

Finally, we output the solution with the maximum value among all combinations
of the parameter $\rho$ and $\Delta$.

Input: A Precision-Tree $T=T_{1/c}(y)$, where $y\in{\mathbb{N}}^{X\times[k]}$
consists of $|X|$ blocks with at most $k$ integers each, $x$-partition
$\\{X_{i}\\}_{i}$ of $X$, $y$-partition sets $\\{\mathcal{Y}_{i}\\}_{i}$ (for
a fixed $\Delta$) of some interval $Y\in\mathcal{I}$.

Output: An integer $\widehat{L}\in\left[0,\textsf{Block-LIS}(y,X,Y)\right]$.

1 Let ${\mathcal{A}_{\text{GL}}}$, ${\mathcal{A}_{\text{BL}}}$ be the
aforementioned algorithms from Lemma 7.1.

2 Define $\kappa_{\rho}\triangleq\tfrac{r}{\rho}$.

3For each $i$, define
$\Lambda_{\rho}(i,*)\triangleq\left[\left(Y^{\prime},{\mathbf{1}}\left[{\mathcal{A}_{\text{BL}}}\left(y(X_{i}),Y^{\prime},\tfrac{1}{\rho},\tau\right)>\kappa_{\rho}\right]\right)\right]_{Y^{\prime}\in\mathcal{Y}_{i}}$.

4for  _$\rho\in E_{2}(1/\lambda)$_ do

5 Compute
$G_{\rho}\leftarrow{\mathcal{A}_{\text{GL}}}(\Lambda_{\rho},\lambda\rho)\cdot
0.5\kappa_{\rho}$ using Lemma 5.5 and $T$.

return $\widehat{L}\leftarrow\max_{\rho}G_{\rho}$.

Algorithm 7 Decompose Figure 7: Description of the decomposition subroutine. Note that lines $2-4$ are merely definitions for $\rho\in E_{2}(1/\lambda)$, and not computational steps. Symbol, Definition | Description
---|---
$\lambda$ | additive error parameter (as fraction); given as input
$\tau$ | branching factor; given as input
$X_{i}$ | sub-interval of $X$
$r:=|X|/\tau$ |  _radius_ , i.e., number of blocks in each interval $X_{i}$
$\rho$ | inverse of fraction of intervals participating in global OPT
$\kappa_{\rho}:=r/\rho$ | the local-LIS threshold that qualifies a candidate interval as “genuine”
$Y$ | permissible range of $y$-values
$\mathcal{S}_{i}$ |  $y$-values in $Y$ found in sampled blocks in $X_{i}$
$\mathcal{Y}_{i,\Delta}$ | candidate intervals for $X_{i}$ using samples of $\mathcal{S}_{i}$ of “distance” $\approx\Delta$
$\ell_{i,Y^{\prime}}:={\textsf{Block-LIS}}(y,X_{i},Y^{\prime})$ | the length of the longest sub-sequence of $y(X_{i})$ using values in $Y^{\prime}$
$T:=T_{1/c}(y)$ |  $\beta$-ary Precision-Tree with starting complexity/precision $c$
$a_{g}(\cdot,\cdot),c_{g}(\cdot,\cdot)$ | approximation and complexity functions for Genuine-LIS
$a_{s}(\cdot,\cdot,\cdot),c_{s}(\cdot,\cdot,\cdot)$ | approximation and complexity functions for Block-LIS
$y_{-\delta,Y^{\prime}}$ |  20cmblock sequence $y$, where the heaviest $\delta$ fraction of blocks
(considering only values in $Y^{\prime}$) are emptied |
$y_{-\delta}(X^{\prime},Y^{\prime}):=y(X^{\prime})_{-\delta,Y^{\prime}}\cap Y^{\prime}$ | multiset of values in $y(X^{\prime})_{-\delta,Y^{\prime}}$ restricted to $Y^{\prime}$
Table 1: Notation Table

Input: A Precision-Tree $T=T_{1/c}(y)$, where $y\in{\mathbb{N}}^{X\times[k]}$
consists of $|X|$ blocks with at most $k$ integers each, value range
$Y\subseteq{\mathbb{N}}$, error parameter $\lambda\in(1/n,1)$, branching
parameter $\tau$.

Output: An integer $\widehat{L}\in\left[0,\textsf{Block-LIS}(y,X,Y)\right]$.

1

2if  _$|X| <c$_ then

3 return $\widehat{L}\leftarrow{\textsf{Block-LIS}}(y,X,Y)$ through exact
computation.

4

5$(X_{*},\mathcal{S}_{*})\leftarrow\textsc{SampleAndPartition}(T,\tau,\tfrac{\tau}{\lambda})$.

6

7 $\mathcal{Y}_{i,*}\leftarrow$ sets of intervals by invoking Lemma 7.3 using
each $\mathcal{S}_{i}\in\mathcal{S}_{*}$.

8

9return
$\widehat{L}\leftarrow\max_{\Delta}\\{\textsc{Decompose}(T,X_{*},\mathcal{Y}_{*,\Delta})\\}$.

Algorithm 8 EstimateBlockLIS Figure 8: Description of the algorithm
EstimateBlockLIS.

###  7.3 Main analysis

Before analyzing the estimator $\widehat{L}$, we show several important
properties. First, we claim that partitioning $X$ into intervals of smaller
size and matching each one with a value range $Y$ monotonically cannot over-
estimate the overall LIS:

######  Lemma 7.4 (Upper Bound).

Fix an interval $Y\subset{\mathbb{N}}$. Let $X_{1},\ldots,X_{\tau}$ be a
partition of $X$ into consecutive, disjoint, in-order block intervals (i.e.,
$X_{1}<X_{2}<\ldots<X_{\tau}$) and let $P\subset[\tau]\times\mathcal{I}$ be an
arbitrary monotone set. Then, we have $\sum_{(i,Y_{i})\in P}{\textsf{Block-
LIS}}(y,X_{i},Y_{i}\cap Y)\leq{\textsf{Block-LIS}}(y,X,Y)$.

###### Proof.

For each $(i,Y_{i})\in P$, let
$\textsf{OPT}_{i}\subseteq(X_{i}\times[k])\,\cap\,y^{-1}(Y_{i}\cap Y)$ be a
set of coordinates of an optimal increasing subsequence for ${\textsf{Block-
LIS}}(y,X_{i},Y_{i}\cap Y)$ Then $\sum_{(i,Y_{i})\in
P}|\textsf{OPT}_{i}|=\sum_{(i,Y_{i})\in P}{\textsf{Block-
LIS}}(y,X_{i},Y_{i}\cap Y)$. On the other hand, since $P$ is a monotone set,
we have $y(p)<y(q)$ for any $p\in\textsf{OPT}_{i},q\in\textsf{OPT}_{j}$ with
$i<j$. We conclude that the sequence $\cup_{i}\,y(\textsf{OPT}_{i})\subseteq
Y$ forms an increasing subsequence of $y(X)$ of length $\sum_{(i,Y_{i})\in
P}{\textsf{Block-LIS}}(y,X_{i},Y_{i}\cap Y)$ and the claim follows. ∎

Next, we argue three essential invariants when constructing candidate
intervals. These guarantees will be used later to lower bound our estimator:

######  Lemma 7.5 (Candidate intervals guarantees).

Fix input $X,Y,y$. With high probability, all the following invariants hold
for the EstimateBlockLIS algorithm:

  1. 1.

For all $i,\Delta$ and all $Y^{\prime}\in\mathcal{Y}_{i,\Delta}$,

$|y_{-\lambda/2}(X_{i},Y^{\prime})|=O\left(\lambda\Delta r\right).$

  2. 2.

For all $\Delta$,

$\operatorname{{\mathbb{E}}}_{i\in[\tau]}\left[|\mathcal{Y}_{i,\Delta}|\right]=O\left(\frac{|y(X,Y)|}{\lambda\Delta|X|}\right),$

  3. 3.

There exist candidate intervals
$Y^{\prime}\in\oplus_{i\in[\tau]}\cup_{\Delta\in
E_{2}(\operatorname{poly}(k/\lambda))}\mathcal{Y}_{i,\Delta}$ such that
$\\{(i,Y^{\prime}_{i})\\}_{i}$ is a monotone set; and

$\sum_{i}{\textsf{Block-
LIS}}(y,X_{i},Y^{\prime}_{i})=\Omega\left(\frac{{\textsf{Block-
LIS}}(y,X,Y)-\lambda|X|}{\log(k/\lambda)}\right).$

We analyze the correctness and complexity of our algorithm, proving Lemma 7.1
assuming Lemma 7.5. We prove Lemma 7.5 in Section 7.5.

###### Proof of Lemma 7.1 using Lemma 7.5.

For all $i,\Delta$ and all $Y^{\prime}\in\mathcal{Y}_{i,\Delta}$, let
$\ell_{i,Y^{\prime}}\triangleq{\textsf{Block-LIS}}(y,X_{i},Y^{\prime})$. By
Lemma 7.5 (3), we have that for some $\Delta^{*}$, there exists a monotone set
of pairs $P^{*}\in\oplus_{i}(\\{i\\}\times\mathcal{Y}_{i,\Delta^{*}})$ such
that:

$\sum_{(i,Y^{\prime})\in
P^{*}}\ell_{i,Y^{\prime}}\geq\Omega\left(\tfrac{{\textsf{Block-
LIS}}(y,X,Y)-\lambda|X|}{\log(k/\lambda)\cdot\log(k/\lambda)}\right)>\tfrac{\Omega({\textsf{Block-
LIS}}(y,X,Y))-\lambda|X|}{\log^{2}(k/\lambda)}.$

Therefore, we have that, for any $\alpha_{s}>1$, there is some $\rho^{*}\in
E_{2}(1/\lambda)$ for which, using $\kappa_{\rho^{*}}=r/\rho^{*}$:

$\sum_{(i,Y^{\prime})\in P^{*}}{\mathbf{1}}\left[\ell_{i,Y^{\prime}}\geq
2\alpha_{s}\cdot\kappa_{\rho^{*}}\right]\geq\tfrac{1}{2\alpha_{s}\kappa_{\rho^{*}}}\cdot\tfrac{\Omega({\textsf{Block-
LIS}}(y,X,Y))-\lambda|X|}{\log^{3}(k/\lambda)}$ (4)

Let us first argue correctness. Define
$\kappa^{*}\triangleq\kappa_{\rho^{*}}=\tfrac{r}{\rho^{*}}$ and
$\mathcal{Y}_{i}^{*}\triangleq\mathcal{Y}_{i,\Delta^{*}}$. Recall the
following guarantees of ${\mathcal{A}_{\text{BL}}}$ and
${\mathcal{A}_{\text{GL}}}$ which hold for each pair $(i,Y^{\prime})\in
P^{*}$:

  1. 1.

Let $\widehat{\ell_{i,Y^{\prime}}}$ be the output of
${\mathcal{A}_{\text{BL}}}(y(X_{i}),Y^{\prime},\tfrac{1}{\rho^{*}},\tau)$.
Then $\widehat{\ell_{i,Y^{\prime}}}$ is a
$\left(\alpha_{s},\tfrac{r}{\rho^{*}}\right)$ -approximation of
$\ell_{i,Y^{\prime}}$, where $\alpha_{s}\triangleq
a_{s}\left(r,\tau,\tfrac{r/\rho^{*}}{|y_{-\lambda/2}(X_{i},Y^{\prime})|}\right)$.

  2. 2.

Let $\Lambda^{*}\triangleq\Lambda_{\Delta^{*},\rho^{*}}$. The output of
${\mathcal{A}_{\text{GL}}}(\Lambda^{*},\lambda\rho^{*})$ is a
$\left(\alpha_{g},\lambda\rho^{*}\tau\right)$-approximation of
$\sum_{(i,Y^{\prime})\in
P^{*}}{\mathbf{1}}\left[\widehat{\ell^{*}_{i,Y^{\prime}}}\geq\kappa^{*}\right]$,
where $\alpha_{g}\triangleq
a_{g}\left(\tau,\tfrac{\lambda\rho^{*}n_{g}}{m_{g}}\right)$, where
$n_{g}=\tau$ and $m_{g}=\sum_{i}\left[|\mathcal{Y}_{i}^{*}|\right]$, are,
respectively, the number of blocks and non-null elements in the Genuine-LIS
instance.

We use the approximation guarantees from above to obtain a lower bound on
$L^{*}\triangleq L_{\Delta^{*},\rho^{*}}$. Assuming $c\geq c_{s}(\cdot)\cdot
c_{g}(\cdot)$, we invoke Lemma 5.5 to get that the quantity $L^{*}$ is a
$(\alpha_{g},\lambda\rho^{*}\tau)$-approximation for a Genuine-LIS instance,
where each block $i$ is defined by all possible candidate intervals
$\mathcal{Y}^{*}_{i}$, and each candidate interval
$Y^{\prime}\in\mathcal{Y}^{*}_{i}$ is genuine iff a
$\left(\alpha_{s},\tfrac{r}{\rho^{*}}\right)$-local approximation
$\widehat{\ell_{i,Y^{\prime}}}$ passes the $\kappa_{\rho^{*}}$ threshold.

Note that the approximations are:

$\displaystyle\alpha_{s}$
$\displaystyle=a_{s}\left(r,\tau,\tfrac{r}{\rho^{*}|y_{-\lambda/2}(X_{i},Y^{\prime})|}\right)$
$\displaystyle\alpha_{g}$
$\displaystyle=a_{g}\left(\tau,\tfrac{\lambda\rho^{*}}{\operatorname{{\mathbb{E}}}_{i}\left[|\mathcal{Y}_{i}^{*}|\right]}\right).$

We let
$\lambda_{s}=\tfrac{|y(X,Y)|}{|X|}\cdot\tfrac{r}{\rho^{*}|y_{-\lambda/2}(X_{i},Y^{\prime})|}$,
and
$\lambda_{g}=\tfrac{m_{g}}{n_{g}}\cdot\tfrac{\lambda\rho^{*}}{\operatorname{{\mathbb{E}}}_{i}\left[|\mathcal{Y}_{i}^{*}|\right]}=\lambda\rho^{*}$,
in which case:

$\alpha_{s}\cdot\alpha_{g}=a_{s}\left(r,\tau,\tfrac{\lambda_{s}|X|}{|y(X,Y)|}\right)\cdot
a_{g}\left(\tau,\tfrac{\lambda_{g}n_{g}}{m_{g}}\right).$ (5)

We need to bound $\lambda_{s}\lambda_{g}$. For this, we use Lemma 7.5 (1) and
(2), to obtain for each $Y^{\prime}\in\mathcal{Y}^{*}_{i}$, for all $i$:

$|y_{-\lambda/2}(X_{i})\cap Y^{\prime}|=O\left(\lambda\Delta r\right);$ (6)
$\tfrac{m_{g}}{n_{g}}=\operatorname{{\mathbb{E}}}_{i}\left[|\mathcal{Y}_{i}^{*}|\right]=O\left(\tfrac{|y(X,Y)|}{\lambda\Delta|X|}\right).$
(7)

We obtain that

$\lambda_{s}\lambda_{g}\cdot
n_{g}/m_{g}=\Omega\left(\tfrac{|y(X,Y)|}{|X|}\cdot\tfrac{r}{\rho^{*}\lambda\Delta
r}\cdot\lambda\rho^{*}\cdot\tfrac{\lambda\Delta|X|}{|y(X,Y)|}\right)=\Omega(\lambda),$

as required in the theorem statement.

We can finally derive the following overall bound on $\widehat{L}$, and in
particular, show it is a $(\alpha,\lambda|X|)$-approximation, for some
$\alpha=O\left(\alpha_{s}\cdot\alpha_{g}\cdot\operatorname{polylog}(k/\lambda)\right)$.
For the lower bound, recall $\widehat{L}=\max_{\rho,\Delta}L_{\rho,\Delta}\geq
L^{*}$, and therefore we have that:

$\displaystyle\widehat{L}$ $\displaystyle\geq L^{*}$
$\displaystyle\geq\left(\tfrac{1}{\alpha_{g}}\sum_{(i,Y^{\prime})\in
P^{*}}{\mathbf{1}}\left[\widehat{\ell_{i,Y^{\prime}}}\geq\kappa^{*}\right]-\lambda\rho^{*}\tau\right)\cdot
0.5\kappa^{*}$ $\displaystyle\geq\sum_{(i,Y^{\prime})\in
P^{*}}\tfrac{1}{\alpha_{g}}{\mathbf{1}}\left[\ell_{i,Y^{\prime}}\geq\alpha_{s}\cdot\left(\kappa^{*}+\tfrac{r}{\rho^{*}}\right)\right]\cdot
0.5\kappa^{*}-\lambda\rho^{*}\tau\cdot 0.5\kappa^{*}$
$\displaystyle\geq\tfrac{0.5\kappa^{*}}{\alpha_{g}}\cdot\sum_{(i,Y^{\prime})\in
P^{*}}{\mathbf{1}}\left[\ell_{i,Y^{\prime}}\geq\alpha_{s}\cdot\left(\kappa^{*}+\tfrac{r}{\rho^{*}}\right)\right]-0.5\lambda|X|$
$\displaystyle\geq\tfrac{0.5\kappa^{*}}{\alpha_{g}}\cdot\sum_{(i,Y^{\prime})\in
P^{*}}\left({\mathbf{1}}\left[\ell_{i,Y^{\prime}}\geq\alpha_{s}\cdot\left(\kappa^{*}+\kappa^{*}\right)\right]\right)-0.5\lambda|X|$
$\displaystyle\geq\tfrac{0.5\kappa^{*}}{\alpha_{g}}\cdot\tfrac{1}{2\alpha_{s}\kappa_{\rho^{*}}}\cdot\tfrac{\Omega({\textsf{Block-
LIS}}(y,X,Y))-\lambda|X|}{\log^{3}(k/\lambda)}-0.5\lambda|X|$
$\displaystyle>\Omega\left(\tfrac{{\textsf{Block-
LIS}}(y,X,Y)}{\alpha_{s}\alpha_{g}\log^{3}(k/\lambda)}\right)-\lambda|X|.$

For the upper bound, we use Lemma 7.4 to claim that for any set of parameters,
and any choice of monotone pairs, $L_{\rho,\Delta}$ is upper bounded by
${\textsf{Block-LIS}}(y,X,Y)$, and hence any approximation of such quantity is
guaranteed to be bounded by ${\textsf{Block-LIS}}(y,X,Y)$ as well.

##### Proving the assumed bound for $c$.

For correctness, it is left to show the lower bound for $c$ suffices to obtain
$c\geq c_{sampling}+c_{g}(\cdot)\cdot c_{s}(\cdot)$ for every set of potential
parameters from above, and where $c_{sampling}$ is the complexity for sampling
the set $S_{*}$. Note that $c_{sampling}=\zeta s=\zeta\tau/\lambda$. As
regards $c_{s},c_{g}$, in order to obtain the desired approximations
$\alpha_{g},\alpha_{s}$, we need complexities
$c_{g}=c_{g}(\tau,\lambda_{g},m_{g}/n_{g})$ and
$c_{s}=c_{s}(r,\tau,1/\rho^{*})$ respectively. Now, noting
$\tfrac{m_{g}}{n_{g}}\stackrel{{\scriptstyle
Eq.~{}(\ref{eq::avg_k})}}{{=}}O\left(\tfrac{|y(X,Y)|}{\lambda\Delta|X|}\right)$,
we have

$\tfrac{1}{\rho^{*}}=\tfrac{\lambda\cdot\lambda_{s}\cdot\Delta\cdot|X|}{|y(X,Y)|}=\Omega\left(\tfrac{\lambda_{s}n_{g}}{m_{g}}\right),$

as needed. This concludes the correctness proof.

##### Runtime Analysis.

The algorithm consists of the following procedures:

First, sub-sampling of blocks, with expected runtime
$\tilde{O}(\tfrac{\tau}{\lambda})\cdot\tfrac{|y(X,Y)|}{|X|}$ by Corollary 5.4.

Second, computation of candidate intervals, takes time
$\tilde{O}(|S|)=\tilde{O}(\tfrac{\tau}{\lambda})\cdot\tfrac{|y(X,Y)|}{|X|}$.

Last, and most important, are the recursive calls invoked by the decomposition
procedure. Here, for each set of parameters $\Delta,t$, the expected runtime
by Lemma 5.5 is

$\tilde{O}\left(\tau+t_{GL}+\tfrac{1}{\delta\tau}\cdot\left\lVert
t_{f}\right\rVert_{1}\cdot\log^{O(\log_{\beta}(\tau))}(\beta)\right),$

where $\delta=\tfrac{1}{c_{g}(\cdot)}$. The Lemma assumption provides the
bound

$t_{GL}=\tilde{O}(m_{g}+n_{g})=\tilde{O}(\tau+\sum_{i}|\mathcal{Y}_{i,\Delta}|)=\tilde{O}(\tau+|S|)=\tilde{O}(\tfrac{\tau}{\lambda})\cdot\tfrac{|y(X,Y)|}{|X|},$

and hence the main quantity to analyze is
$\tfrac{1}{\delta\tau}\cdot\left\lVert
t_{f}\right\rVert_{1}\cdot\log^{O(\log_{\beta}(\tau))}(\beta)$.

Notice that computing each $f_{i}$ requires $|\mathcal{Y}_{i,\Delta}|$
invocations of ${\mathcal{A}_{\text{BL}}}$, where for each
$Y^{\prime}\in\mathcal{Y}_{i,\Delta}$, we pay (expected) time $t\cdot
c_{s}(\cdot)\cdot\tfrac{|y(X_{i},Y^{\prime})|}{|X_{i}|}$. Furthermore, note
that candidate intervals in $\mathcal{Y}_{i,\Delta}$ are disjoint and
contained in $Y$, and hence
$\sum_{Y^{\prime}\in\mathcal{Y}_{i,\Delta}}|y(X_{i},Y^{\prime})|\leq|y(X_{i},Y)|$.
Therefore:

$\operatorname{{\mathbb{E}}}_{T}\left[\left\lVert
t_{f}\right\rVert_{1}\right]\leq\sum_{i}\sum_{Y^{\prime}\in\mathcal{Y}_{i,\Delta}}t\cdot
c_{s}\cdot\tfrac{|y(X_{i},Y^{\prime})|}{|X_{i}|}\leq\sum_{i}t\cdot
c_{s}\cdot\tfrac{|y(X_{i},Y)|}{|X_{i}|}=t\cdot
c_{s}\cdot\tfrac{|y(X,Y)|\tau}{|X|}.$

Now, since $c\geq c_{s}\cdot c_{g}$, then,

$\operatorname{{\mathbb{E}}}_{T}\left[\tfrac{1}{\delta\tau}\cdot\left\lVert
t_{f}\right\rVert_{1}\right]=\tfrac{c_{g}}{\tau}\cdot\operatorname{{\mathbb{E}}}[\left\lVert
t_{f}\right\rVert_{1}]\leq t\cdot c_{s}\cdot
c_{g}\cdot\tfrac{|y(X,Y)|}{|X|}\leq t\cdot c\cdot\tfrac{|y(X,Y)|}{|X|}.$

Counting the time taken by all procedures above, the overall expected runtime
is:

$\tilde{O}\left(\tfrac{\tau}{\lambda}+t\cdot
c\cdot\log^{O(\log_{\beta}(\tau))}(\beta)\right)\cdot\tfrac{|y(X,Y)|}{|X|}=t\cdot
c\cdot\log^{O(\log_{\beta}(\tau))}(\beta)\cdot\tfrac{|y(X,Y)|}{|X|},$

as needed.

∎

###  7.4 Dyadic Construction for Candidate Intervals: Proof of Lemma 7.3

We now describe the algorithm for generating candidate intervals, proving
Lemma 7.3. First, we show how to generate a small “covering” set of candidate
intervals over some fixed set $[m]$.

######  Claim 7.6.

For any $m\in{\mathbb{N}}$, there exists a clustering of $[m]$ into intervals
$\\{\mathcal{J}_{\Delta,1},\mathcal{J}_{\Delta,2},\ldots,\mathcal{J}_{\Delta,m/\Delta}\\}_{\Delta\in
E_{2}(m)}$ where each $\mathcal{J}_{\Delta,j}\subseteq\mathcal{I}\cap 2^{[m]}$
and further:

  1. 1.

$|\mathcal{J}_{\Delta,j}|=\Delta$ for all $\Delta,j$.

  2. 2.

For any interval $I\in[m]\cap\mathcal{I}$, there exists a set of intervals
$\mathfrak{C}_{I}\subseteq\\{\mathcal{J}_{\Delta,j}\\}_{\Delta,j}$ of size
$|\mathfrak{C}_{I}|=O(\log m)$, such that $I$ is precisely covered by
$\mathfrak{C}_{I}$; i.e.,
$I=\cup_{\mathcal{J}\in\mathfrak{C}_{I}}\mathcal{J}$.

###### Proof.

Consider a binary tree $T_{m}$ with leaves indexed by integers in $[m]$ and
internal nodes indexed by the union of its children. The set of clusters