text:
\section{Introduction}

Finding the length of longest increasing subsequence (LIS) of an array
is a classic algorithmic problem. We are given
a function $f:[n] \rightarrow \mathbb{R}$, which we think of as an array.
An \emph{increasing subsequence} of this array is a sequence
of indices $i_1 < i_2 < \cdots < i_k$ such that
$f(i_1) \leq f(i_2) \leq \cdots \leq f(i_k)$. An LIS is an
increasing subsequence
of maximum size. The LIS problem is a standard elementary application
of dynamic programming used in basic algorithms textbooks (e.g. ~\cite{CLRS}).
The obvious dynamic program yields
an $O(n^2)$ algorithm. Fredman~\cite{F75} gave a clever way of maintaining the dynamic program,
leading to an $O(n\log n)$ algorithm.
Aldous and Diaconis~\cite{AD99} use the elegant algorithm of
\emph{patience sorting} to find
the LIS.

The size of the \emph{complement} of the LIS is called
the \emph{distance to monotonicity}, and  is equal to the minimum number of values that need to be changed to make
$f$ monotonically nonde
creasing.  We write ${\tt lis}_f$ for the length of the LIS
and set ${\tt loss}_f=n-{\tt lis}_f$. The distance to monotonicity is conventionally defined
as $\varepsilon_f = {\tt loss}_f/n$.
For exact algorithms, of course,
finding ${\tt lis}_f$ is equivalent to finding ${\tt loss}_f$. Approximating these quantities can be
very different problems.

In recent years, motivated by the increasing ubiquity of massive
sets of data, there has been considerable attention given to
the study of approximate solutions of computational problems on huge
data sets by judicious sampling of the input.
In the context of property testing it was
shown in~\cite{EKK+00,DGLRRS99,FischerSurvey,ACCL1}
that for any $\varepsilon > 0$,
$O(\varepsilon^{-1}\log n)$ random samples are necessary and sufficient to
distinguish the case that $f$ is increasing (${\tt loss}_f=0$)
from the case that ${\tt loss}_f \geq \varepsilon n$.

In
of~\cite{PRR04,ACCL1}, algorithms for estimating
distance
to monotonicity were given.  Both of these algorithms  gave a $2+o(1)$-approximation to ${\tt loss}_f$  and
had running time $({\tt loss}_f (\log n)/n)^{O(1)}$, and were the best such algorithms known prior to the present work.
These algorithms
provide little information about the LIS if ${\tt lis}_f$ is between $0$ and $n/2$.
In this case ${\tt loss}_f \geq n/2$, so a 2-approximation to ${\tt loss}_f$ may produce the (trivial) estimate $n$ to ${\tt loss}_f$.
Indeed, there are simple examples where ${\tt loss}_f=n/2$
and the algorithms of ~\cite{PRR04,ACCL1} do exactly this.

Note that for small $\varepsilon>0$,
the situation that ${\tt loss}_f=\varepsilon n$ and ${\tt lis}_f=(1-\varepsilon) n$
is qualitatively different than the situation ${\tt loss}_f=(1-\varepsilon)n$ and ${\tt lis}_f = \varepsilon n$.
In the former case the array is ``nearly"
increasing and the known algorithms exploit this structure.

In this paper, we show how to get $\delta n$-additive approximations
to ${\tt lis}_f$ in time polylogarithmic in $n$ for any $\delta >0$.
With high probability, our algorithm outputs an estimate ${\tt est}$ such that $|{\tt est} - {\tt lis}_f| \leq \delta n$.
This is equivalent to getting an additive $\delta n$-approximation
for ${\tt loss}_f$.
The existing multiplicative 2-approximation algorithm for ${\tt loss}_f$
gives the rather weak consequence of an additive $n/2$-approximation for ${\tt lis}_f$.
Prior to the present paper, this was the best additive error guarantee that was known.  Here we prove:

\iffalse
We use \emph{with high probability}
to indicate probability at least $1-n^{-\Omega(\log n)}$, where the $\Omega$-notation
hides some fixed constant independent of any parameters.
\fi

\begin{theorem} \label{thm:main} Let $f$ be an array of size $n$
and ${\tt lis}_f$ the size of the LIS.
There is a randomized algorithm
which takes as input an array $f$ and  parameter $\delta > 0$, and outputs
a number ${\tt est}$ such that
$|{\tt est} - {\tt lis}_f| \leq \delta n$ with probability at least 3/4. The running time
is $(1/\delta)^{O(1/\delta)} (\log n)^c$, for some
absolute constant $c$ independent of $n$ and $\delta$.
\end{theorem}

The algorithm of this theorem is obtained from a specific choice of parameters within
our main algorithm.  By using a different  choice of parameters, the same algorithm
provides a
multiplicative $(1+\tau)$-approximation to ${\tt loss}_f$ for any $\tau>0$ (improving
on the  $(2+\tau)$-approximations
of~\cite{PRR04,ACCL1}).

\begin{theorem} \label{thm:dist} Let $0<\tau < 1$ and $\varepsilon_f={\tt loss}_f/n$.
There exists an algorithm with running time
$(1/(\varepsilon_f\tau))^{O(1/\tau)}(\log n)^c$ (where $c$ is an absolute constant) that computes a real number $\varepsilon$
such that with probability at least 3/4,  $\varepsilon_f \in [\varepsilon ,(1+\tau)\varepsilon]$.
\end{theorem}

The error probability of 1/4  in each of these theorems can be reduced to any desired value $\eps>0$ by the following standard
method: for an appropriate constant $C$,  repeat the algorithm $C \log(1/\eps)$ times and output the median output of the trials.  This output will be outside
the desired estimation interval only if at least half of the trials produce an output outside of the desired estimation interval.    Since for each trial this happens
with probability at most 1/4, we can use a binomial tail bound
 (e.g. \Prop{hoeff1} below), to conclude that the probability that the median lies outside the desired interval
is at most $\eps$.

\subsection{Related work and relation to other models}

The field of \emph{property testing}~\cite{RS96,GGR98} deals with finding sublinear, or even constant,
time algorithms for distinguishing whether an input has a property,
or is far from the property (see surveys~\cite{FischerSurvey,RonSurvey,GoldreichSurvey}). The property
of monotonicity has been studied over a various partially ordered domains, especially
the boolean hypercube and the set $[n]$~\cite{GGLRS00,DGLRRS99,ELNRR02,HK03,ACCL1,PRR04,BGJRW09}. Our result
can be seen as a \emph{tolerant tester}~\cite{PRR04}, which can closely
approximate the distance to monotonicity.

The LIS has been studied in detail in the streaming model~\cite{GJKK07,SW07,GG07,EJ08}. Here,
we are allowed a small number (usually, just a single) of passes over
the array and we wish to estimate either the LIS or the
distance to monotonicity. The distance approximations
in the streaming model
are based on the sublinear time approximations.
The technique of counting inversions used in the property
testers and sublinear time distance approximators is a major
component of these algorithms. This problem has
also been studied in the communication
models where various parties may hold different
portions of the array, and the aim is to compute
the LIS with minimum communication. This is usually
studied with the purpose of proving streaming lower bounds~\cite{GJKK07,GG07,EJ08}.
Subsequent work of the authors use dynamic programming methods to design
a streaming algorithm for LIS, giving estimates similar to those obtained here~\cite{SaSe12}.
This does not use the techniques from this result, and is a much easier problem
than the sampling model.

There has been a body of work on studying the Ulam
distance between strings~\cite{AK07,AK08,AIK09,AN10}. For permutations, the Ulam
distance is twice the size of the complement
of the longest common subsequence. Note that Ulam
distance between a permutation and the identity permutation
is basically the distance to monotonicity. There has
been a recent sublinear time algorithm for approximating
the Ulam distance between two permutations~\cite{AN10}. We again note
that the previous techniques for distance approximation
play a role in these results. Our results
may be helpful in getting better approximations
for these problems.

\subsection{Obstacles to additive estimations of the LIS}

A first approach to estimating the length of the LIS is to take a small random sample $S$ of entries of the array, and
exactly compute the length of the LIS of the sample, ${\tt lis}_f(S)$.  Scaling this up to
$n\frac{{\tt lis}_f(S)}{|S|}$ gives a natural estimator for ${\tt lis}_f$.
A little consideration shows that this estimator can be very inaccurate.
Consider the following example.  Let $K$ be a large constant
and $n=Kt$. For $0 \leq i \leq t-1$ and $0 \leq j < K$,
set $f(iK+j+1)=iK-j$. Refer to \Fig{func1}.  The LIS of this function has size $t=n/K$,
but a small random sample will almost certainly be completely
increasing and so the estimator is likely to equal $n$.
\iffalse
This is because the scale of violations (pairs $i<j$ with $f(i)>f(j)$)
is too small for the sample
to detect. Violations can lie at any scale, and the algorithm needs find them wherever they are.
\fi

\begin{figure}[tb]
  \centering
 \includegraphics[width=0.25\textwidth]{figures/func1.pdf}
    \caption{Small random samples will almost always be totally increasing}
  \label{fig:func1}
\end{figure}

An alternative approach to estimating the LIS
is to give an algorithm which, given an index $i \in [n]$, classifies
$i$ as {\em good} or {\em bad} in such a way that:

\begin{itemize}
\item The good indices form an increasing sequence.
\item The number of good indices is close to the size of the LIS, so the number of bad indices
can be bounded.
\end{itemize}

This approach was used in \cite{ACCL1} and \cite{PRR04}.
The classification algorithms presented in those papers essentially work as follows.
Given an index $i$,
for each $k$ between $1$ and $O(\log(n))$ consider each of the index intervals of
the form $[i-(1+\gamma)^k,i+(1-\gamma)^k]$, for all $k$ (for a suitably small $\gamma$), and for each such interval, examine a randomly chosen
subset of indices of polylogarithmic size.
If, for any one of these samples,
$i$ is in violation with at least half of the sample then $i$ should be classified as bad.
The analysis of this algorithm shows that the fraction of indices that
are delared bad is at most $(2+o(1)){\tt loss}_f/n$ which gives a multiplicative $2+o(1)$-approximation
to ${\tt loss}_f$.    This analysis is essentially tight since for the
function shown in \Fig{func1} where  ${\tt lis}_f = n/K$),
these algorithms will classify all indices as bad.  In particular, when $K=2$, the distance to monotonicity
is $n/2$ but the algorithm returns an estimate of $n$.

\iffalse The problem
is that all indices are involved in many violations in an interval of size $K$.
To get a good estimate to the LIS the algorithm must, for most of the decreasing intervals
of size $K$, classify one (and only one)
of the indices in the interval as good.
\fi

If we abstract away the details from this algorithm we see that an index $i$ is classified based on
an $log(n)^{O(1)}$ size sample of indices where the probability that an index $j$ is in the sample is roughly proportional
to $1/|j-i|$.   Call this a {\em sparse proximity-based sample}. It is natural to ask whether there is a better way to use this sample to classify $i$.
The following example shows that there is a strong limitation on the quality of approximation that can be provided by
a classification algorithm based on a sparse proximity-biased sample.
Set $n=64$ and divide the indices
into three contiguous blocks, where the first has size $r$, the second
has size $2r$ and the third has size $3r$.  Consider the sequence $f$ whose
first block is $100r+1,\ldots,101r$,
whose second block is
$1,101r+1,2,101r+2,\ldots, r,101r$
and whose third block is some increasing
subsequence  of
$r+1,\ldots,99r$.  Let $f'$ be a sequence that
agrees with $f$ on the first two blocks. The
final $3r$ positions is some sequence with values in the range
$r+1,\ldots,99r$ but looks like the function in \Fig{func1}.
Refer to \Fig{funcprob} for a pictorial representation
of these sequences.

Notice that in classifying an index $i$ in the first block, a sparse proximity-based is unlikely to be able
to distinguish $f$ from $f'$ and so it will classify $i$ as good or bad the same in both cases.
The LIS of $f$ has size $4r$ (and excludes the first block
of elements) and an increasing sequence that uses any element from the first block has size
at most $2r$.  Hence the algorithm must classify indices $i$ as bad, or incur an additive $2r=n/3$ error.
On the other hand,  the LIS for $f'$ has size $2r$ (and includes all indices in the first block),
and if the algorithm classifies such indices as bad then the algorithm will classify at most $r$ indices as good
and the additive error will be at least $r=n/6$.

Roughly speaking, this example shows that for a classification algorithm that provides better than an $n/6$
approximation, the classification of an index $i$ may involve small scale properties of the sequence
far away from $i$.
Since one can build
many variants of this example, where the size and location of the
critical block is different, and the important scale within the critical
block may also vary, it seems that very global information at all scales
may be required to make a satisfactory decision about any particular index.

\begin{figure}[tb]
  \centering
 \includegraphics[width=1\textwidth]{figures/func-f.pdf}
    \caption{{The sequences/functions $f$ and $f'$ where small scale properties in one block affect
	points of a distant block}\label{fig:funcprob}}\hfill\break
\end{figure}
Another perspective is to consider the dynamic program that computes
the LIS.  The dynamic program starts by building and storing
small increasing sequences. Eventually it tries to join them to build
larger and larger sequences. Any one of the currently stored increasing
sequences may extend to
the LIS, while the others may turn out to be incompatible with any
increasing sequence close in size to the LIS.
Deciding among these alternatives requires accurate knowledge of
how partial sequences all over the sequence fit together.
Any sublinear time algorithm that attempts to
approximate the LIS arbitrarily well has to be
able to (in some sense) mimic this.

\section{The algorithmic idea and intuition} \label{sec-intuit}

In this section we give an overview of the algorithm.
It is convenient to identify the array/function $f$ with the set
of points $\{\langle i,f(i) \rangle: i \in [n]\}$ in $\mathbb{R}^2$. We take the natural partial order where $\langle a_1,a_2 \rangle \preceq \langle b_1,b_2 \rangle$
if and only if $a_1 \leq b_1$ and $a_2 \leq b_2$.
The LIS corresponds to the longest chain in this partial order.
The axes of the plane will
be denoted, as usual, by $x$ and $y$. We use \emph{index interval} to denote
an interval of indices, and typically denote such an interval by the notation $(x_L,x_R]$
which is the set of indices $x$ satisfying $x_L<x \leq x_R$.  The {\em width} of
an interval $I=(x_L,x_R]$, denoted ${\bf {\rm  w}}(I)$ is the number $x_L-x_R$ of indices it contains.
We use \emph{value} to denote $y$-coordinates.  Intervals of values
are denoted by closed intervals $[y_L,y_R]$.   A {\em box} ${\cal B}$ is a Cartesian product
of an index interval and value interval.  The width of box, ${\bf {\rm  w}}({\cal B})$,
is the width of the corresponding index interval.
We write $X({\cal B})$ for the index set of ${\cal B}$.

\subsubsection*{An interactive protocol}

The first idea, which takes its inspiration from complexity theory,
is to consider an easier problem, that of giving an
\emph{interactive protocol} for proving a lower bound on ${\tt lis}_f$. (Note that
we will not make any mention of these protocols in the
actual algorithm or in any proof but they provide a useful intuition to keep in mind.)
Suppose that we have a sequence $f$
and two players, a prover and verifier. The prover
has complete knowledge of $f$  and the verifier has query access to $f$.
The prover makes a claim of the form ${\tt lis}_f \geq b n$ for
some $b \in (0,1)$.
The verifier wishes to check this claim
by asking the prover questions and querying $f$ on a small
number of indices.
At the end of the interaction, the verifier either accepts or rejects and we require
the following (usual) properties. If ${\tt lis}_f \geq b n$, then
there is a strategy of the prover that makes the verifier accept with high
probability. If the prover is lying and ${\tt lis}_f < (b -\delta)n$, then for any strategy of the
prover it is unlikely that the verifier will accept.

The protocol consists of $R$ rounds.  In each round the verifier either accepts or rejects the round, and the round
is designed to have the following properties: (1) If the LIS has size at least $bn$ then the prover can make the verifier
accept with probability at least $b$.  (2) If the LIS has size less than $(b-\delta)n$, then no matter how the prover
behaves the verifier will accept the round with probability less than $(b-\delta)$.
After performing the $r$ rounds, the verifier will then accept
the prover's claim if the number of accepted rounds is at least $(b-\frac{\delta}{2})R$.  A standard application of the
Chernoff-Hoeffding bound then gives that for $R=\Omega(\log n)$, with high probability the verifier will accept if
the LIS size is at least $bn$ (and the prover follows the protocol) and will reject if the LIS size is at most $(b-\delta)n$.

\begin{figure}[tb]
  \centering
 \includegraphics[width=0.25\textwidth]{figures/protocol.pdf}
    \caption{The interactive protocol: if $P$ is in the light gray regions, the verifier rejects. In this case,
    $P \prec S_j$, leading to ${\cal B}_{j+1}$ as shown in dark gray.}
  \label{fig:prot}
\end{figure}

So now we describe how a single round works.  the verifier (secretly) selects an index $i$ uniformly at random from  $(0,n]$.
Let $F(i) = \langle i,f(i) \rangle$.
The prover and verifier jointly generate a nested sequence ${\cal B}_1 \supset \cdots \supset {\cal B}_k$ of boxes
all containing $F(i)$
and a sequence $S_1,\ldots,S_k$ of points. For all $j$, $S_j$ is contained in ${\cal B}_j$.
At the beginning of the $j$th round, ${\cal B}_1,\ldots,{\cal B}_j$ and $S_1,\ldots,S_{j-1}$
are already determined. (We initialize with ${\cal B}_1$ as a box
containing all input points.) Now, the verifier selects some point $S_j$ inside ${\cal B}_j$.
This is called a {\em splitter} for ${\cal B}_j$. The verifier compares $F(i)$ with $S_j$
and rejects if $F(i)$ is incomparable to $S_j$. (Refer to \Fig{prot}.) If $F(i) \preceq S_j$,
then the verifier declares ${\cal B}_{j+1}$ to be the box formed by the bottom-left corner of ${\cal B}_j$ and $S_j$.
If $F(i) \succ S_j$, then ${\cal B}_{j+1}$ is the box formed by $S_j$ and the top-right corner of ${\cal B}_j$.
This ends the $j$th round.
If this process finally leads to a box ${\cal B}_k$ containing the single point $F(i)$, then
the verifier accepts the index $i$.

Suppose ${\cal L}$ is some LIS. The prover can make the verifier accept whenever $F(i)$ belongs to ${\cal L}$
by always selecting $S_i$ so that $S_i \in {\cal L} \cap {\cal B}_i$.  (Note that at each step the set ${\cal L} \cap {\cal B}_i$
is an LIS for the box ${\cal B}_i$.) We leave it to the reader to show that
the prover cannot make the verifier to accept with probability higher than $|{\cal L}|/n = {\tt lis}_f/n$.

The number of rounds of the protocol depends on how \emph{balanced} the splitters
selected by the prover are.   A splitter $S_i$ is $\rho$-balanced in ${\cal B}_i$ if
it does not belong to the leftmost or rightmost $\rho$ fraction of points of ${\cal B}_i$,
which ensures that each successive box is reduced in size by a factor $1-2\rho$. This would bound the number of rounds
by $O(\log n/\rho)$.  We require that the prover select a $\rho$-balanced splitter for some $\rho=\Theta(\delta)$ (if there
is such a splitter) and halt otherwise.  Iimposing the $\rho$-balance requirement on the prover can decrease the probability
of convincing the verifier by at most $\Theta(\rho)$).

\subsubsection*{Algorithmically searching for a splitter}

Can we  simulate this protocol by an algorithm?  At first glance this seems impossible, since the prover has complete knowledge
 of the array, while the algorithm must ``pay" for any information.

At each step, the all-knowing prover selects a $\rho$-balanced splitter in the current box that belongs to the LIS within that box.
Since our algorithm does not know the LIS, it seems impossible to simulate this.  But since we are only
doing an approximation, we do not need the splitter to be on the LIS, we only need that the splitter
belongs to an increasing sequence that is close to the LIS.  How can we recognize such a splitter?

Let ${\cal B}_j$ be the current box being split and ${\cal L}_j$ be the LIS of ${\cal B}_j$.
We say that an input point $P$ is a \emph{violation} with a splitter $S$
if they are incomparable. A good splitter is one which is a violation
with few points in ${\cal L}_j$.
How few?  If
we can guarantee that the number of violations of the LIS with the splitter
is at most $\gamma {\bf {\rm  w}}({\cal B})$, then the total error will be $\gamma {\bf {\rm  w}}({\cal B})$ times the number
of rounds which is $O(\log n/\rho)$.  The overall error will be a small fraction of ${\bf {\rm  w}}({\cal B})$ if
$\gamma$ is a small fraction of $\rho/\log n$.

It will be convenient in this informal discussion to assume that splitters are not necessarily input point (although it turns
out that our algorithm will restrict its search for splitters to input points).
We do not know what ${\cal L}_j$ is, so we look for a splitter $S$ with
a much stronger property: $S$ has a total of $\gamma {\bf {\rm  w}}({\cal B})$ (input point) violations in ${\cal B}_j$.
We call this a {\em conservative} splitter.  This is a stronger requirement than what is needed for a good splitter because it includes
violations of the splitter with points that are not on the LIS.    If we can find a conservative splitter, it is safe to use it
as the splitter in the interactive proof.  Whether a candidate point is a conservative splitter for box ${\cal B}_j$ can be quickly (approximately) checked by estimating
the fraction of violations that $i$ has within ${\cal B}_j$ by examining a small random sample of
indices from ${\cal B}_j$.    Furthermore, if a non-trivial fraction of points are
conservative splitters, then one can be found and identified quickly by random sampling.

Thus conservative splitters are easy to find (if there are enough of them)
and if one is found then we can use it to simulate the prover.
Of course, there may not be enough conservative splitters for the random search algorithm to succeed; indeed there
may be no conservative splitters.
A new idea is required to deal with this problem:
boosting the quality of the approximation.

\subsubsection*{Boosting the quality of approximation}

Let us restart our quest for an algorithm from a different starting point:
Given an algorithm that guarantees an additive $\delta n$-approximation to ${\tt lis}_f$,
can we use it to get an additive $\delta'$-approximation for some
smaller $\delta'$?  If we could, then by using the known
additive $1/2$-approximation algorithm as a starting point,
we might be able to apply this error reduction method recursively to
achieve any desired error.

Consider the following divide-and-conquer dynamic program for
estimating the LIS of points in a box ${\cal B}$.
Fix $s$ to be some (balanced) index in ${\cal B}$.
Let $y$ be the value of some point in ${\cal B}$ and set $P = \langle s,y\rangle$.
By varying $y$, we get different points $P$.
Define the box ${\cal B}_{L}(P)$ formed by the bottom-left corner of ${\cal B}$ and $P$.
Analogously, ${\cal B}_{R}(P)$ is formed by $P$ and the top-right corner of ${\cal B}$.
Observe that ${\tt lis}({\cal B}) = \max_P \{{\tt lis}({\cal B}_{L}(P)) + {\tt lis}({\cal B}_{R}(P))\}$.
This recurrence can be viewed as a  dynamic program for ${\tt lis}({\cal B})$.
Let ${\tt alis}({\cal B}_{L}(P))$ and ${\tt alis}({\cal B}_{R}(P))$ denote estimates obtained by running our
base approximation algorithm on ${\cal B}_{L}(P)$ and ${\cal B}_{R}(P)$. We can maximize ${\tt alis}({\cal B}_{L}(P))+{\tt alis}({\cal B}_{R}(P))$ over $P$
to get
an approximation for ${\tt lis}({\cal B})$
While it is too costly to search over all points $P$,
a good approximation can be obtained by maximizing over a polylogarithmic
sample from the points in ${\cal B}$. For the sake of this discussion, we will
assume that the true maximizer $P^*$ can be determined.
We denote the corresponding boxes ${\cal B}_{L}(P^*)$ and ${\cal B}_{R}(P^*)$ by ${\cal B}_L$ and ${\cal B}_R$.

An initial analysis suggests that we gain nothing from this.
If ${\tt alis}({\cal B}_L)$ is a $\delta {\bf {\rm  w}}({\cal B}_L)$-additive approximation and ${\tt alis}({\cal B}_R)$
is a $\delta {\bf {\rm  w}}({\cal B}_R)$-additive approximation then the best we can say is
that the sum is an additive $\delta ({\bf {\rm  w}}({\cal B}_L)+{\bf {\rm  w}}({\cal B}_R))=\delta {\bf {\rm  w}}({\cal B})$
approximation to ${\tt lis}({\cal B})$, so we get no advantage.

However, if we make a subtle change in the notion of additive error, then
an advantage emerges.
Instead of measuring the additive approximation error
as a multiple of ${\bf {\rm  w}}({\cal B})$, we measure it as a multiple of ${\tt loss}({\cal B})=|{\cal B} \cap {\cal F}|-{\tt lis}({\cal B})$, where ${\cal F}=
\{F(i):i \in [n]\}$ is the set of input points.
Note that in general ${\tt loss}({\cal B})$
may be much smaller than ${\bf {\rm  w}}({\cal B})$.  So suppose we have an algorithm that
whose approximation error is at most $\tau {\tt loss}({\cal B})$.
Then the additive error of ${\tt alis}({\cal B}_L)+{\tt alis}({\cal B}_R)$ will be at most
$\tau ({\tt loss}({\cal B}_L)+{\tt loss}({\cal B}_R))$, which may be significantly  less than $\tau {\tt loss}({\cal B})$.
If this can be bounded above by $\tau' {\tt loss}({\cal B})$ for some $\tau'<\tau$,
the quality of approximation can be boosted.

The nice surprise is that
${\tt loss}({\cal B})-({\tt loss}({\cal B}_L)+{\tt loss}({\cal B}_R))|
= |{\cal B}\cap {\cal F}| - (|{\cal B}_L \cap {\cal F}| + |{\cal B}_R\cap {\cal F}|)$. This quantity is precisely the number of
points in ${\cal B} \cap {\cal F}$ that are in violation with $P^*$.  This gives the following dichotomy: if the number of such violations is at least
$\mu |{\cal B} \cap {\cal F}|$ then we can take $\tau'$ to be $(1-\mu)\tau$ and boost the quality of approximation from $\tau$
to $\tau'$. Otherwise, the number of violations is less than $\mu |{\cal B}|$ and $P^*$
is  a conservative splitter!

It is not clear how to apply this dichotomy to interleave the simulation of the interactive protocol
and the boosting idea to  get an algorithm.
But there is a more significant difficulty.
In the search for a good splitter we measured the number of violations
as $\gamma {\bf {\rm  w}}({\cal B})$ and argued that $\gamma$ should be $O(1/\log n)$.
For the recursive boosting to
work efficiently, we measured the quality of the splitter by $\mu |{\cal B}|$
and for this we need $\mu$ to be at least $\Omega(1/\log\log n)$.
Why? For each level of recursion, we can improve the
additive approximation from $\tau$ to $\tau(1-\mu)$.
So we will need $1/\mu$ levels of
recursion to improve from $\delta$ to $\delta/2$.
At each level of the recursion, we make at least $2$
recursive calls, for the left and right subproblems
generated by any choice of a splitter. So the total number of iterated recursive calls
is exponential in $1/\mu$.  Since we want the running time to be $\log(n)^{O(1)}$, this  leads to $\mu = \Omega(1/\log\log n)$.

For the interactive protocol simulation, splitters can have at most
$O(|{\cal B} \cap {\cal F}|/\log n)$ violations inside ${\cal B}$, and for the boosting algorithm
every (or nearly every) splitter has $\Omega(|{\cal B} \cap {\cal F}|/\log\log n)$
inside ${\cal B}$.
So while the dichotomy seems promising, we have
a huge gap from an algorithmic perspective.

\subsubsection*{Closing the dichotomy gap}

We seek ways to close the gap in this dichotomy.
Upon further consideration (and using past work in the area as a guide),
it seems fruitful to modify the criterion for a good splitter.
For a candidate splitter $P$ we relax the condition on the maximum number
of violations $\gamma {\bf {\rm  w}}({\cal B})$ to $\mu|{\cal B} \cap {\cal F}|+ \gamma {\bf {\rm  w}}({\cal B})$,
where $\gamma$ will be $1/\textrm{poly}\log n$ and $\mu$ will be a small constant.
(We strengthen this requirement by requiring that a similar
condition holds for various subboxes of ${\cal B}$.)
Note that this condition is weaker than the original condition on splitters.
But we prove that it is good enough to simulate the
interactive protocol.

Now for the other side of the dichotomy. Even if there is no good splitter
satisfying this weaker condition, the above divide-and-conquer
scheme might still fail to boost the quality of approximation.
The  boosting algorithm uses an index $s$
to divide the box ${\cal B}$ into two parts and then searches over different $y$ to maximize
${\tt alis}({\cal B}_L)+{\tt alis}({\cal B}_R)$.  This is essentially solving a longest path problem on
a 3-layer DAG.  In the modified boosting algorithm we do analogous thing,
but where we divide the box
into a larger number of parts and solve a longest path problem on a DAG with more layers.
The number of layers turns out to be $1/\gamma$, where $\gamma$ is
the parameter in the relaxed definition of splitter.

\iffalse

\begin{figure}[tb]
	\centering
  \psfrag{I}{$I$} \psfrag{I1}{$I_1$} \psfrag{I2}{$I_2$} \psfrag{It}{$I_s$}
  \psfrag{h1}{$h_1$} \psfrag{h2}{$h_2$} \psfrag{h3}{$h_{s-1}$}
  \psfrag{H0}{$H_0$} \psfrag{H1}{$H_1$} \psfrag{H2}{$H_2$} \psfrag{Hr}{$H_{s-1}$} \psfrag{Hl}{$H_s$}
  \ \psfig{file=h.eps,width=6in}
	\ \caption{The figure to the left shows the placement of possible values $h_1,h_2,\ldots$. The
	black points for the LIS and the grey points correspond to the $h$ values.
	The figure to the right shows the construction of the graph
	$G$, and the layers of vertices $H_i$. The arrows give the directed edges from one
	vertex in layer $H_1$.}\label{fig-graph}\hfill\break
\end{figure}
\fi

These two ingredients - the simulation of the interactive protocol
and the modified boosting algorithm - are combined together
to give our algorithm.  There are various parameters such as $\alpha,\mu,\gamma$ involved
in the algorithm, and we must choose their values carefully. We also need to determine how many
levels of boosting are required to get a desired approximation.
A direct
choice of parameters leads to a $(\log n)^{1/\delta}$
approximation algorithm.
The better algorithm
claimed in \Thm{main} is obtained by a more delicate
version of the algorithm, which involves modifying the various parameters
as the algorithm proceeds.  This reduces
the number of recursive calls needed for boosting
from polylogarithmic in $n$ to a constant depending on $\delta$.

\section{Preliminaries}
\label{sec:prelim}
\subsection{Basic definitions}
\label{subsec:basic defs}

We write $\mathbb{N}$ for the set of nonnegative integers and $\mathbb{N}^+$
for the set of positive integers.   We typically use interval notation $[a,b]$ and $(a,b]$
to denote intervals of nonnegative integers.  Occasionally we also use interval notation
to denote intervals of real numbers; the context should make it clear which meaning is intended.

Throughout this paper $n$ is an arbitrary but fixed positive integer and we refer to the
set $(0,n]=\{1,\ldots,n\}$ as the {\em index set}.  We let $f$ denote a fixed arbitrary
function mapping $(0,n]$ to $\mathbb{N}^+$.
Occasionally,  we abuse notation and
view 0 as an index.
Also for convenience,
we assume that we are given an upper bound ${\tt valbound}$ on the maximum of $f$.
and define ${\rm range}(f)$ to be the set $[1,{\tt valbound}]$.

For $X \subseteq (0,n]$ we write $f(X)=\{f(x):x \in X\}$, and
for $Y \subseteq {\rm range}(f)$ we
write $f^{-1}(Y)=\{x \in [n]:f(x) \in Y\}$.

\begin{description}
\item [{\bf Points}]
As usual, $\mathbb{N}^2$ denotes the set of ordered
pairs of nonnegative integers, which we call {\em points}.
A point is denoted by $\point{a}{b}$ (rather than $(a,b)$, to avoid confusion
with interval notation).
The first coordinate of point $P$ is denoted
$x(P)$ and is called the {\em index of $P$}.  The second
coordinate of $P$ is denoted $y(P)$ is called the {\em value of $P$}.
We denote points by upper case letters, and
sets of points
by calligraphic letters.

\item[{\bf The sets  $X({\cal S})$ and $Y({\cal S})$}] For a set ${\cal S}$ of points, we write
$X({\cal S})$ for the set $\{x(P):P \in {\cal S}\}$ of indices of points
of ${\cal S}$, and
$Y({\cal S})$ for the set $\{y(P):P \in {\cal S}\}$
of values of points in ${\cal S}$.

\item[{\bf The point $F(x)$, the set ${\cal F}$, and ${\cal F}$-points}]
For $x \in (0,n]$, $F(x)$ denotes the point $\langle x,f(x)\rangle$.
We define ${\cal F}=\{F(x):x \in (0,n]\}$.
We refer to points in ${\cal F}$ as ${\cal F}$-points.

Observe that for
a set ${\cal S}$ of points, $F^{-1}({\cal S}) \subseteq X({\cal S})$ is the set of
indices $x$ for which $F(x) \in {\cal S}$.  Since $F$ is a 1-1 function
it follows that the sets $F^{-1}({\cal S})$ and ${\cal F} \cap {\cal S}$ are in 1-1 correspondence.

\item [{\bf Relations $P \leq Q$, $P \prec Q$, $P \searrow Q$, $P \mathpalette\superimpose{{\searrow}{*}} Q$ and   sets  $P^{NE}$, $P^{NW}$, $P^{SE}$,$P^{SW}$}]

For points $P,Q$,
\begin{description}
\item[$P \leq Q$] means
$x(P) \leq x(Q)$ and $y(P) \leq y(Q)$
\item[$P \prec Q$] means $x(P)<x(Q)$ and $y(P) \leq y(Q)$.
\item[$P \searrow Q$] means $x(P) < x(Q)$ and $y(P)>y(Q)$.
\item[$P \mathpalette\superimpose{{\searrow}{*}} Q$] means $x(P) \leq x(Q)$ and $y(P) > y(Q)$.
\end{description}

Observe that for points $P,Q$ with $x(P) \neq x(Q)$, for example, if $P,Q$ are distinct points of ${\cal F}$,
then the conditions $x(P) \leq x(Q)$ and $x(P) \prec x(Q)$ are equivalent,
and the conditions $P \searrow Q$ and $P \mathpalette\superimpose{{\searrow}{*}} Q$ are equivalent.

For a point $P$, we define the following sets. Refer to \Fig{position}.
\begin{description}
\item
[$P^{NW}$] (for northwest) The set of points $Q$ such that $Q \mathpalette\superimpose{{\searrow}{*}} P$.
\item
[$P^{SW}$] (for southwest) The set of points $Q$ such that $Q \leq P$.
\item
[$P^{NE}$] (for northeast) The set of points $Q$ such that $P \prec Q$.
\item
[$P^{SE}$] (for southeast) The set of points $Q$ such that $P \searrow Q$.

\end{description}

\begin{figure}[tb]
  \centering
 \includegraphics[width=0.25\textwidth]{figures/position.pdf}
    \caption{The various positions and sets relative to point $P$. $Q$ denotes a hypothetical point
    in the respective region.}
  \label{fig:position}
\end{figure}

There is an asymmetry in these definitions: For example one might expect that $Q \in P^{NE}$ would
be equivalent to $P \in Q^{SW}$ but this is not the case.
Notice that this asymmetry disappears if $x(P) \neq x(Q)$.
One reason to define the sets this way is so that for each point $P$, the sets
 $P^{NW}$,$P^{NE}$, $P^{SW}$, $P^{SE}$ partition $\mathbb{N}^2$.

\item[{\bf Relations $P \sim Q$ ($P$ is comparable to $Q$) and $P\not\sim Q$ ($P$ is a violation with $Q$)}]

For $P,Q \in {\cal F}$ we define:

\begin{description}
\item[$P \sim Q$] means that $P$ and $Q$ are {\em comparable}, i.e., $P \leq Q$ or $Q \leq P$ .
\item[$P \not\sim Q$] means that $P$ and $Q$ are a {\em  incomparable} or a {\em violation}, i.e., either $P \searrow Q$
or $Q \searrow P$ .
\end{description}
We emphasize that we only use these terms in the case that $P$ and $Q$ are ${\cal F}$-points.  Since ${\cal F}$-points have distinct indices,
the distinctions between $\leq$ and $\prec$, and between $\searrow$ and $\mathpalette\superimpose{{\searrow}{*}}$ disappear.

\item [{\bf Index  intervals}]   A set of consecutive indices  is called
an {\em index interval}.    An index interval is usually written using the notation
$(a,b]=\{a+1,\ldots,b\}$.
For an index interval $I$, we define indices $x_L(I)$
and $x_R(I)$, the {\em left and right endpoints of $I$} so that $I=(x_L(I),x_R(I)]$.
Note $x_R(I) \in I$ but $x_L(I) \not\in I$.

\item [{\bf Value intervals}]
A {\em value interval}
refers to an integer subinterval $[c,d]$ of ${\rm range}(f)$.
For value intervals we always use closed interval notation.
For a value interval $J$ we define indices $y_B(J)$
and $y_T(J)$, the {\em top and bottom endpoints of $J$}
such that $J=[y_B(J),y_T(J)]$.  Thus, in contrast with index intervals,
$J$ contains both of its endpoints.

\item[{\bf Box}]
A box ${\cal B}$ is the Cartesian product of a nonempty index interval
$I$ and a nonempty value interval $J$.

Using the notation described above, we have ${\cal B} = X({\cal B}) \times Y({\cal B})$,
$X({\cal B})=(x_L(X({\cal B})),x_R(X({\cal B}))]$, and $Y({\cal B})=[y_B(Y({\cal B}),y_T(Y({\cal B}))]$. To simplify notation we define
$x_L({\cal B})=x_L(X({\cal B}))$ and analogously $x_R({\cal B}), y_B({\cal B}), y_T({\cal B})$.
Thus $X({\cal B})=(x_L({\cal B}),x_R({\cal B})]$ and $Y({\cal B})=[y_B({\cal B}),y_T({\cal B})]$.
We also define the {\em bottom-left point of ${\cal B}$},
$P_{BL}({\cal B})=\point{x_L({\cal B})}{y_B({\cal B})}$
and the {\em top-right point of ${\cal B}$},  $P_{TR}({\cal B})=\point{x_R({\cal B})}{y_T({\cal B})}$.
(Note that under these definitions $P_{BL}({\cal B}) \not\in {\cal B}$ since
$x_L({\cal B}) \not\in X({\cal B})$.)

If $Q,R$ are points with $Q \prec R$, the
{\em box spanned by $Q,R$}, denoted $Box(Q,R)$ is the box having $P_{BL}({\cal B})=Q$ and $P_{TR}({\cal B})=R$.
It is easy to see that
$Box(Q,R)=
\{P:Q \prec P \leq R\}$

\item[{\bf Grids}]
A {\em grid} $\Gamma$ is any Cartesian product $I \times J$ where
$I$ is a set of indices and $J$ is a set of values.  Thus
$\Gamma$ is a grid if and only if $\Gamma = X(\Gamma) \times Y(\Gamma)$.
A box is the special case of a grid in which both $X(\Gamma)$
and $Y(\Gamma)$ are intervals.

We refer to the sets of the form $\{x\} \times Y(\Gamma)$ for $x \in X(\Gamma)$ as
{\em columns of $\Gamma$} and sets of the form $X(\Gamma) \times \{y\}$ for $y \in Y(\Gamma)$
as {\em rows of $\Gamma$}.

\item[{\bf The universe ${\cal U}$ and the universal grid $\Gamma({\cal U})$}]  The {\em universe ${\cal U}$}  is  the box $(0,n] \times {\rm range}(f)$.
The {\em universal grid} is the grid $(0,n] \times F(0,n]$.  This is the smallest grid that contains ${\cal F}$, and its
size is at most $n^2$.  Every point that is encountered in any of our algorithms belongs to the universal grid.

\item[{\bf width}] The {\em width} of an interval $I$, denoted ${\bf {\rm  w}}(I)$, is $|I|=x_R(I)-x_L(I)$.
Similarly, for a box ${\cal B}$,
${\bf {\rm  w}}({\cal B})$ is equal to $|X({\cal B})|=
x_R({\cal B})-x_L({\cal B})$.

\item [{\bf Relation $\triangleleft$ on index intervals and boxes}]
\begin{itemize}
\item For index intervals $I_1,I_2$ we write $I_1 \triangleleft I_2$
if $x_R(I_1)=x_L(I_2)$.  It follows that $I_1 \cap I_2=\emptyset$
and $I_1 \cup I_2$ is
equal to the index interval $(x_L(I_1),x_R(I_2)]$.
In particular
this implies that $x_1 < x_2$ for all $x_1 \in I_1$ and $x_2 \in I_2$.
\item For boxes ${\cal B}_1,{\cal B}_2$ we write ${\cal B}_1 \triangleleft {\cal B}_2$ to mean
$P_{TR}({\cal B}_1)=P_{BL}({\cal B}_2)$.  This is equivalent to
$X({\cal B}_1) \triangleleft X({\cal B}_2)$ and $y_T({\cal B}_1)=y_B({\cal B}_2)$.
In particular,
this implies  ${\cal B}_1 \cap {\cal B}_2=\emptyset$ and $P_1 \prec P_2$ for all $P_1 \in {\cal B}_1$ and $P_2 \in {\cal B}_2$.
\end{itemize}

\item [{\bf Box sequences}]

A {\em box sequence} is a list of boxes such that each successive box is entirely to the right
of the previous.
We use the notation  $\vec{{\cal B}}$ to denote a box sequence.
We write ${\cal B} \in \vec{{\cal B}}$ to mean that the box ${\cal B}$ appears
in $\vec{{\cal B}}$.

\begin{figure*}[tb]
  \centering
  \subfloat[${\cal B}$-strip]{\includegraphics[width=0.35\textwidth]{figures/strip.pdf} \label{fig:strip}}
  $\qquad \qquad$
  \subfloat[Box chains]{\includegraphics[width=0.35\textwidth]{figures/boxchain.pdf} \label{fig:boxchain}}
    \caption{(a) ${\cal S}$ is a ${\cal B}$-strip. The figure also shows the strip ${\cal T} | {\cal B}$ for box ${\cal T}$.
    (b) The box chain $\vec{\cal T}$: The boxes ${\cal T}_1, {\cal T}_2, \ldots$ form a chain. The box $\vec{{\cal T}}[x]$
    is ${\cal T}_2$. The regions $\vec{{\cal T}}^{NW}$ and $\vec{{\cal T}}^{SE}$ are shaded.}
\end{figure*}

\item [{\bf ${\cal B}$-strips and ${\cal B}$-strip decompositions}]

If ${\cal B}$ is a box, a ${\cal B}$-strip is a subbox ${\cal S}$ of ${\cal B}$ such that $Y({\cal S})=Y({\cal B})$.  Thus
a ${\cal B}$-strip has the same vertical extent as ${\cal B}$ and is specified relative to ${\cal B}$
by its index set $X({\cal S})$.
If $I \subseteq X({\cal B})$ is an index interval then $\strip{I}{{\cal B}}$
denotes the ${\cal B}$-strip with index set $I$.  Similarly if ${\cal T}$ is a subbox of ${\cal B}$
then $\strip{{\cal T}}{{\cal B}}$ denotes the strip $\strip{X({\cal T})}{{\cal B}}$.
Refer to \Fig{strip}.

A ${\cal B}$-strip decomposition is a partition of ${\cal B}$ into strips.
A ${\cal B}$-strip decomposition into $r$ strips is specified by a sequence $x_0=x_L({\cal B}) < x_1 < \cdots < x_r = x_R({\cal B})$,
where the $j$th strip is $\strip{(x_{j-1},x_j]}{{\cal B}}$.   We use the sequence notation $\vec{{\cal S}}$ to denote a ${\cal B}$-strip decomposition
in the  natural left-to-right order.

In particular if $\Gamma \subset {\cal B}$ is a grid then $\Gamma$ naturally defines
a strip decomposition of ${\cal B}$ obtained by taking the strips that end at successive columns
of $\Gamma$ with the final strip ending at $x_R({\cal B})$.

\item [{\bf Increasing point sequences} and {\bf Box Chains}]

A set of points ${\cal P}$ that can be ordered so that
$P_0 \prec \cdots \prec P_k$ is called an {\em increasing point sequence} or simply {\em increasing sequence}.
If ${\cal S}$ is a set of points then an ${\cal S}$-increasing point sequence is an increasing sequence
whose points all belong to ${\cal S}$.

A {\em box chain} $\vec{{\cal T}}$ is a box sequence $\vec{{\cal T}}=({\cal T}_1,\ldots,{\cal T}_k)$
satisfying ${\cal T}_1 \triangleleft \cdots \triangleleft {\cal T}_k$. Refer to \Fig{boxchain} for
the following definitions.
\begin{itemize}
\item
There is a one-to-one correspondence between increasing point sequences
and box chains which maps the increasing sequence ${\cal P}$ with points
$P_0 \prec P_1 \prec \ldots \prec P_k$  to the box chain
$\vec{{\cal T}}$ given by $Box(P_0,P_1) \triangleleft \cdots \triangleleft Box(P_{k-1},P_k)$.
We refer to  ${\cal P}$ as the {\em increasing sequence associated to box chain $\vec{{\cal T}}$}.
If $\vec{{\cal T}}$ is a box chain, we write ${\cal P}(\vec{{\cal T}})$ for the associated  increasing point sequence
and ${\cal P}^{\circ}(\vec{{\cal T}})$ for the {\em interior increasing sequence associated to $\vec{{\cal T}}$},
which excludes the first and last points $P_0$ and $P_k$.

\item
The box $Box[\vec{{\cal T}}]$ spanned by $\vec{{\cal T}}$ is the smallest
box containing $\vec{{\cal T}}$.  If $P_0,\cdots,P_k$ is the increasing point sequence associated
to $\vec{{\cal T}}$ then $Box[\Vec{{\cal T}}]=Box(P_0,P_k)$.
\item If $\vec{{\cal T}}$ spans box ${\cal B}$ then for each $x \in X({\cal B})$ there is a unique box
${\cal T} \in \vec{{\cal T}}$ such that $x \in X({\cal T})$.  This box is denoted $\vec{{\cal T}}[x]$
\item
Given a strip decomposition $\vec{{\cal S}}$ of ${\cal B}$, a box chain
$\vec{{\cal T}}$ is {\em compatible with $\vec{{\cal S}}$} if $\vec{{\cal S}}$ is composed of strips
$\strip{{\cal T}}{{\cal B}}$  for ${\cal T} \in \vec{{\cal T}}$.  In this case, the box spanned by $\vec{{\cal T}}$
has the form $X({\cal B}) \times Y'$ where $Y' \subseteq Y({\cal B})$.
\item  If $\vec{{\cal T}}$ is a box chain spanning box ${\cal B}$,
then $\vec{{\cal T}}$ naturally defines a partition of ${\cal B}$ into three
sets: $\vec{{\cal T}}^{\cup}$,
$\vec{{\cal T}}^{NW}$ (for northwest) and $\vec{{\cal T}}^{SE}$ (for southeast),
where:
\begin{itemize}
\item
$\vec{{\cal T}}^{\cup}=\bigcup_{{\cal T} \in \vec{{\cal T}}} {\cal T}$.  Equivalently, $\vec{{\cal T}}^{\cup}={\cal B} \cap  \bigcap_{P \in {\cal P}(\vec{{\cal T}})} (P^{SW} \cup P^{NE})$.
\item
$\vec{{\cal T}}^{NW}={\cal B} \cap \bigcup_{P \in {\cal P}(\vec{{\cal T}})}P^{NW}$.
\item
$\vec{{\cal T}}^{SE}={\cal B} \cap \bigcup_{P \in {\cal P}(\vec{{\cal T}})}P^{SE}$.
\end{itemize}
\end{itemize}
\iffalse
\item{\bf $(x_0,\ldots,x_k)$-sequence and $(x_0,\ldots,x_k)$-box chain}.
Given an index path $x_0,\ldots,x_k$, we say that a
increasing sequence $P_0,\ldots,P_k$ is an {\em $(x_0,\ldots,x_k)$-path}
if $x(P_i)=x_i$ for each $i \in \{0,\ldots,k\}$ and the
associated box chain is an {\em $(x_0,\ldots,x_k)$-box chain}.
\item
{\bf $In({\cal B}),Out({\cal B}),{\tt in}({\cal B}),{\tt out}({\cal B}),In(\vec{{\cal B}}),
Out(\vec{{\cal B}}),{\tt in}(\vec{{\cal B}}),{\tt out}(\vec{{\cal B})})$}
For boxes ${\cal B} \subset {\cal C}$ we define:
\begin{itemize}
\item $In({\cal B})=\{x \in X({\cal B}):F(x) \in {\cal S}\}$.
\item $Out({\cal B})=\{x \in X({\cal B}):F(x) not\in {\cal B}\}$.   Thus
$In({\cal B}),Out({\cal B})$ is a partition of $X({\cal B})$.
\item ${\tt in}({\cal B})=|In({\cal B})|$ and ${\tt out}({\cal B})=|Out({\cal B})|$.
Thus ${\tt in}({\cal B})+{\tt out}({\cal B})={\bf {\rm  w}}({\cal B})$.
\item $Out({\cal B}|{\cal C})=\{x \in X({\cal C}):F(x) not\in {\cal B}\}$.   Thus
$In({\cal B}),Out({\cal B}|{\cal C})$ is a partition of $X({\cal C})$.  Note that
$Out({\cal B})=Out({\cal B}|{\cal C})$.
\item ${\tt out}({\cal B}|{\cal C})=|Out({\cal B}|{\cal C})|$.  Thus ${\tt out}({\cal B}|{\cal C})+{\tt in}({\cal B})={\tt in}({\cal C})$.
\end{itemize}
\fi
\end{description}

\subsection{Increasing sequences and the functions {\tt lis}{} and {\tt loss}}

A set $X \subseteq (0,n]$ of indices is said to be {\em $F$-increasing} if the set
$F(X)=\{F(x):x \in X\}$ is an increasing point sequence.
For a box ${\cal B}$ we say that
$X$ is $(F,{\cal B})$-increasing if it is $F$-increasing and $F(X) \subseteq {\cal B}$.
If $\vec{{\cal B}}$ is a box chain we say that $X$ is
{\em $(F,\vec{{\cal B}})$-increasing} if it is $F$-increasing
and $F(X) \subseteq \vec{{\cal B}}^{\cup}$.

\begin{itemize}
\item ${\tt lis}({\cal B})={\tt lis}_f({\cal B})$ is the size of a
longest increasing (point) sequence (LIS) contained in ${\cal B}$,
which is also the size of the largest $(F,{\cal B})$-increasing set.
\item
${\tt loss}({\cal B})=|{\cal B} \cap {\cal F}|-{\tt lis}({\cal B})$, i.e. ${\tt loss}({\cal B})$ is the smallest number of ${\cal F}$-points in ${\cal B}$ that must
be deleted so that the remaining points of ${\cal B} \cap {\cal F}$ form an increasing sequence.
\end{itemize}

\subsection{The LIS approximation problem}

We develop an algorithm ${\rm {\bf ApproxLIS}}$ that takes as input a function $f$ and  box ${\cal B}$
and outputs an approximation ${\rm {\bf ApproxLIS}}({\cal B})$ to ${\tt lis}({\cal B})$.
The required quality of approximation is specified by input parameters $\overline{\tau}$ and $\overline{\delta}$.
The algorithm is recursive and calls itself with different choices of these input parameters.
To prevent confusion, the symbols $\overline{\tau}$ and $\overline{\delta}$ denote the initial setting,
while $\tau$ and $\delta$ are used to generically refer to these parameters in the algorithm.

In our analysis we will require a carefully chosen measure of the quality of
the estimate ${\rm {\bf ApproxLIS}}({\cal B})$.
For $\overline{\tau},\overline{\delta} \in (0,1)$ we say that ${\rm {\bf ApproxLIS}}$
is a {\em $(\overline{\tau},\overline{\delta})$-approximation to ${\tt lis}$ on box ${\cal B}$} provided that:

\[
|{\rm {\bf ApproxLIS}}({\cal B})-{\tt lis}({\cal B})| \leq \overline{\tau} {\tt loss}({\cal B}) + \overline{\delta} {\bf {\rm  w}}({\cal B}).
\]

A few remarks:

\begin{itemize}
\item A $(0,\overline{\delta})$-approximation is an
{\em additive $\overline{\delta} {\bf {\rm  w}}({\cal B})$-approximation}
to ${\tt lis}({\cal B})$.
Since ${\tt loss}({\cal B}) \leq {\bf {\rm  w}}({\cal B})$ a
$(\overline{\tau},\overline{\delta})$-approximation is also an additive
$(\overline{\tau}+\overline{\delta})$-approximation.
\item Our initial goal is to get a good additive approximation, so the reader may wonder why we introduce
the parameter $\overline{\tau}$.  Separating the error into these two parts is important for the analysis of our algorithm.
Our algorithm
is recursive. The value of $\tau$ in the base algorithm is very large (essentially infinite), but we have the freedom
to choose $\delta$ to be very
small.  Each level of recursion shrinks $\tau$, at the cost
of making $\delta$ larger.  By applying enough
recursive levels, we can make the final $\tau$ less than the desired bound of $\overline{\tau}$.
By starting with a small initial $\delta$, we can keep the final $\delta$ at most $\overline{\delta}$. This ensures
the final algorithm is a $\overline{\tau} + \overline{\delta}$-additive approximation.
\item We refer to the quantity $\tau {\tt loss}({\cal B})$ as the {\em primary error} and
to $\delta {\bf {\rm  w}}({\cal B})$ as the {\em secondary error}.
\end{itemize}

\section{The main theorems}
\label{sec:main}

We present two polylogarithmic time approximation algorithms for LIS, which we refer to as  the {\em basic algorithm}
and
the {\em improved algorithm}. The basic algorithm is somewhat simpler (though still fairly involved) while the improved algorithm
enhances the basic algorithm to give significantly better running time.  For the running time of the basic algorithm,
the exponent of $\log n$ is $\Theta(1/\overline{\tau})$.  For the improved version, the exponent of $\log n$ is a constant
independent of the error parameters $\overline{\tau}$ and $\overline{\delta}$.

\begin{theorem}
\label{thm:alg1}
 There is a randomized algorithm ${\rm {\bf BasicMain}}$ that:
\begin{itemize}
\item  takes as input an integer $n$, an array $f$ of length $n$ and an error parameter $\overline{\tau} \in (0,1)$,
\item  runs in time $(\log n)^{O(1/\overline{\tau})}$, and
\item outputs a value that, with probability at least $1-n^{-\Omega(\log n)}$, is a
{\em $(\overline{\tau},\frac{5}{\overline{\tau}\log n})$}-approximation to ${\tt lis}({\cal B})$.
\end{itemize}
\end{theorem}

Our improved algorithm gives:

\begin{theorem}
\label{thm:alg2}
 There is a randomized algorithm ${\rm {\bf ImprovedMain}}$ that:
\begin{itemize}
\item  takes as input an integer $n$, an array $f$ of length $n$ and  error parameters $\overline{\tau}, \overline{\delta} \in (0,1)$,
\item  runs in time $(1/\overline{\delta}\overline{\tau})^{O(1/\overline{\tau})}(\log n)^c$, and
\item outputs a value that, with probability at least $3/4$, is a
$(\overline{\tau}, \overline{\delta})$-approximation to ${\tt lis}_f$.
\end{itemize}
\end{theorem}

In the second theorem the probability of error is 1/4, as compared to $n^{-\Omega(\log n)}$ in the first.    It just happens that the analysis
of the first algorithm  gives a better error probability.  As we noted in the introduction, this difference
is not significant:
we can always reduce the error probability of the second algorithm to any desired $\eps>0$ by the standard trick of doing $O(\log(1/\eps)$
independent trials of the algorithm, and outputing the median of the trials.

We deduce \Thm{main} and \Thm{dist} from  \Thm{alg2}.

\iffalse
Since a $(\overline{\tau},\overline{\delta})$-approximation is also an additive $(\overline{\tau}+\overline{\delta})$-approximation,
\Thm{main} follows immediately by setting $\overline{\delta} = \overline{\tau}$ to be the half the desired error parameter.
\fi
\Thm{dist} requires a few calculations.

\begin{proof}[of \Thm{main}]
A $(\overline{\tau},\overline{\delta})$-approximation is also an additive $\overline{\tau}+\overline{\delta}$ approximation.  Given a desired additive error
$\delta$ in \Thm{main}, we set $\overline{\delta}=\overline{\tau}=\delta/2$ and run ${\rm {\bf ImprovedMain}}$. \Thm{alg2}
gives us the desired guarantee.
\end{proof}

\begin{proof}[of \Thm{dist}]
For convenience, we will assume that ${\rm {\bf ImprovedMain}}$ has an error of $n^{-\Omega(\log n)}$.
(Since we will make at most $\textrm{poly}(n)$ runs of ${\rm {\bf ImprovedMain}}$ and can union bound,
we henceforth assume no error.)
Suppose we run ${\rm {\bf ImprovedMain}}$ with parameters $\overline{\tau},\overline{\delta}$ and $a$ is the estimate.
Then, $|n-a - {\tt loss}_f| \leq \overline{\tau} {\tt loss}_f + \overline{\delta} n$.
We divide by $n$, note that $\varepsilon_f = {\tt loss}_f/n$ and denote $b = 1 - a/n$.
Hence, $b \in [\varepsilon_f(1-\overline{\tau}) - \overline{\delta}, \varepsilon_f(1+\overline{\tau}) + \overline{\delta}]$.
Rearranging, $\varepsilon_f \in [(b-\overline{\delta})/(1+\overline{\tau}),(b+\overline{\delta})/(1-\overline{\tau})]$.
For convenience, we denote this interval by $[b_1, b_2]$.

Our aim is to choose $\overline{\tau}$ and $\overline{\delta}$ such that $b_2/b_1 \leq (1+\tau)$.
Suppose we set $\overline{\tau} = q\cdot\tau$ and $\overline{\delta} \leq q\cdot\overline{\tau}\varepsilon_f$,
for some sufficiently small absolute constant $q$. Then,
\begin{eqnarray*}
	\frac{(b+\overline{\delta})/(1-\overline{\tau})}{(b-\overline{\delta})/(1+\overline{\tau})}
	= \frac{(b+\overline{\delta})(1+\overline{\tau})}{(b-\overline{\delta})(1-\overline{\tau})}
	& \leq & \frac{(\varepsilon_f(1+\overline{\tau}) + 2q\cdot\overline{\tau}\varepsilon_f)(1+\overline{\tau})}{(\varepsilon_f(1-\overline{\tau})-2q\cdot\overline{\tau}\varepsilon_f)(1-\overline{\tau})} \\
	& \leq & \frac{(1+q(1+2q)\tau)(1+q\tau)}{(1-q(1-2q)\tau)(1-q\tau)} \leq 1+\tau.
\end{eqnarray*}

But the value of $\varepsilon_f$ is not known in advance. We fix $\overline{\tau} = q\cdot\tau$
and run ${\rm {\bf ImprovedMain}}$ iteratively
where the value of $\overline{\delta}$ during the $j$th run is $\overline{\tau}/2^j$.
The algorithm will terminate before $\overline{\delta} \leq q\cdot\overline{\tau}\varepsilon_f/2$.
The running time is dominated by that of the last iteration,
which is $(1/\tau \varepsilon_f)^{O(1/\tau)}(\log n)^c$.
\end{proof}

\section{Algorithmic and analytical  building blocks}
\label{sec:blocks}
We present some procedures  used in  our algorithms, and some analytic tools we'll need.
First we establish some conventions and review  basic tail bounds that will be useful in analyzing the use of randomness in our algorithms
We define the notion of a good {\em splitter} of a box and present a subroutine for finding
splitters.  We present the important {\em dichotomy lemma} that roughly says: if there are few good splitters in a box ${\cal B}$
then ${\tt loss}({\cal B})$ must be a non-trivial fraction of $|{\cal B} \cap {\cal F}|$.
We present a simple subroutine that given a box constructs a grid inside it that is suitably representative of the box.
\subsection{Conventions for random bits}
\label{subsec:random}

Random sampling is needed  in the following procedures:

\begin{itemize}
\item
The procedures ${\rm {\bf FindSplitter}}$, ${\rm {\bf BuildGrid}}$ which are presented later in this section.
We refer to the random bits used
in these procedures as {\em secondary random bits}.
\item
The main procedure ${\rm {\bf ApproxLIS}}$ which is presented in \Sec{first algorithm}.
The random bits used in this procedure are called
the {\em primary random bits}.
\end{itemize}

All procedures depend on the function $f$. We treat the function $f$ as fixed, so the dependence on $f$ is implicit.
The other arguments to these procedures are boxes, indices, and auxiliary precision and error parameters.
We can enumerate the possible arguments to each of these procedures.
Indices have $n$ possible values, and boxes always have their corners on the universal grid, so there are at most
$n^4$ of them.  The auxiliary parameters will be from a restricted set of size at most $((\log n)/\tau)^{O(1)}$ where
$\tau$ is the primary error parameter.

For purposes of analysis, we imagine that  before running the algortihm we pregenerate
all of the random bits needed for each procedure and each possible set of arguments for the procedure,
Once all of these bits are (conceptually) fixed, the running of the algorithm
is deterministic.   This viewpoint has three advantages for us.

\begin{enumerate}
\item In our overall algorithm, the same procedure may be called multiple times with the same arguments. For each
such call, we use the \emph{same sequence of random bits}, as generated at the outset of the algorithm.
Therefore, every such duplicate
call produces the same output.
\item The randomized procedure ${\rm {\bf Classify}}$ (defined in Section) will itself be run on a few randomly chosen indices.
In the analysis, we need to reason about the output of ${\rm {\bf Classify}}$
on all inputs, not just the ones evaluated by the algorithm. By generating random bits for every possible call
to a procedure, the output of ${\rm {\bf Classify}}$ can be seen as fixed on all possible inputs.
If the random bits were not fixed in advance, then the output of ${\rm {\bf Classify}}$ on a new input
is a random variable.  Both points of view lead to the same mathematical conclusions,
but viewing the randomness as fixed from the  beginning simplifies the analysis.
\item In the analysis, we identify some useful (deterministic) assumptions of the ensemble of all of the random bits.
The main analysis
shows that if the ensemble of random bits satisfies these assumptions,
then the output of our algorithm is guaranteed to have the right properties. This involves no probabilistic reasoning.
Probabilistic arguments are only required to show that these two assumptions
hold with very high probability over the choice of the ensemble of random bits.
\end{enumerate}

The pre-generation of random bits is, of course, simply an analytical
device.  Since we want our algorithm to be fast, we cannot afford
to generate all  of bits in advance. So
we generate random bits only as we need them, and only for those choices of parameters to procedures that actually arise.  Once we evaluate
a procedure with a given set of arguments, we record the input parameters and output. If the same procedure is called again
with the same arguments, we return the same value.    It is evident that this online approach to generating randomness produces the same
distribution over executions and outputs as the inefficient offline approach. Hence, we execute the online algorithm,
but use the offline viewpoint for analysis.

\subsection{Tail bounds for sums of random variables}
\label{subsec:tail}

We recall a version of the Chernoff-Hoeffding bound for sums
of random variables:

\begin{prop}
\label{prop:hoeff1}
\cite{Ho63}
Let $X_1,\ldots,X_n$ be independent random variables with $X_i \in [a_i,b_i]$
and $\mu_i=\mathbb{E}[X_i]$ and $\mu=\sum_i \mu_i$.  Then for any $T>0$:
\begin{eqnarray*}
{\rm Pr}[\sum_i X_i - \mu \geq T] & \leq & e^{-2T^2/\sum_i (b_i-a_i)^2}\\
{\rm Pr}[\sum_i X_i - \mu \leq -T] & \leq & e^{-2T^2/\sum_i (b_i-a_i)^2}.
\end{eqnarray*}

\end{prop}

A standard application of is to bound
the probability of error when estimating the size of a subpopulation within
a given population.
For a finite set $X$,  a {\bf random sample of
size $m$ from a set $X$} means a sequence
$x_1,\ldots,x_m$ of elements each drawn uniformly and independently  from $X$.

\begin{prop}
\label{prop:hoeff2}
Let $X$ be an index interval and $\gamma \in [0,1]$ and
$s \in \mathbb{N}^+$.
Let $A \subseteq X$ be fixed.
For a random sample  $x_1,\ldots,x_s$ from $X$,
let $r$ denote the fraction of points
that belong to $A$.
Then
$\Pr[|r - \frac{|A|}{|X|}| \geq \gamma] \leq 2e^{-2\gamma^2s}$.
\end{prop}

We will also need the following upper tail bound:

\begin{prop}
\label{prop:cher} (Theorem 1, Eq. (1.8) in~\cite{DuPa})
Let $X = \sum_i X_i$, where $X_i$'s are independently distributed in $[0,1]$.
If $T > 2e\hbox{\bf E}[X]$, then ${\rm Pr}[X > T] \leq 2^{-T}$.
\end{prop}

\subsection{Splitters and the subroutine ${\rm {\bf FindSplitter}}$}
\label{subsec:splitters}

A basic operation in our algorithm is to take a box ${\cal T}$ and choose an index $s \in F^{-1}({\cal T})$, that is used
to ``split'' the box ${\cal T}$ into the two boxes $Box(P_{BL}({\cal T}),F(s))$ and $Box(F(s),P_{TR}({\cal T}))$.
This gives a box chain of size two spanning ${\cal T}$.
For this reason, the index $s \in F^{-1}({\cal T})$ is called a {\em splitter} for ${\cal T}$; we also refer to
the point $\langle s,f(s) \rangle$ as a splitter.   Note that $s>x_L({\cal T})$ for all $s \in F^{-1}({\cal T})$ and therefore
 $Box(P_{BL}({\cal T}),F(s))$ is always a nonempty box.
It could happen that $s = x_R({\cal T})$, in which case $Box(F(s),P_{TR}({\cal T}))$ is a trivially empty box.
In this case we say that the splitter
 is {\em degenerate};  any other splitter is said to be  {\em nondegenerate}.

We give a subroutine that, given a pair of boxes ${\cal T} \subseteq {\cal B}$,
looks for a ``useful" splitter $s$ for ${\cal T}$ with $F(s) \in {\cal T}$.
We require a splitter to be \emph{balanced} and \emph{safe} (in a precise sense to be specified).  Roughly,
a balanced splitter is not too close to either the  left or right edge of ${\cal T}$ (and in particular is not degenerate).
A splitter is safe if most ${\cal F}$-points of $ \strip{{\cal T}}{{\cal B}}$ are comparable to $F(s)$.

The definitions in this section are inspired by the classic ideas of \emph{inversion counting}~\cite{EKK+00,ACCL1}
for estimating the distance to monotonicity.
\iffalse Indeed, most sublinear or streaming algorithms for this
problem use some variant of this method.
\fi

We begin by formally defining balanced indices.

\begin{definition} \label{def:balanced} For a box ${\cal T}$ and $\rho \in [0,1]$, an index $x$
is said to be {\em $\rho$-balanced in ${\cal T}$}
if $x-x_L({\cal T})$ and $x_R({\cal T})-x$
are both at least  $\rho {\bf {\rm  w}}({\cal T})$, and is \emph{$\rho$-unbalanced} otherwise.
\end{definition}
It follows that the number of $\rho$-balanced indices is at least $\lfloor (1-2\rho){\bf {\rm  w}}({\cal T}) \rfloor$ and the number of $\rho$-unbalanced indices
is at most $2\rho {\bf {\rm  w}}({\cal T}) + 1$.  Excluding the degerate splitter $x_R({\cal T})$ we get:
\begin{prop}
\label{prop:unbalanced} For any $\rho>0$,
the number of nondegenerate $\rho$-unbalanced splitters of ${\cal T}$ is at most $2\rho {\bf {\rm  w}}({\cal T})$.
\end{prop}

\medskip

The definition of safe has several parameters and ``moving parts'' and some preliminary discussion may be helpful.   The definition
involves three parameters: a box ${\cal R}$, a real number $\mu \in (0,1)$ and a positive real number $L$.
The notion of safety is expressed by saying that $s$ is a {\em $(\mu,L)$-safe splitter for ${\cal R}$}.   The requirements are
that $s$ pass a collection of tests, one for each substrip ${\cal S}$ of ${\cal R}$ that is
adjacent to $s$ in the following sense: either the maximum index in $X({\cal S})$ is $s-1$ or the minimum index is $s+1$.
The requirement corresponding to substrip ${\cal S}$ of ${\cal R}$ is that the number
of ${\cal F}$-points inside of ${\cal S}$ that are in violation with $F(s)$ should be ``not too large'' compared with the
total number of ${\cal F}$-points inside of ${\cal S}$: specifically it should be at most $L+\mu|{\cal F}\cap {\cal S}|$.

\begin{definition} \label{def:safe} This is a series of definitions used to formalize safeness of splitters.
 \begin{itemize}
\item $viol(s,{\cal S})$: This is the number of points $P \in {\cal S} \cap {\cal F}$ that are in violation with
$F(s)$.
\item $Z(s,{\cal S}) := viol(s,{\cal S})-\mu|{\cal F} \cap {\cal S}|$.
\item $Z_x(s,{\cal S})$: This is defined for index $x \in X({\cal S})$. Suppose $F(x) \in {\cal S}$. If $F(x) \sim F(s)$, $Z_x(s,{\cal S})=-\mu$
and if $F(x) \not\sim F(s)$, $Z_x(s,{\cal S})=1-\mu$.  If $F(x) \not \in {\cal S}$, $Z_x(s,{\cal S})$ is 0.
Note that $Z(s,{\cal S}) = \sum_{x \in X({\cal S})} Z_x(s,{\cal S})$.
\item  $(\mu,L)$-accepting: A strip ${\cal S}$ is {\em $(\mu,L)$-accepting for $s$} if $Z(s,{\cal S})\leq L$ and is
{\em $(\mu,L)$-rejecting for $s$} otherwise.
\item Adjacent strips: A strip ${\cal S}$ is said to be {\em adjacent to $s$} if either $x_L({\cal S})=s$ (i.e. the lowest index  in  $X({\cal S})$ is $s+1$)
or $x_R({\cal S})=s-1$ (the highest index in $X({\cal S})$ is $s-1$).
\item $(\mu,L)$-unsafe: We say that $s$  is {\em $(\mu,L)$-unsafe  for ${\cal R}$}  if there is
some ${\cal R}$-strip ${\cal S}$ that is  adjacent to $s$  and $(\mu,L)$-rejecting for
$s$.
\item $(\mu,L)$-safe:We say that $s$ is {\em $(\mu,L)$-safe for ${\cal R}$} if every ${\cal R}$-strip ${\cal S}$ that is adjacent to $s$
is $(\mu,L)$-accepting for $s$. We remark that the $(\mu,L)$-safe and $(\mu.L)$-unsafe indices for ${\cal R}$ partition the set of splitters of ${\cal R}$.
\end{itemize}
\end{definition}

With this preamble, we can state the main definition of \emph{adequate splitters}.

\begin{definition} Let ${\cal T} \subseteq {\cal B}$ be a pair of boxes and $\mu,\rho \in (0,1)$ and $L>0$ .
A splitter $s \in X({\cal T})$ is {\em $(\mu,L,\rho)$-adequate for ${\cal T},{\cal B}$} if:
\begin{itemize}
\item $F(s) \in {\cal T}$
\item $s$ is $(\mu,L)$-safe for $\strip{{\cal T}}{{\cal B}}$
\item $s$ is $\rho$-balanced in ${\cal T}$.
\end{itemize}
\end{definition}

We describe a procedure ${\rm {\bf FindSplitter}}$ that takes as input
a pair of boxes ${\cal T} \subseteq {\cal B}$  and parameters $\rho,\mu$ and $L \geq 1$ and
searches for such a splitter. The procedure
returns a pair $(splitter\_found, s)$
where $splitter\_found$ is set to {\tt TRUE} or {\tt FALSE}
and $s \in X({\cal T})$.

We say that an execution
of  ${\rm {\bf FindSplitter}}$ on input $({\cal T},{\cal B},\mu,L,\rho)$ is
{\em reliable} if the following holds:
\begin{itemize}
\item If ${\cal T}$ has at least $\rho {\bf {\rm  w}}({\cal B})$ splitters that are $(\mu,L,\rho)$-adequate  for ${\cal T},{\cal B}$ then $splitter\_found$
is set to {\tt TRUE}.
\item If $splitter\_found={\tt TRUE}$ then $s$ is a $(\mu,2L,\rho)$-adequate splitter for ${\cal T},{\cal B}$.  (Note that here
we relax the parameter $L$ to  $2L$.)
\end{itemize}
An execution where either of these two conditions fails is called {\em unreliable}.
The procedure ${\rm {\bf FindSplitter}}$ is designed so that each execution
is reliable with high probability. The construction  is  straightforward application of
random sampling, though the details are a bit technical. We first state the claims related to ${\rm {\bf FindSplitter}}$.
On first reading the reader may wish to skip the details and simply take note of these claims.

\begin{prop}
\label{prop:splitter}
For any input ${\cal T},{\cal B},\mu,L,\rho$, an execution of ${\rm {\bf FindSplitter}}({\cal T},{\cal B},\mu,L,\rho)$ is reliable with probability at least $1-n^{-\Omega(\log n)}$
and has running time $O((\frac{{\bf {\rm  w}}({\cal T})}{L})^3(\log n)^4/\rho)$.
\end{prop}

For further reference. we note the following direct corollary.

\begin{corollary}
\label{cor:fails}
Let $\mu,\rho \in (0,1)$ and $L>0$.
Let ${\cal T}$ be a subbox of ${\cal B}$.
Assume that a reliable run of ${\rm {\bf FindSplitter}}({\cal T},{\cal B},\mu,L,\rho)$ fails to find a splitter.
Then the number of nondegenerate $(\mu,L)$-safe splitters for $\strip{{\cal T}}{{\cal B}}$ is at most $3\rho{\bf {\rm  w}}({\cal T})$.
\end{corollary}

\begin{proof} (of \Cor{fails} assuming  \Prop{splitter})
Since the run is reliable and no splitter was found, there are at most $\rho {\bf {\rm  w}}({\cal T})$
splitters that are $\rho$-balanced and $(\mu,L)$-safe for ${\cal T},{\cal B}$. By  \Prop{unbalanced},
the number of nondegenerate $\rho$-unbalanced splitters is at most $2\rho {\bf {\rm  w}}({\cal T})$.  Summing, the total
number of nondegenerate $(\mu,L)$-safe splitters is at most $3\rho {\bf {\rm  w}}({\cal T})$.
\end{proof}

The procedure ${\rm {\bf FindSplitter}}$ uses the following auxiliary procedures.

\begin{itemize}
\item {\bf $approxZ$:} The input is an index $s$, box ${\cal C}$, and integer $m \leq {\bf {\rm  w}}({\cal C})$
and the output is an approximation of $Z(s,{\cal C})$. If $m={\bf {\rm  w}}({\cal C})$ then this returns the exact
value $Z(s,{\cal C})=\sum_{x \in X({\cal C})}Z_x(s,{\cal C})$.  Otherwise, this is obtained by taking a random sample $M$ of size $m$ from $X({\cal C})$
and outputting $\frac{{\bf {\rm  w}}({\cal C})}{m}\sum_{x \in M} Z_x(s,{\cal C})$.
\item {\bf $Test\_Safe$:} Input is an index $s$, box ${\cal R}$ and parameter $L$. Output is either {\em accept} or {\em reject}.
For each strip
${\cal S}$ of ${\cal R}$ that is adjacent to $s$ and has width a multiple of $\lceil L/3 \rceil$, evaluate $approxZ(s,{\cal S},m)$
with $m = \min({\bf {\rm  w}}({\cal S}),10((\log n){\bf {\rm  w}}({\cal S})/L)^2)$.  $Test\_Safe(s,{\cal R},L)$ \emph{accepts} if every evaluation of $approxZ$ returns a value
less than $4L/3$ and otherwise {\em rejects}.
\item  ${\rm {\bf FindSplitter}}({\cal T},{\cal B},\mu,L,\rho)$ takes a random sample $R$ of size $10(\log n)^2/\rho$
from  the interval $X_{\rho}({\cal T})$ consisting of all indices that are $\rho$-balanced in ${\cal T}$.
For each $s \in R$, we first check if both $F(s) \in {\cal T}$ and $Test\_Safe(s,\strip{{\cal T}}{{\cal B}},L)$ accepts.  If some $s \in R$
is accepted, then
${\rm {\bf FindSplitter}}$ returns $splitter\_found={\tt TRUE}$ and $splitter$ is set to $s$.  If all are rejected,
then $splitter\_found={\tt FALSE}$.
\end{itemize}

\begin{proof} (of \Prop{splitter})
The running time of  ${\rm {\bf FindSplitter}}({\cal T},{\cal B},\mu,L,\rho)$ is at most $O((\frac{{\bf {\rm  w}}({\cal T})}{L})^3(\log n)^4/\rho)$.
There are $O((\log n)^2/\rho)$ invocations to $Test\_Safe$. Note that ${\bf {\rm  w}}({\cal T}|{\cal B}) = {\bf {\rm  w}}({\cal T})$.
Each call to $Test\_Safe$ runs $approxZ$ with $m = O(((\log n) {\bf {\rm  w}}({\cal S})/L)^2)$ on at most $3{\bf {\rm  w}}({\cal T})/L$ substrips.
Multiplying all of these numbers together gives the final bound.
(Later, we select $\rho = 1/(\log n)^{O(1)}$ and $L = {\bf {\rm  w}}({\cal T})/(\log n)^{O(1)}$, to bound the running time by $(\log n)^{O(1)}$.)

The random seed of ${\rm {\bf FindSplitter}}$ is used to specify the sample $R$  as well as the samples $M$ for each
call to $approxZ$.  We say that a particular value of the
random seed is {\em sound for input $({\cal T},{\cal B},\mu,L,\rho)$} provided that:
\begin{itemize}
\item If the number of  $(\mu,L,\rho)$-adequate splitters for ${\cal T},{\cal B}$ is at least $\rho {\bf {\rm  w}}({\cal T})$,
then at least one such index is selected for $R$.
\item For every call to $approxZ(s,{\cal S},m)$, the estimate returned is within $L/3$ of $Z(s,{\cal S})$.
\end{itemize}

We say that the random seed is {\em sound} if it is sound for all possible inputs $({\cal T},{\cal B},L,\rho)$.  We now
show (1) the probability that the random seed is not sound is $n^{-\Omega(\log(n))}$, and (2)  if the random
seed is sound then for any input $({\cal T},{\cal B},L,\rho)$ to ${\rm {\bf FindSplitter}}$,
the execution ${\rm {\bf FindSplitter}}({\cal T},{\cal B},L,\rho)$ is reliable.  This will complete the proof of the  proposition.

First consider (1).   First we fix an input $({\cal T},{\cal B},L,\rho)$ to ${\rm {\bf FindSplitter}}$ and upper bound the probability that the random seed is not
sound for that input.  Consider the probability that the first condition of soundness is violated.
 by the hypothesis of (1), a randomly selected index from $X({\cal T})$ is $(\mu,L,\rho)$-adequate for ${\cal T},{\cal B}$
with probability at least $\rho$.  The probability that $R$ contains no such index is at most $(1-\rho)^{10(\log n)^2/\rho}=n^{-\Omega(\log n)}$.
Next consider the probability that the second condition of soundess is violated.
 Consider some call to $approxZ(s,{\cal S},m)$.
The output is $X = X_1 + X_2 + \ldots + X_m$, where each random variable $X_i = ({\bf {\rm  w}}({\cal S})/m)Z_{x_i}(s,{\cal S})$ for the  $i$th sample $x_i$.
Note that $\hbox{\bf E}[Z_{x_i}] = Z(s,{\cal S})/{\bf {\rm  w}}({\cal S})$, so $\hbox{\bf E}[X] = Z(s,{\cal S})$. Also, $X_i \in [-{\bf {\rm  w}}({\cal S})/m,0]$ (since $\mu \in (0,1)$).
By \Prop{hoeff1}, since $m = 10((\log n){\bf {\rm  w}}({\cal S})/L)^2$, the probability that
the estimate has error more than $L/3$ is $\exp(-\Omega(L^2m/{\bf {\rm  w}}({\cal S})^2)) = n^{-\Omega(\log n)}$. Thus the overall
probability that the seed is not sound for $({\cal T},{\cal B},L,\rho)$ is at most $n^{-\Omega(\log n)}$.

Note that the number of possible settings of the parameters for $approxZ(s,{\cal S},m)$ is at most $n^3$ (at most $n$ choices each for $s$ and $n$
and the boundary of the ${\cal B}$-strip ${\cal C}$), so we can sum the probability of errors over all possible calls and conclude that
the probability that a random seed is not sound is $n^{-\Omega(\log n)}$.

Next we show (2).  Assume the seed is sound and fix the input $({\cal T},{\cal B},L,\rho)$ to ${\rm {\bf FindSplitter}}$.  For the first condition of reliability,
 suppose that there  are at least $\rho {\bf {\rm  w}}({\cal T})$
splitters that are $(\mu,L,\rho)$-adequate for ${\cal T},{\cal B}$.  By the soundness of the seed, at least one such splitter $s$ is chosen to be in $R$.
 When $Test\_Safe(s,\strip{{\cal T}}{{\cal B}},L)$  is performed,
for each examined strip ${\cal S}$, $approxZ(s,{\cal S},m)$ will be at most $4L/3$.  This is because $s$ is $(\mu,L)$-safe for $\strip{{\cal T}}{{\cal B}}$
and thus $Z(s,{\cal S}) \leq L$ and the second condition of soundness guarantees that $approxZ(s,{\cal S},m) \leq Z(s,{\cal S})+L/3$.
So $s$ will be accepted, and thus $splitter\_found$ will be set to {\tt TRUE}.

For the second condition defining reliable, it suffices to show that
no $(\mu,2L)$-unsafe splitter is accepted.  Suppose $s$ is $(\mu,2L)$-unsafe.  Then there is a strip ${\cal S}$ adjacent to $s$ such that $Z(s,{\cal S}) > 2L$.  If ${\cal S}'$
is the strip adjacent to $s$ whose width is the largest multiple of $\lceil L/3 \rceil$ below ${\bf {\rm  w}}({\cal S})$
then $Z(s,{\cal S}') \geq Z(s,{\cal S})-L/3 > 5L/3$. By the soundness of the seed, $Test\_Safe(s,\strip{{\cal T}}{{\cal B}},L)$ evaluates
$approxZ(s,\strip{{\cal T}}{{\cal B}},m)$, which returns a value greater than $4L/3$. Hence, $Test\_Safe(s,\strip{{\cal T}}{{\cal B}},L)$ rejects.
\iffalse
If $Test\_Safe$ returns {\tt TRUE}, then the output splitter $s$ must be $(\mu,2L)$-safe.
\fi
\end{proof}

\subsection{The dichotomy lemma}
\label{subsec:dichotomy}

In this subsection, we prove a key technical lemma. The lemma expresses the
dichotomy discussed in the overview of the algorithm in the introduction.
If a given box has few good splitters, then any increasing sequence in the box must
miss a significant fraction of ${\cal F}$-points in the box. This lemma can be seen as a generalization
(and a different viewpoint) of Lemma 2.3 in~\cite{ACCL1}. That result was a key part
of the $2$-approximation for the distance to monotonicity, and related the distance to
(roughly speaking) the number of unsafe points.

\begin{figure*}[tb]
  \centering
  \subfloat[The setting]{\includegraphics[width=0.35\textwidth]{figures/dichotomy1.pdf} \label{fig:dichot1}}
  $\qquad \qquad$
  \subfloat[The strategy]{\includegraphics[width=0.35\textwidth]{figures/dichotomy2.pdf} \label{fig:dichot2}}
    \caption{(a) We have a boxchain $\vec{{\cal D}}$ compatible with strip decomposition $\vec{{\cal S}}$, spanning box ${\cal R}$.
    (b) We bound $\chi^{out}$ through the dark gray regions. These disjoint regions are constructed through a set
    of strips. ${\cal V}(x)$ consists of violations in the strip that are not contained in the main box chain.}
\end{figure*}

The set up for the lemma is:
\begin{description}
\item[D1] ${\cal R}$ is a box.
\item[D2]  $\vec{{\cal S}}$ is a strip decomposition of  ${\cal R}$, i.e., a partition of ${\cal R}$ into ${\cal R}$-strips.
\item[D3] For $x \in X({\cal R})$, $s(x)$ is the width of the strip containing $x$.
\item[D4] $\mu \in (0,1)$.
\item[D5]  An index $x \in X({\cal R})$ is called {\em safe} or {\em unsafe},
depending on whether it is a $(\mu,s(x))$-safe splitter for ${\cal R}$.
\item[D6] $\vec{{\cal D}}$ is an arbitrary box-chain that is
compatible with $\vec{{\cal S}}$. (This means that $\vec{{\cal S}}$ consists of the strips $\strip{{\cal D}}{{\cal R}}$ for ${\cal D} \in \vec{{\cal D}}$.
Refer to \Fig{dichot1}.)
\item[D7] An index $x$ such that $F(x) \in \vec{{\cal D}}^{\cup}$ is called a {\em  $\vec{{\cal D}}$-index}.
\item[D8] $S$ is the set of $\vec{{\cal D}}$-indices $x$ that are safe, and $U$
is the set of  $\vec{{\cal D}}$-indices that are unsafe.
\item[D9] $\chi=|{\cal R} \cap {\cal F}|$ is the number of ${\cal F}$-points in ${\cal R}$, $\chi^{in}$ is the number of such points
that lie inside ${\cal D}^{\cup}$ and $\chi^{out}=\chi-\chi^{in}$ is the number of such points that lie outside of
${\cal D}^{\cup}$.
\end{description}

\begin{lemma}
\label{lem:dichotomy}
Under hypotheses D1-D9,
we have  $\chi^{out} \geq \frac{\mu}{1-\mu}|U|$  and
$\chi^{in} \leq (1-\mu)\chi + \mu(|S|)$.
\end{lemma}

The point of the lemma is that if there are few safe indices then the fraction of ${\cal F}$-points of ${\cal R}$ that
lie in $\vec{{\cal D}}$ can't be much larger than $1-\mu$.
The idea of the proof is that each unsafe index in $\vec{{\cal D}}^{\cup} \cap {\cal F}$ can be associated
to a non-trivial set of points in ${\cal F}$ that are outside of $\vec{{\cal D}}$.

\begin{proof} For each $x \in U$, there exists a strip ${\cal W}(x)$ with $x$ on either
the left or right end such that ${\cal W}(x)$ is $(\mu,s(x))$-rejecting for $x$.
In \Fig{dichot2}, we show such a point $F(x)$ with ${\cal W}(x)$ to the right.
Let ${\cal V}(x)$ be the set of violations with $F(x)$, contained in ${\cal W}(x)$ but not in $\vec{{\cal D}}^\cup$.
In other words, ${\cal V}(x) = \{F(y) | F(y) \not\sim F(x), F(y) \in {\cal W}(x) \setminus \vec{{\cal D}}^\cup\}$.
In \Fig{dichot2}, the corresponding region in ${\cal W}(x)$ is marked in dark gray. Observe
that it is contained in $\vec{{\cal D}}^{SE}$. We now lower bound $|{\cal V}(x)|$.

\begin{claim}
\label{clm:cV}
$|{\cal V}(x)| \geq \frac{\mu}{1-\mu} |\vec{{\cal D}}^{\cup} \cap {\cal W}(x)\cap {\cal F}|$.
\end{claim}

\begin{proof}
The number of violations with $x$ in ${\cal W}(x)$ is at least $\mu|{\cal F} \cap {\cal W}(x)|+s(x)$.
Any violation with $x$ contained in $\vec{{\cal D}}^\cup$ must be contained in $\vec{{\cal D}}[x]$ (the unique box of $\vec{{\cal D}}$ whose index set includes $x$).
This is because $\vec{{\cal D}}$ is a box chain (a look at \Fig{dichot2} should make this clear).
Hence, the number of such violations is at most ${\bf {\rm  w}}(\vec{{\cal D}}[x]) \leq s(x)$.
Combining, $|{\cal V}(x)| \geq \mu|{\cal F} \cap {\cal W}(x)|$. Since ${\cal V}(x)$ is disjoint with $\vec{{\cal D}}^\cup$,
$|\vec{{\cal D}}^\cup \cap {\cal W}(x)\cap {\cal F}| \leq (1-\mu)|{\cal F} \cap {\cal W}(x)|$ and $|{\cal V}(x)| \geq \frac{\mu}{1-\mu} |\vec{{\cal D}}^{\cup} \cap {\cal W}(x) \cap {\cal F}|$.
\end{proof}

Let $L$ (resp. $R$) be the indices $x \in U$ such that $x$ lies to the left (resp. right) of  ${\cal W}(x)$.
For $x \in R$, ${\cal V}(x) \subseteq \vec{{\cal D}}^{NW}$ (refer to \Fig{dichot2}).
Similarly for $x \in L$, ${\cal V}(x) \subseteq \vec{{\cal D}}^{SE}$.

We construct  $L' \subseteq L$ and $R' \subseteq R$
such that:

\begin{itemize}
\item The family   $\{{\cal W}(x):x \in L'\}$ of strips
is pairwise disjoint and the
family $\{{\cal W}(x):x \in R'\}$
is pairwise disjoint.
\item $\bigcup_{z \in L'} {\cal W}(z)$ contains $\{F(z) | z \in L\}$
and $\bigcup_{z \in R'} {\cal W}(z)$ contains $\{F(z) | z \in R\}$.
\end{itemize}

The sets $L'$ and $R'$ are constructed separately by simple greedy algorithms.  To construct $L'$ (resp. $R'$), start with $L'$ (resp. $R'$) set to
the $\emptyset$ and repeatedly select
the least index $x \in L$ (resp. largest index $x \in R$) for which $F(x)$ is not already covered by ${\cal W}(z)$ for a previously selected $z$.

Let us define ${\cal W}'$ to be the union $\bigcup_{x \in L' \cup R'} {\cal W}(x)$.
We lower bound $\chi^{out}$ by  $|\bigcup_{x \in L' \cup R'} {\cal V}(x)|$ which is equal to $|\bigcup_{x \in L'}|{\cal V}(x)|+|\bigcup_{x \in R'}|$, since  ${\cal V}(x) \subseteq \vec{{\cal D}}^{NW}$ for $x \in R$ and   ${\cal V}(x) \subseteq \vec{{\cal D}}^{SE}$ for $x \in L$.
Furthermore, since
${\cal W}(x)$ are disjoint for $x \in R'$ and for $x \in L'$, this is equal to $\sum_{x \in L' \cup R'}|{\cal V}(x)|$.
Using   \Clm{cV}
and the fact that $U \subseteq \vec{{\cal D}}^\cup \cap {\cal W}'$, we obtain:
\begin{eqnarray*}
\chi^{out} \geq \Big|\bigcup_{x \in L' \cup R'} {\cal V}(x) \Big|& = &
\sum_{x \in L' \cup R'} |{\cal V}(x)| \\
 &  \geq & \sum_{x \in L' \cup R'}\frac{\mu}{1-\mu}|\vec{{\cal D}}^{\cup} \cap {\cal W}(x) \cap {\cal F}|\\
& \geq & \frac{\mu}{1-\mu}|\vec{{\cal D}}^{\cup} \cap {\cal W}'(x)| \geq \frac{\mu}{1-\mu}|U|.
\end{eqnarray*}
For the second conclusion of the lemma, using  $\chi^{in}= |U|+|S|$ we get:

\begin{eqnarray*}
\chi^{in} = \chi - \chi^{out} & \geq & \chi - \frac{\mu}{1-\mu}|U| \\
& = & \chi - \frac{\mu}{1-\mu} (\chi^{in} - |S|).
\end{eqnarray*}
Multiplying both sides by $1-\mu$ and adding $\mu \chi^{in}$ to both sides yields the desired inequality.
\hfill $\Box$\\
\end{proof}

\subsection{Value nets and the subroutine {\rm {\bf BuildNet}}}
\label{subsec:nets}

Given a box, we want to select a suitably  representative set of values from the box.
Let us say that a value interval $J$ is {\em $\alpha$-popular for box ${\cal B}$} if there
are at least $\alpha {\bf {\rm  w}}({\cal B})$ indices $x \in X({\cal B})$ such that $f(x) \in J$.
If ${\cal B}$ is a box and $\alpha \in (0,1)$,
a {\em $\alpha$-value net} for ${\cal B}$ is a subset $V$ of $Y({\cal B})$ such that:
\begin{itemize}
\item $y_T({\cal B}) \in V$.
\item For all subintervals $J$ of $Y({\cal B})$ that are $\alpha$-popular for ${\cal B}$, $V \cap J \neq \emptyset$.
\end{itemize}

Refer to \Fig{valuenet}. The value net contains a value in $J$ whenever the corresponding dark gray region contains at least
$\alpha {\bf {\rm  w}}({\cal B})$ ${\cal F}$-points.

\begin{figure*}[tb]
  \centering
  \subfloat[Value nets]{\includegraphics[width=0.25\textwidth]{figures/valuenet.pdf} \label{fig:valuenet}}
  $\qquad \qquad$
  \subfloat[The digraph $D(\Gamma)$]{\includegraphics[width=0.45\textwidth]{figures/digraph.pdf} \label{fig:digraph}}
    \caption{(a) If the number of points in the gray region is large enough, then a value
    net must contain a value in $J$.
    (b) All grid points (which are internal to the box) are vertices. The dashed arrows show the 3 different types of arcs in $D(\Gamma)$. The solid line traces a $D(\Gamma)$ path,
    and the corresponding box chain is colored gray.}
\end{figure*}

If we had access to  the set of values $Y({\cal B}) \cap f(X({\cal B}))$ in nondecreasing order, then we could
construct a $\alpha$-value net for ${\cal B}$ by taking those values whose position in the order is a multiple of
$\lceil \alpha {\bf {\rm  w}}({\cal B}) \rceil$.  However, we can only access the values indirectly
by evaluating $f$ at indices in $X({\cal B})$ so constructing this order would require evaluating $f$ at every
index in $X({\cal B})$, which is too time consuing.

To  construct a  $\alpha$-value net quickly we use random sampling.

\begin{prop}
\label{prop:buildnet}
There is a randomized procedure ${\rm {\bf BuildNet}}$ that takes
as input a triple $({\cal B},\alpha,\xi)$ where ${\cal B}$ is a box
and $\alpha,\xi \in (0,1)$, runs in time $(1/\alpha)^{O(1)}\log(1/\xi)$ and outputs
a subset $V$ of $Y({\cal B})$ of size at most $4\lceil 1/\alpha \rceil$
such that with probability at least $1-\xi$, $V$  is a $\alpha$-value net for ${\cal B}$.
\end{prop}

\begin{proof}
Given a box ${\cal B}$, let ${\cal B}'$ be the strip $\strip{{\cal B}}{{\cal U}}$. (This is the set
of all points whose index belongs to $X({\cal B})$.)
It suffices to  construct a $\alpha$-value net $V'$ for ${\cal B}'$.  Once we do this
we take $V=V' \cap Y({\cal B}) \cup \{y_T({\cal B})\}$. This                                                                                is a $\alpha$-value net for ${\cal B}$
since every $\alpha$-popular value  interval $J$  for ${\cal B}$ is also
$\alpha$-popular for ${\cal B}'$.

So let us construct a $\alpha$-value net for ${\cal B}'$.
Let $s=4\lceil 1/\alpha \rceil$.
Let $M=\lceil s\ln(s/2\xi)\rceil$.
Let $R$ be a sequence of $sM-1$ uniform random samples from $X({\cal B}')$
and let $y_1 \leq \cdots \leq y_{sM-1}$ be their $y$-values in sorted order.
Note that all of these are in $Y({\cal B}')$.
Let $y_0=0$ and $y_{sM}={\tt valbound}$.  Define $V=\{y_{iM}:i \in [1,s-1]\}$.

We analyze the probability that $V$ is not a $\alpha$-value net for ${\cal B}'$.

Let $B=\lceil \alpha {\bf {\rm  w}}({\cal B}')/2 \rceil$ (which is also equal to $\lceil \alpha {\bf {\rm  w}}({\cal B})/2 \rceil$).
Let $x_1,\ldots,x_{{\bf {\rm  w}}({\cal B})}$ be the indices of $X({\cal B}')$ ordered so that $f(x_1) \leq \cdots \leq f(x_{{\bf {\rm  w}}({\cal B}')})$.
Write ${\bf {\rm  w}}({\cal B}')$ as $qB+r$ where $r < B$, and note that $q \leq {\bf {\rm  w}}({\cal B}')/B \leq 2/\alpha \leq s/2$.  Partition $x_1,\ldots,x_{qB}$ into
$q$ ``bins'', where each bin is a sequence of $B$ consecutive indices.
Let  $A_i$ for $i \in [1,q]$ be the number of samples from $R$ that fall in bin $i$.

We now show that (1) with probability at least $1-\xi$, $A_i \geq M$ for all $i \in [1,q]$, and
(2)
if $A_i \geq M$ for each $i$, then $V$ is a $\alpha$-value net for ${\cal B}'$.

We prove (2) first.   Note that $V$ contains
at least $1$ value from each bin.
Let $J$ be a $\alpha$-popular subinterval of $Y({\cal B}')$.  Then $|F^{-1}(J) \cap X({\cal B}')| \geq \alpha {\bf {\rm  w}}({\cal B}') > 2B-2$.
Since $F^{-1}(J) \cap X({\cal B}')$ is a consecutive subsequence of $x_1,\ldots,x_{{\bf {\rm  w}}({\cal B}')}$, it must contain at least one bin,
and hence intersects $V$.

It remains to prove (1).  Fix $i \in [1,q]$ and  consider the event that  $A_i \leq M-1$.
$A_i$ is the sum of $sM-1$ Bernoulli trials each having probability at least $\frac{B}{{\bf {\rm  w}}({\cal B}')} \geq \alpha/2$, and so has expectation at least
$\frac{\alpha}{2}(sM-1)\geq 2M-1$. By
\Prop{hoeff1}, ${\rm Prob}[A_i \leq  M-1] \leq e^{-M/s}$. By the union bound, the probability that some $A_i\leq M-1$
is at most $se^{-M/s}/2$ and by the choice of $M$ this is at most $\xi$.  This completes the proof of the value net construction for ${\cal B}'$.
\end{proof}

\iffalse
To get a $\alpha$-value net for ${\cal B}$, we restrict
the $\alpha$-value net $V$ for ${\cal B}'$
to $Y({\cal B}) \cap V$ and add the endpoints $y_B({\cal B}),y_T({\cal B})$. This is a valid value net since the box ${\cal B}$ is basically ${\cal B}'$ restricted
to a value interval. \Fig{valuenet} should makes this clear.
\fi

\subsection{Grids, the subroutine {\rm {\bf BuildGrid}} and grid digraphs}
\label{subsec:grids}

A grid $\Gamma$ is a {\em ${\cal B}$-grid} if $X(\Gamma) \subset X({\cal B})-\{x_L({\cal B}),x_R({\cal B})\}$ and
$Y({\cal B})$ is a value net for ${\cal B}$. If $x_1<\cdots<x_k$ are the indices of $X(\Gamma)$, then
they define a ${\cal B}$-strip decomposition  of $X({\cal B})$ whose associated index partition is $(x_L({\cal B}),x_1],(x_1,x_2],\cdots,(x_k,x_R({\cal B})]$.
We call this the strip decomposition of ${\cal B}$ induced by $\Gamma$.

\begin{definition} \label{def:fine}
For a box ${\cal B}$ and $\alpha>0$, a grid $\Gamma$ is an {\em $\alpha$-fine} ${\cal B}$-grid if:

\begin{itemize}
\item $X(\Gamma)$ contains an index from every subinterval $I$ of  $X({\cal B})$ having size exceeding $\alpha {\bf {\rm  w}}({\cal B})$.
\item $Y(\Gamma)$ is a $\frac{\alpha}{|X(\Gamma)|}$-value net.
\end{itemize}
\end{definition}

We define a procedure ${\rm {\bf BuildGrid}}{}$ that  takes as input a triple $({\cal B},\alpha,\xi)$ (as does
{\rm {\bf BuildNet}})
and outputs a ${\cal B}$-grid $\Gamma$ that is {\em $\alpha$-fine} with probability at least $1-\xi$.

The procedure works as follows.
If ${\bf {\rm  w}}({\cal B}) \leq 1/\alpha$ then $X(\Gamma)=X({\cal B})$ and $Y(\Gamma)=Y({\cal B})$. Otherwise, set $r= \lceil 1/\alpha \rceil$ and for $i \in [0,r]$, define
$x_i=x_L({\cal B}) + \lfloor i \alpha  {\bf {\rm  w}}({\cal B}) \rfloor$.  We take $X(\Gamma)=\{x_1,\ldots,x_{r-1}\}$.
It follows that $x_0=x_L({\cal B})$, $x_r=x_R({\cal B})$ and  $x_i-x_{i-1} \leq \lceil \alpha {\bf {\rm  w}}({\cal B}) \rceil$ for each $i \in [1,r]$.
The set $Y(\Gamma)$ is constructed by applying ${\rm {\bf BuildNet}}({\cal B},\alpha^2/2,\xi)$.
We say that  ${\rm {\bf BuildGrid}}({\cal B},\alpha,\xi)$ {\em is reliable} if the grid $\Gamma$ that it outputs is
$\alpha$-fine.  The definition of the grid, together with  \Prop{buildnet} implies:

\begin{prop}
\label{prop:buildgrid}  ${\rm {\bf BuildGrid}}({\cal B},\alpha,\xi)$ produces a grid $\Gamma$ with
$|X(\Gamma)| \leq 1+\lceil 1/\alpha \rceil \leq 3/\alpha$  and
$|Y(\Gamma) \leq \lceil 8/\alpha^2 \rceil \leq 16/\alpha^2$  that is reliable with probability at least $1-\xi$.
\end{prop}

{\bf Grid digraph $D(\Gamma)$:} This is associated with the
${\cal B}$-grid $\Gamma$. The vertex set is
$\Gamma\cup \{P_{BL}({\cal B}),P_{TR}({\cal B})\}$. The arc sets
consists of pairs $(P_{BL}({\cal B}),Q)$ where $Q$ lies in the leftmost columnn of $\Gamma$,
$(Q,P_{TR}({\cal B}))$ where $Q$ belongs to the rightmost column of $\Gamma$,  and $(P,Q)$ where
$P \prec Q$ and $P$ and $Q$ are in adjacent columns of $\Gamma$. $D(\Gamma)$ is acyclic and has unique
source $P_{BL}({\cal B})$ and unique sink $P_{TR}({\cal B})$.  A {\em $D(\Gamma)$-path} is a source-to-sink path in $D(\Gamma)$.
Every arc $(P,Q)$ of $D(\Gamma)$ corresponds to a box $Box(P,Q)$ and a $D(\Gamma)$-path
corresponds to a ${\cal B}$-box chain.  A box chain arising in this way is a $D(\Gamma)$-chain.
Each box correponding to an arc is called a \emph{grid box}.
Refer to \Fig{digraph}.

\medskip

The following lemma says that if $\Gamma$ is a $\alpha$-fine ${\cal B}$-grid then for any increasing sequence in ${\cal B}$
there is a $D(\Gamma)$-chain that contains all but a small number of points from the sequence.

\begin{lemma}(Grid approximation lemma)
\label{lem:grid-approx}
Suppose $\Gamma$ is a $\alpha$-fine ${\cal B}$-grid.
Let ${\cal L}$ be an increasing sequence of ${\cal F}$-points in ${\cal B}$.
Then there is
a $D(\Gamma)$-chain $\vec{{\cal D}}=({\cal D}_1,\dots,{\cal D}_r)$
such that the subset ${\cal L}-\vec{{\cal D}}^{\cup}$
has size at most $\alpha {\bf {\rm  w}}({\cal B})$.
\end{lemma}

\begin{proof}
Let $X(\Gamma)=\{x_1<\ldots<x_{r}\}$.
To specify a $D(\Gamma)$-chain we need to choose a nondecreasing comparable sequence of points $P_1,\ldots,P_{r}$,
such that $P_i$ is in column $x_i$ of $\Gamma$.
Let ${\cal L}_i$ be the portion of ${\cal L}$ with $x$ coordinate at most $x_i$ and let $Q_i$ be the largest
point in ${\cal L}_i$.  Take $P_i$ to be the least point of $\Gamma$ in column $i$ such that $Q_i \preceq P_i$.

The points of ${\cal L}$ that lie outside of the corresponding box chain are those that belong to $P_i^{NW}$ or $P_i^{SE}$
for some point $P_i$.  Since every point of ${\cal L}_i$ is less than $P_i$, there are no points of ${\cal L}$ in $P_i^{NW}$.
The points of ${\cal L}$ in $P_i^{SE}$ have $x$-coordinate greater than $x_i$ and $y$-coordinate
strictly between $y(Q_i)$ and $y(P_i)$. By choice of $P_i$, there is no value in $Y(\Gamma)$
strictly between $y(Q_i)$ and $y(P_i)$. Since $Y(\Gamma)$ is a $\alpha/r$-value net for ${\cal B}$,
there are at most $\alpha{\bf {\rm  w}}({\cal B})/r$ points of ${\cal L}$ in $P_i^{SE}$.

Since each point $P_i$ is in violation with at most $\alpha{\bf {\rm  w}}({\cal B})/r$ points of ${\cal L}$, the total
number of points of ${\cal L}$ that violate some $P_i$ is at most $\alpha {\bf {\rm  w}}({\cal B})$.
\end{proof}

\section{The basic LIS approximation algorithm}
\label{sec:first algorithm}

In this section  we describe the algorithm {\rm {\bf BasicMain}}, which achieves the properties
stated in \Thm{alg1}.    As asserted in the theorem, {\rm {\bf BasicMain}}{} takes as input a natural number $n$, an array $f$
of size $n$ and an error parameter $\overline{\tau} \in (0,1)$ and outputs an estimate to ${\tt lis}_f$.  Recall that we assume the
values of the array are in the range $[1,{\tt valbound}]$, where ${\tt valbound}$ is a known integer.

The program {\rm {\bf BasicMain}}{} sets certain global parameters, initializes a parameter $t_{\max}$ and then calls a subroutine ${\rm {\bf ApproxLIS}}$, which is the main
part of the algorithm.  The subroutine ${\rm {\bf ApproxLIS}}$ takes as input a box ${\cal B}$ and a nonnegative integer $t$ and outputs an estimate of ${\tt lis}_f({\cal B})$.
We denote
an invocation  of ${\rm {\bf ApproxLIS}}$ on box ${\cal B}$ with parameter $t$ by  ${\rm {\bf ApproxLIS}}_t({\cal B})$.
The global parameters are all used within ${\rm {\bf ApproxLIS}}$ and the procedures it calls.
The values for the global parameters are chosen to make the error analysis work.
 The array size $n$ and the array $f$
are also treated as global parameters in ${\rm {\bf ApproxLIS}}$.

\vspace{-10pt}
\begin{center}
	\fbox{\begin{minipage}{\columnwidth}
${\rm {\bf BasicMain}}(n,f,\overline{\tau})$\\
Output: Approximation to ${\tt lis}_f$.
\begin{enumerate}
\item Fix global parameters according to table (unchanged throughout algorithm).
\begin{center}
  \begin{tabular}{ | l || c | c |}
    \hline
    {\bf Name} & {\bf Symbol} & {\bf Value} \\ \hline
    Initial precision & $t_{\max}$ & $\lceil 4/\overline{\tau} \rceil$ \\ \hline
    Sample size parameter & $\sigma$ & $10(\log n)^4$ \\ \hline
    Grid precision parameter & $\alpha$ & $\gamma$ \\ \hline
    Width threshold & $\omega$ & $1/\rho$ \\ \hline
    Tainting parameter & $\eta$ & $\frac{1}{10 \log n}$ \\ \hline
    Primary splitter parameter & $\mu_r$ & $2/(r+3)$ \\ \hline
    Secondary splitter parameter & $\gamma$ & $\frac{1}{(C_1\log n)^3}$ \\ \hline
    Splitter balance parameter & $\rho$ & $\frac{1}{C_1\log n}$ \\ \hline
  \end{tabular}
\end{center}

\item Let box  ${\cal U}$ be the  box $[1,n] \times [1,{\tt valbound}]$.
\item  Return ${\rm {\bf ApproxLIS}}_{t_{\max}}({\cal U})$.
\end{enumerate}
\end{minipage}}
\end{center}

The algorithm ${\rm {\bf ApproxLIS}}$ is recursive, and in recursive calls will be run on r values of $t \leq t_{\max}$ and subboxes ${\cal B}$ of ${\cal U}$.
We will prove the following property of ${\rm {\bf ApproxLIS}}$:

\begin{theorem}
\label{thm:basic approxlis}
Suppose ${\rm {\bf ApproxLIS}}$ is run with the global parameters set as in ${\rm {\bf BasicMain}}$.
On input a box ${\cal B} \subseteq {\cal U}$ and an integer $t$, ${\rm {\bf ApproxLIS}}_t({\cal B})$:
\begin{itemize}
\item  runs in time $(\log n)^{O(t)}$, and
\item outputs a value that, with probability at least $1-n^{-\Omega(\log(n)}$, is a
{\em $(\tau_t,\delta_t )$}-approximation to ${\tt lis}({\cal B})$, where:
\begin{eqnarray*}
\tau_t&=& \frac{4}{t} \\
\delta_t& = & \frac{t}{\log(n)}.
\end{eqnarray*}
\end{itemize}
\end{theorem}

\Thm{alg1} follows immediately from \Thm{basic approxlis}:

\begin{proof}[of \Thm{alg1}]
${\rm {\bf BasicMain}}(n,f,\overline{\tau})$ returns the output of ${\rm {\bf ApproxLIS}}_{t_{\max}}({\cal U})$.  By \Thm{basic approxlis}, this gives a
$(4/t_{\max},t_{\max}/\log(n))$-approximation to ${\tt lis}_f$ which runs in time $\log(n)^{O(t_{\max})}$.  Using the fact that $t_{\max} = \lceil 4/\overline{\tau} \rceil$ which is
between $4/\overline{\tau}$ and  $5/\overline{\tau}$ gives the desired running time and approximation error for ${\rm {\bf BasicMain}}$.
\end{proof}

\iffalse

Observe for $\tau_t$ (the multiplicative error) decreases with the $t$, but $\delta_t$ (the additive error) increases with $t$.
The $1/\log n$ factor in $\delta_t$ allows us to choose $t$ large enough for the desired guarantees.
We will show that the running time for $t \geq 1$ is $(\log n)^{O(t)}=(\log n)^{O(1/\tau_t)}$.

\fi

\iffalse
\subsection{Auxiliary parameters of the algorithm}
\label{subsec:parameters}

The algorithm never refers to the the parameters $\tau_t$, $\delta_t$ and $\xi$, and they will only appear in the analysis.
The algorithm does use the following auxiliary parameters. We use $C_1$ to denote a suitably large constant.

\begin{center}
  \begin{tabular}{ | l || c | c |}
    \hline
    {\bf Name} & {\bf Symbol} & {\bf Value} \\ \hline
    Sample size parameter & $\sigma$ & $10(\log n)^4$ \\ \hline
    Grid precision parameter & $\alpha$ & $\gamma$ \\ \hline
    Width threshold & $\omega$ & $1/\rho$ \\ \hline
    Tainting parameter & $\eta$ & $1/(10 \log n)$ \\ \hline
    Primary splitter parameter & $\mu_t$ & $2/(t+3)$ \\ \hline
    Secondary splitter parameter & $\gamma$ & $\frac{1}{(C_1\log n)^3}$ \\ \hline
    Splitter balance parameter & $\rho$ & $\frac{C_1}{\log n}$ \\ \hline
  \end{tabular}
\end{center}

These parameter choices come from the analysis of the algorithm.
We develop various recurrences between the parameters, and these values are chosen to
satisfy them.
The running time of the algorithm will turn out to be  $[(\frac{1}{\gamma}+\frac{1}{\alpha})(\log n)]^{t}$ which
is $(\log n)^{O(1/\tau)}$.

\fi

\subsection{Description and pseudocode for {\rm {\bf ApproxLIS}}}
\label{subsec:first overview}

The procedure ${\rm {\bf ApproxLIS}}$, uses four subprocedures ${\rm {\bf Classify}}$, ${\rm {\bf CriticalBox}}$, ${\rm{\bf TerminalBox}}$, and ${\rm {\bf GridChain}}$,
each taking as input a box ${\cal B}$ and a nonnegative quality parameter $t$,
and possibly other input.  These procedures use
the previously defined procedures ${\rm {\bf FindSplitter}}$
and ${\rm {\bf BuildGrid}}$. For later convenience, we put the quality parameter as a subscript to the procedure.

The main approximation algorithm ${\rm {\bf ApproxLIS}}_t({\cal B})$ returns
an estimate of ${\tt lis}({\cal B})$. If the
input box ${\cal B}$ has width 1, then it outputs $|{\cal F} \cap {\cal B}|$. Otherwise,
${\rm {\bf ApproxLIS}}_t$ uses a subroutine
${\rm {\bf Classify}}_t$. This takes as input ${\cal B}$
and an index $x \in X({\cal B})$ and outputs a classification of $x$ as {\em good} or {\em bad}.
${\rm {\bf ApproxLIS}}_t({\cal B})$ outputs an estimate of the number of good point by running ${\rm {\bf Classify}}_t(x,{\cal B})$
on a small random sample of indices.

Recall from Section \ref{subsec:random}
that
our viewpoint of fixing the random bits at the outset specifies the behavior of ${\rm {\bf Classify}}_t$ on every index.
We define $Good_t({\cal B})$ to be the set of indices $x$ for which ${\rm {\bf Classify}}_t(x,{\cal B})$ would return {\em good}.
Thus ${\rm {\bf ApproxLIS}}_t({\cal B})$ returns an estimate of $|Good_t({\cal B})|$.
The algorithm ${\rm {\bf Classify}}_t$ is designed so that $Good_t({\cal B})$ is the index set of an increasing sequence,
and with probability close to 1, is close in size to ${\tt lis}({\cal B})$.  Hence, ${\rm {\bf ApproxLIS}}_t({\cal B})$
should be a good estimate of ${\tt lis}({\cal B})$.

The procedure ${\rm {\bf Classify}}_t$ is recursive.  If $F(x) \not\in {\cal B}$, then $x$ is declared bad.
Otherwise, if ${\cal B}$ has width 1, we declare $x$ to be good,
and if ${\bf {\rm  w}}({\cal B})>1$  and $t=0$ then $x$ is declared bad.
The main case ($F(x) \in {\cal B}$, ${\bf {\rm  w}}({\cal B}) >1$ and $t \geq 1$) is accomplished by
calling
${\rm {\bf CriticalBox}}_t(x,{\cal B})$, which returns a subbox ${\cal C}$ of ${\cal B}$
such that $x \in X({\cal C})$. The procedure then recursively calls
${\rm {\bf Classify}}_{t-1}(x,{\cal C})$.  The classification returned by this recursive call is the output
of ${\rm {\bf Classify}}_t(x,{\cal B})$.

The procedure ${\rm {\bf CriticalBox}}_t(x,{\cal B})$  finds a subbox ${\cal C}$, called the {\em critical subbox of ${\cal B}$ for $x$}.
The procedure operates in two stages.
The first stage  is performed by ${\rm{\bf TerminalBox}}$,
which shrinks ${\cal B}$ to a subbox ${\cal T}$, called the {\em terminal box} with $x \in X({\cal T})$.
Intuitively, ${\rm{\bf TerminalBox}}$  attempts to simulate the interactive protocol discussed in the introduction.
${\rm{\bf TerminalBox}}({\cal B},x)$ initializes ${\cal T}$ to ${\cal B}$.  It  uses the subroutine ${\rm {\bf FindSplitter}}{}$
to look for an index $s$ such that $F(s) \in {\cal T}$
and $s$ is a good splitter for the ${\cal B}$-strip $\strip{{\cal T}}{{\cal B}}$.
If ${\rm {\bf FindSplitter}}$ succeeds
in finding $s$, then the splitter defines a box chain of size
2 spanning ${\cal T}$, and ${\cal T}$ is replaced by the box in the chain whose index set contains $x$.  This process is repeated
until either ${\bf {\rm  w}}({\cal T}) \leq \omega$ (${\cal T}$ is {\em narrow}) or ${\rm {\bf FindSplitter}}$ fails to find a good splitter.
This ends the first stage.

In the second stage,  a box chain $\vec{{\cal C}}({\cal T})$ spanning ${\cal T}$, called the {\em critical chain for ${\cal T}$}, is constructed.
Intuitively, this part implements approximation boosting sketched in the introduction.
We
use ${\rm {\bf BuildGrid}}$ to build a suitably
fine grid for ${\cal T}$ of size $(\log n)^{O(1)}$.
We then recursively
evaluate ${\rm {\bf ApproxLIS}}_{t-1}({\cal C})$
for every grid box ${\cal C}$.  Think of these values as giving
a length function on the edges of the grid digraph.  The procedure
performs a longest path
computation to compute the exact longest
path in the grid digraph
from the lower left corner to the upper right
corner of ${\cal T}$. (This computation takes $(\log n)^{O(1)}$ time.)

Having found the critical chain $\vec{{\cal C}}({\cal T})$, the output of ${\rm {\bf CriticalBox}}$ is
the box $\vec{{\cal C}}({\cal T})[x]$ of $\vec{{\cal C}}({\cal T})$  whose index set contains $x$.

The pseudocode for the algorithm is presented below.
The arguments ${\cal B},{\cal T}$ represent boxes, $t$ is a nonnegative integer, and $x$ is an index.
The array $f$ and the domain size $n$ are
treated as implicit global parameters.

\vspace{-10pt}
\begin{center}
	\fbox{\begin{minipage}{\columnwidth}
${\rm {\bf ApproxLIS}}_t({\cal B})$\\
Output: Approximation to ${\tt lis}({\cal B})$.
\begin{enumerate}
\item If ${\bf {\rm  w}}({\cal B})=1$, output $|{\cal B} \cap {\cal F}|$.
\item Otherwise (${\bf {\rm  w}}({\cal B})>1$): Select $\sigma$ uniform random indices
from $X({\cal B})$. Run ${\rm {\bf Classify}}_t(x,{\cal B})$ on
each sample point. Let $g$ be the number of points classified
as $good$ and return $g{\bf {\rm  w}}({\cal B})/\sigma$.
\end{enumerate}
\end{minipage}}
\end{center}

\vspace{-10pt}
\begin{center}
	\fbox{\begin{minipage}{\columnwidth}
${\rm {\bf Classify}}_t(x,{\cal B})$\\
Output: {\em good} or {\em bad}
\begin{enumerate}
\item If $F(x) \not\in {\cal B}$, return {\em bad}.
\item Otherwise ($F(x) \in {\cal B}$)
\begin{enumerate}
\item Base case: If ${\bf {\rm  w}}({\cal B})=1$, return {\em good}. If $t=0$ and ${\bf {\rm  w}}({\cal B})>1$, return {\em bad}.
\item  Main case (${\bf {\rm  w}}({\cal B})>1$ and $t \geq 1$):
\begin{enumerate}
\item ${\cal C} \longleftarrow {\rm {\bf CriticalBox}}_t(x,{\cal B})$.
\item Run ${\rm {\bf Classify}}_{t-1}(x,{\cal C})$ and return its output.
\end{enumerate}
\end{enumerate}
\end{enumerate}
\end{minipage}
}
\end{center}

\vspace{-10pt}
\begin{center}
	\fbox{\begin{minipage}{\columnwidth}
${\rm {\bf CriticalBox}}_t(x,{\cal B})$\\
Output: Subbox ${\cal C}$ of ${\cal B}$ such that $x \in X({\cal C})$
\begin{enumerate}
\item ${\cal T} \longleftarrow {\rm{\bf TerminalBox}}_t(x,{\cal B})$.
\item Call ${\rm {\bf GridChain}}_t({\cal T})$ and let $\vec{{\cal C}}({\cal T})$ be the chain of boxes returned.
\iffalse
\item Define the chain $\vec{{\cal C}}({\cal T})$ spanning ${\cal T}$ as follows:
\begin{enumerate}
\item If ${\cal T}$ is {\em narrow} then $\vec{{\cal C}}({\cal T})$ is the chain returned by ${\rm {\bf LIS.Chain}}({\cal T})$ (see Section \ref{subsec:unit chain}).
\item If ${\cal T}$ is {\em wide} then call ${\rm {\bf GridChain}}_t({\cal T})$ and let $\vec{{\cal C}}({\cal T})$ be the chain of boxes
returned.
\end{enumerate}
\fi
\item Return $\vec{{\cal C}}({\cal T})[x]$ (the box ${\cal C} \in \vec{{\cal C}}({\cal T})$ with $x \in X({\cal C})$).
\end{enumerate}
\end{minipage}
}
\end{center}

\vspace{-10pt}
\begin{center}
	\fbox{\begin{minipage}{\columnwidth}
${\rm{\bf TerminalBox}}_t(x,{\cal B})$ \\
Output: subbox ${\cal T}$ of ${\cal B}$ such that $x \in X({\cal T})$.
\begin{enumerate}
\item Initialize ${\cal T}$ to ${\cal B}$ and boolean variable $splitter\_found$ to {\tt TRUE}.
\item Repeat until ${\bf {\rm  w}}({\cal T}) \leq \omega$ (${\cal T}$ is narrow) or $splitter\_found$ is {\tt FALSE}:
\begin{enumerate}
\item Run ${\rm {\bf FindSplitter}}({\cal T},{\cal B},\mu_t,\gamma {\bf {\rm  w}}({\cal T}),\rho)$:
returns boolean $splitter\_found$ and  index
$splitter$.
\item If $splitter\_found={\tt TRUE}$ then
\begin{enumerate}
\item If $x \leq splitter$ then replace ${\cal T}$ by the
box $Box(P_{BL}({\cal T}),F(splitter))$.
\item If $x > splitter$ then replace ${\cal T}$ by the
box $Box(F(splitter), P_{TR}({\cal T}))$.
\end{enumerate}
\end{enumerate}
\item Return ${\cal T}$.
\end{enumerate}
\end{minipage}}
\end{center}

\vspace{-10pt}
\begin{center}
	\fbox{\begin{minipage}{\columnwidth}
${\rm {\bf GridChain}}_t({\cal T},\alpha)$\\
Output: box chain $\vec{{\cal C}}({\cal T})$ spanning ${\cal T}$.
\begin{enumerate}
\item Call ${\rm {\bf BuildGrid}}({\cal T},\alpha,n^{-2\log n})$
which returns a grid $\Gamma$.
\item  Construct the associated digraph $D(\Gamma)$
\item For each grid-box ${\cal D}$ of $D(\Gamma)$.
recursively evaluate ${\rm {\bf ApproxLIS}}_{t-1}({\cal D})$.
\item Compute the longest path in $D(\Gamma)$
from $P_{BL}({\cal T})$ to $P_{TR}({\cal T})$ according to the
length function ${\rm {\bf ApproxLIS}}_{t-1}({\cal D})$.
\item Return the $\Gamma$-chain $\vec{{\cal C}}({\cal T})$ associated to the longest path.
\end{enumerate}
\end{minipage}}
\end{center}

\section{Properties of {\rm {\bf ApproxLIS}}}

In this section and the next we prove \Thm{basic approxlis} by showing that
a call to ${\rm {\bf ApproxLIS}}_t({\cal B})$ runs in time
$(\log n)^{O(t)}$ and that with probability $1-n^{O((\log n)}$.   the output
is within $\tau_t {\tt loss}({\cal B})+ \delta_t {\bf {\rm  w}}({\cal B})$ of ${\tt lis}({\cal B})$.

We first present the easy running time analysis.  We next turn to the much more difficult task of
bounding the error of the estimate returned by the algorithm. We start with
some important structural observations about the behavior of the algorithm. We then
identify two assumptions about the random bits used by the algorithm, which encapsulate
all that we require from the random bits in the error analysis.  We show that these
assumptions hold with probability very close to 1.

In \Sec{correctness}
we  formulate and prove \Thm{basic correctness}, which says
that whenever the two assumptions hold then ${\rm {\bf ApproxLIS}}$ returns a suitably accurate estimate, and which immediately
implies the desired error bounds in Theorem \ref{thm:basic approxlis}.

\subsection{Running time analysis}
\label{subsec:running time}

Let $A_t=A_t(n)$ be the running time of ${\rm {\bf ApproxLIS}}_t$  and
$C_t=C_t(n)$ be the running time of ${\rm {\bf Classify}}_t$ on boxes of width at most $n$.
In what follows we use $P_i=P_i(n)$ to denote functions of the form $a_i ((\log n))^{b_i}$, where $a_i,b_i$ are constants that
are independent of $n$ and $t$.

\begin{claim} \label{clm:runtime} For all $t \geq 1$,
\begin{eqnarray*}
A_t & \leq & P_1 C_t + P_2. \\
C_t & \leq & C_{t-1}+ P_3 A_{t-1}+P_4.
\end{eqnarray*}
\end{claim}

\begin{proof} The first recurrence with $P_1=\sigma=10(\log n)^4$ is immediate from the definition of
${\rm {\bf ApproxLIS}}_t$.  The function $P_2$ is an upper bound on the cost of operations within ${\rm {\bf ApproxLIS}}_t$ excluding the calls to ${\rm {\bf Classify}}_t$

For the second recurrence, the final recursive call to ${\rm {\bf Classify}}_{t-1}$  gives the $C_{t-1}$ term.
The rest of the cost comes from  ${\rm {\bf CriticalBox}}_t$ which invokes ${\rm{\bf TerminalBox}}_t$, which involves several iterations
whose cost is dominated by the cost of ${\rm {\bf FindSplitter}}$.  Each iteration reduces the width of ${\cal T}$ by at least a $(1-\rho)$
factor, so the number of iterations is at most $(\log n)/\rho$.  The cost of ${\rm {\bf FindSplitter}}$ is $(\log n)^{O(1)}$,
so the cost of ${\rm{\bf TerminalBox}}_t$ is included in the term $P_4$.  ${\rm {\bf CriticalBox}}_t$ then calls ${\rm {\bf GridChain}}_t$.  This involves building a grid of
size $(\log n)^{O(1)}$ and making one call to ${\rm {\bf ApproxLIS}}_t$ for each grid box, which accounts for the term $P_3 A_{t-1}$.  All of the rest
of the cost of ${\rm {\bf GridChain}}_t$ is in doing a longest path computation on the grid digraph, which is absorbed into the $P_4$ term.
\end{proof}

\begin{corollary} \label{cor:runtime} For all $t \geq 1$, $A_t$ and $C_t$ are in $\log n^{O(t)}$.
\end{corollary}

\begin{proof} Note that $A_0, C_0 = (\log n)^{O(1)}$. By the recurrences of \Clm{runtime},
$C_t \leq P_5(P_1P_3+1)^t$ and $A_t \leq P_6(P_1P_3+1)^t$  which are both $(\log n)^{O(t)}$.
\end{proof}

\subsection{The t-splitter tree and terminal chain}
\label{sec:terminal}

We analyze the structure of the output of ${\rm{\bf TerminalBox}}_t$.
This procedure takes three parameters: the level $t$, the box ${\cal B}$ and an index $x$.
It also uses randomness within the calls to ${\rm {\bf FindSplitter}}$.
 Recall from Section \ref{subsec:random} that we classify the random bits used in ${\rm {\bf ApproxLIS}}$ as primary random bits
and all other random bits as secondary. Since ${\rm{\bf TerminalBox}}_t$ never calls ${\rm {\bf ApproxLIS}}$, all random bits used are secondary.

In the following discussion, the box ${\cal B}$, level $t$, and secondary
random bits as fixed. Under this view, ${\rm{\bf TerminalBox}}$ maps each index $x \in X({\cal B})$
to a box ${\cal T}(x)$.
We now define the {\em $t$-splitter tree}, which summarizes all important information
about the execution and output of ${\rm{\bf TerminalBox}}_t(x,{\cal B})$.

For each subbox ${\cal T}$ of ${\cal B}$, consider the output of ${\rm {\bf FindSplitter}}_t({\cal T},{\cal B},\mu_t,\gamma {\bf {\rm  w}}({\cal T}),\rho)$.
If $splitter\_found$ is {\tt FALSE} we say that ${\cal T}$ is {\em splitterless}. Otherwise, we say that ${\cal T}$ is {\em split}.
For each split box ${\cal T}$, ${\rm {\bf FindSplitter}}$ returns a splitter $s=splitter({\cal T})$ which is used to define two
subboxes of ${\cal T}$: the {\em left child} $Box(P_{BL}({\cal T}),F(s))$ and the {\em right child} $Box(F(s),P_{TR}({\cal T}))$.
Note that, when viewed as boxes in the plane, the left child lies below and to  the left of the right child.  The
left- and right-child relations together
define a directed acyclic graph on the subboxes of ${\cal B}$ in which each splitterless box has out-degree 0
and each split box has out-degree 2.  Note that if there is a path from box ${\cal T}$ to box ${\cal T}'$ then
${\cal T}' \subset {\cal T}$.

Now consider the subdigraph $R({\cal B})$ induced on the set of boxes reachable from ${\cal B}$.

\begin{itemize}
\item $R({\cal B})$ is a binary tree rooted at ${\cal B}$.
We refer to $R({\cal B})$ as the {\em $t$-splitter tree for ${\cal B}$} and the leaves of the tree as {\em terminal boxes}.
\item The sequence of boxes encountered along any root-to-leaf path are nested.
\item Two boxes ${\cal T}$ and ${\cal T}'$  in the tree such that neither is an ancestor of the other have disjoint index sets, i.e. $X({\cal T}) \cap X({\cal T}') = \emptyset$.
\item The terminal boxes together form a box chain that spans ${\cal B}$, called the {\em terminal chain}, which we denote by $\vec{{\cal T}}=\vec{{\cal T}}_t({\cal B})$.
\item
Recall (from Section \ref{subsec:basic defs}) that the box chain $\vec{{\cal T}}$ has an associated increasing sequence of points
and ${\cal P}^{\circ}(\vec{{\cal T}})$ denotes this sequence, excluding the first and last point.
Every point $P \in {\cal P}^{\circ}(\vec{{\cal T})}$ is the splitter of a unique non-terminal box of $R({\cal B})$, denoted ${\cal H}(P)$.
\item The
point sequence ${\cal P}^{\circ}(\vec{{\cal T}})$
associated to $\vec{{\cal T}}$ is the same as the sequence obtained by doing
a depth first traversal of the tree $R({\cal B})$, always visiting the left child of a node before the right child,
and recording
the sequence of splitters $splitter({\cal H})$ in post-order (listing the splitter of box ${\cal H}$ immediately after having listed all splitters in its left subtree).
\item Each terminal box ${\cal T}$ contains a grid $\Gamma({\cal T})$, as formed in the procedure ${\rm {\bf GridChain}}$. We can concatenate
grid chains spanning each ${\cal T} \in \vec{{\cal T}}$ to get a box chain that spans ${\cal B}$. This is called
a \emph{spanning terminal-compatible grid chain in ${\cal B}$}. Note that there are many possible such spanning terminal-compatible grid chains.
\end{itemize}

The following lemma is evident from the above observations and the definition of ${\rm{\bf TerminalBox}}_t$:

\begin{lemma}
\label{lem:terminal}
For every $x \in F^{-1}({\cal B})$, the set of boxes in the $t$-splitter tree of ${\cal B}$ whose index set contains $x$
is a root-to-leaf path in the tree.   This path is equal to the sequence of boxes produced during the execution
of ${\rm{\bf TerminalBox}}_t(x,{\cal B})$.  In particular, the leaf that is reached is the terminal box that is returned
by ${\rm{\bf TerminalBox}}_t(x,{\cal B})$, and is equal to
$\vec{{\cal T}}[x]$ (the unique box ${\cal T} \in \vec{{\cal T}}$ such that $x \in X({\cal T})$).
\end{lemma}

\subsection{Two assumptions about  the random bits}
\label{subsec:assumptions}

As described in Section \ref{subsec:random}, the random bits used in the algorithm are classified as
either {\em secondary random bits} (those used in ${\rm {\bf FindSplitter}}$ and ${\rm {\bf BuildGrid}}$), and  {\em primary
randomness} used within ${\rm {\bf ApproxLIS}}$.
  Note that the procedures ${\rm {\bf FindSplitter}}$ and ${\rm {\bf BuildGrid}}$
do not involve calls to themselves or other procedures, while ${\rm {\bf ApproxLIS}}_t$  makes calls to ${\rm {\bf Classify}}_t$, and ${\rm {\bf Classify}}_t$ makes
calls to ${\rm {\bf ApproxLIS}}_{t-1}$.    The primary random bits used in all calls
to ${\rm {\bf ApproxLIS}}_t$ for a fixed $t$ are called the {\em level $t$ random bits}.

We now identify two assumptions about the random bits used in the algorithm
and show that these assumptions hold with probability $1-n^{\Omega(-(\log n))}$.
These assumptions encapsulate the only properties of  the random bits needed for the error analysis.
In the main analysis performed in the next section, we assume that
all random bits are fixed so that these conditions are satisfied.
The algorithm can then be viewed as deterministic.
The first assumption involves the secondary random bits.

\smallskip
\noindent
{\bf Assumption 1.}  For every possible
choice of arguments, the procedures ${\rm {\bf FindSplitter}}$ and ${\rm {\bf BuildGrid}}$ are reliable according to the definitions in Sections \ref{subsec:splitters} and \ref{subsec:grids}.

\smallskip

Propositions \ref{prop:splitter} and \ref{prop:buildgrid} imply that the probability that a call to ${\rm {\bf FindSplitter}}$ or ${\rm {\bf BuildGrid}}$ is unreliable
is $n^{-\Omega((\log n)}$.  As indicated earlier, there are at most $n^{O(1)}$ different possible arguments to
either procedure, so we can apply a union bound.

\begin{prop}
\label{prop:assumption 1}
The probability that Assumption 1 fails is at most $n^{-\Omega(\log(n)}$.
\end{prop}

We henceforth view the secondary randomness as fixed in a way that satisfies Assumption 1.
We note an important consequence of Assumption 1 that we'll need later.
Recall that for a box ${\cal B}$, with terminal chain $\vec{{\cal T}}$,
each point $P \in {\cal P}^{\circ}({\cal T})$ was found as the splitter of a unique non-terminal box
${\cal H}(P)$.  Under Assumption 1,  and the definition of reliable, each of those splitters is
$(\mu_t,2\gamma w({\cal H}(P)))$-safe for ${\cal H}(P)$.

\begin{prop}
\label{prop:ass 1 cons}
Under assumption 1, for any box ${\cal B}$ with terminal chain $\vec{{\cal T}}$, each of the
points $P \in {\cal P}^{\circ}({\cal T})$ is $(\mu_t,2\gamma w({\cal H}(P)))$-safe for th box ${\cal H}(P)$.
\end{prop}
\iffalse
\smallskip
We will show that Assumption 1 holds with high probability over the random seed. The next section
will assume that the secondary randomness is fixed and Assumption 1 holds.
\subsection{The properties on the random seed} \label{sec:random}
\fi

Next we turn to the second assumption.
Assumption 2 will state the conditions we need for the primary randomness.
To formulate this assumption,
we now  introduce  a somewhat technical definition of \emph{tainted boxes}.
We do not need this definition to analyze the basic  ${\rm {\bf ApproxLIS}}$ algorithm, but
the improved version will need this notion.   We introduce this notion here because
this will allow us to reuse the proof for the improved algorithm.

For any $x \in {\cal B}$ and integer $t$, the output of ${\rm {\bf Classify}}_t(x,{\cal B})$ is either \emph{good}
or \emph{bad}.
The set of indices classified \emph{good} is denoted by $Good_t({\cal B})$.
The procedure ${\rm {\bf ApproxLIS}}_t$ tries to approximate $|Good_t({\cal B})|$ by random sampling.
The randomness used for this random sampling is primary randomness from level $t$.
 is therefore  independent of $Good_t({\cal B})$.

\begin{definition} \label{def:tainted}  Let $\eta$ be the taint parameter specified
within {\rm {\bf BasicMain}}{}.
A box-level pair $({\cal B},t)$ is said to be \emph{tainted} if $t \geq 1$ and ${\bf {\rm  w}}({\cal B})>1$ and at least one of the following holds:
\begin{itemize}

	\item $|{\rm {\bf ApproxLIS}}_t({\cal B})  - |Good_t({\cal B})|| > \eta {\bf {\rm  w}}({\cal B})$.
	\item There exists a  spanning terminal-compatible grid chain $\vec{{\cal C}}$ for ${\cal B}$, such that
	the total width of the boxes $\{{\cal C} \in \vec{{\cal C}} | \textrm{$({\cal C},t-1)$ is tainted}\}$ is at least $\eta {\bf {\rm  w}}({\cal B})$.
\end{itemize}
\end{definition}

\smallskip
\noindent
{\bf Assumption 2.}  There are no tainted box-level pairs.

\begin{prop}
\label{prop:assumption 2}
The probability that Assumption 2 fails   is at most  $n^{-\Omega(\log(n))}$.
\end{prop}

\begin{proof}
By Proposition \ref{prop:hoeff2} for each box-level pair $({\cal B},t)$,  the probability that it satisfies the first condition of tainting, $|{\rm {\bf ApproxLIS}}_t({\cal B})  - |Good_t({\cal B})|| > \eta {\bf {\rm  w}}({\cal B}) (= {\bf {\rm  w}}({\cal B})/(10\log n))$,
holds with probability at most $n^{-\Omega((\log n))}$. Taking a union bound over all box-level  pairs $({\cal B},t)$ ensures that with probability
at least $1-n^{-\Omega(\log(n)}$, there are no box-level pairs that satisfy the first condition for being tainted.  If no box-level pair satisfies the first condition
for being tainted, then a trivial induction on $t$ implies
that  no such pair satisfies the second condition either.

There is a subtle point here.   The set $Good_t({\cal B})$ depends on the random bits, as does the set of indices
sampled by ${\rm {\bf ApproxLIS}}_t({\cal B})$. When we apply Proposition \ref{prop:hoeff2}, the set $A$ is $Good_t({\cal B})$, which
is itself determined randomly.  It is crucial that the
set of indices selected for sampling is uniformly distributed after conditioning on the
set $Good_t({\cal B})$. This is indeed the case.  The set
$Good_t({\cal B})$ is determined by the output of ${\rm {\bf Classify}}_t(x,{\cal B})$ on all $x \in X({\cal B})$.  The random bits needed to determine
these are the secondary random bits, together with the primary random bits of level at most $t-1$.
The choice of the sample in ${\rm {\bf ApproxLIS}}_t({\cal B})$ depends on the primary bits at level $t$, and is therefore
a uniformly distributed sample of the $Good_t({\cal B})$.
\end{proof}

\section{Analysis of correctness}
\label{sec:correctness}

We introduce some notation.

\begin{itemize}
\item ${\tt alis}_t({\cal B})$ is the output of ${\rm {\bf ApproxLIS}}_t({\cal B})$.
\item ${\tt aloss}_t({\cal B})=|{\cal B} \cap {\cal F}| - {\tt alis}_t({\cal B})$.
\item $\nu_t({\cal B})={\tt lis}({\cal B})-{\tt alis}_t({\cal B})$.
\end{itemize}

\begin{theorem}
\label{thm:basic correctness}
Suppose the random bits satisfy Assumptions 1 and 2. For all $t \geq 1$ and boxes ${\cal B} \subseteq {\cal U}(f)$:
\begin{eqnarray}
\label{goal 1}
|\nu_t({\cal B})| & \leq & \tau_t{\tt loss}({\cal B})+\delta_t {\bf {\rm  w}}({\cal B}),
\end{eqnarray}
where $\tau_t=\frac{4}{t}$ and $\delta_t=\frac{t}{\log n}$.
\end{theorem}

\begin{proof}[of \Thm{basic approxlis}]  The claimed run time for
${\rm {\bf BasicMain}}$ follows from \Cor{runtime}.  By \Prop{assumption 1} and \Prop{assumption 2},
Assumptions 1 and 2 hold with probability $1-n^{O(\log(n)}$ and by \Thm{basic correctness} this is enough
to guarantee the desired error bound.
\end{proof}

So it remains to prove \Thm{basic correctness}.
Recall that we refer to the term $\tau_t {\tt loss}({\cal B})$ as {\em primary error} and  to
the term $\delta_t {\bf {\rm  w}}({\cal B})$ as {\em secondary error}.
The secondary error term comes from several sources, including sampling error.
It is a bit of a nuisance to track, but is not the main issue in the analysis;
we will have the
freedom to make $\delta_t$ as small as we like. In contrast,
the coefficient  $\tau_t$ and primary splitter parameter $\mu_t$ are
tightly constrained by the structure of our recursive algorithm.

In \Sec{primary},
we focus on the primary error terms. We structure the analysis to show how $\tau_t$ and  $\mu_t$ were determined. We identify
a series of \emph{secondary error terms} $\zeta_i$ (for $i$ betwen 1 and 5).
In Section \ref{subsec:secondary analysis} we show that the sum of these error terms is bounded above by $\delta_t {\bf {\rm  w}}({\cal B})$.
After isolating these secondary terms we will be left
with a recurrence that constrains $\tau_t$ by an expression involving $\mu_t$ and $\tau_{t-1}$. We
choose $\mu_t$ to minimize this expression, which yields a recurrence inequality for $\tau_t$ in terms of
$\tau_{t-1}$. By inspection, $\tau_t=4/t$ satisfies this recurrence.

\subsection{Setting up the proof} \label{sec:stripnot}

We now summarize some notation about subsets of the box ${\cal B}$.
\begin{itemize}
\item ${\cal L}$ denotes a fixed LIS of ${\cal B}$.
\item   The terminal chain $\vec{{\cal T}}$ spans the box ${\cal B}$, and the associated sequence $\vec{{\cal S}}({\cal T})$ of strips of the form
$\strip{{\cal T}}{{\cal B}}$ is a strip decomposition of ${\cal B}$.
\item For  each terminal box ${\cal T}$, there is an associated grid $\Gamma({\cal T})$ which is constructed by the subroutine
${\rm {\bf BuildGrid}}$, and a grid chain $\vec{{\cal C}}({\cal T})$
in $\Gamma({\cal T})$  which is constructed by a call to ${\rm {\bf GridChain}}$.  (We remind the reader that in the analysis we assume
that we have generated separate random bits for each subroutine and each choice of input parameters so that
the output of the subroutine is specified whether or not we actually execute it.)
\end{itemize}

Much of our analysis focuses on the behavior of ${\cal L}$ as well as our algorithm within each strip.
This motivates the following notation. Refer to \Fig{lis-strip}.
\begin{figure*}[tb]
  \centering
  \subfloat[Dividing ${\cal L}$ into strips]{\includegraphics[width=0.35\textwidth]{figures/lis-strip.pdf} \label{fig:lis-strip}}
  $\qquad \qquad$
  \subfloat[The grid chain $\vec{{\cal D}}({\cal T})$]{\includegraphics[width=0.35\textwidth]{figures/critical.pdf} \label{fig:critical}}
    \caption{(a) The terminal chain $\vec{{\cal T}}$ is given by shaded boxes. The LIS ${\cal L}$ is depicted as a monotonically increasing freeform curve.
    (b) The grid chain $\vec{{\cal D}}({\cal T})$ is denoted by the shaded boxes.
The set $\vec{{\cal E}}$ of boxes (not indicated explicitly) are the boxes intersecting the LIS that are not tainted.}
\end{figure*}
For each terminal box ${\cal T}$:
\label{subsec:more defs}
\begin{itemize}
	\item $\beta({\cal T}) = |(\strip{{\cal T}}{{\cal B}}) \cap {\cal F}|$.
	\item ${\cal L}({\cal T})={\cal L} \cap (\strip{{\cal T}}{{\cal B}})$.
	\item ${\cal L}^{in}({\cal T}) = {\cal L} \cap {\cal T}$.
	\item ${\cal L}^{out}({\cal T}) = {\cal L} \cap ((\strip{{\cal T}}{{\cal B}}) - {\cal T})$.
\end{itemize}

 We give some notation regarding critical boxes.
\begin{itemize}
	\item The concatenation of the $\vec{{\cal C}}({\cal T})$ for all ${\cal T} \in \vec{{\cal T}}$ is a box chain $\vec{{\cal C}}$ called the {\em critical chain}. Members of this chain are {\em critical boxes}.
	\item For index $x  \in X({\cal B})$, $\vec{{\cal C}}[x]$ denotes the unique critical box ${\cal C}$ such that $x \in X({\cal C})$.
	Observe that for each $x \in F^{-1}({\cal B})$, the function ${\rm {\bf CriticalBox}}_t(x)$ returns ${\cal C}[x]$.
\end{itemize}

For each terminal box ${\cal T}$, let $\vec{{\cal D}}({\cal T})$ denote the grid chain of $\Gamma({\cal T})$ containing the maximum number
of points from ${\cal L}$. Refer to \Fig{critical}.
We will actually use the subsequence $\vec{{\cal E}}({\cal T})$, which consists of
boxes ${\cal E} \in \vec{{\cal D}}({\cal T})$ such that ${\cal E} \cap {\cal L} \neq \emptyset$ and $({\cal E},t-1)$ is not tainted.
The following quantities are used heavily in our proof.
\begin{itemize}
\item ${\tt out}(\vec{{\cal D}}({\cal T})) = \beta({\cal T}) - \sum_{{\cal D} \in \vec{{\cal D}}({\cal T})} |{\cal D} \cap {\cal F}|$.
(Number of ${\cal F}$-points in $({\cal T}|{\cal B})$ outside $\vec{{\cal D}}({\cal T})$.)
\item ${\tt out}(\vec{{\cal E}}({\cal T})) = \beta({\cal T}) - \sum_{{\cal E} \in \vec{{\cal E}}({\cal T})} |{\cal E} \cap {\cal F}|$.
(Number of ${\cal F}$-points in $({\cal T}|{\cal B})$ outside $\vec{{\cal E}}({\cal T})$.)
\item ${\tt loss}(\vec{{\cal E}}({\cal T})) = \sum_{{\cal E} \in \vec{{\cal E}}({\cal T})} {\tt loss}({\cal E})$.  (Recall that  ${\tt loss}({\cal E})=|{\cal E} \cap {\cal F}| - {\tt lis}({\cal E})]$, so ${\tt loss}(\vec{{\cal E}})$ is the number
of ${\cal F}$-points from $\bigcup_{{\cal E} \in \vec{{\cal E}}({\cal T})} {\cal E}$  that are missed by the union of
the  LIS  for ${\cal E} \in \vec{{\cal E}}({\cal T})$.)
\item ${\tt aloss}_t(\vec{{\cal E}}({\cal T})) = \sum_{{\cal E} \in \vec{{\cal E}}({\cal T})} {\tt aloss}({\cal E})$. (Recall that
${\tt aloss}({\cal E})=[|{\cal E} \cap {\cal F}| - {\tt alis}_t({\cal E})]$ so ${\tt aloss}_t(\vec{{\cal E}}({\cal T}))$ is the
estimate of ${\tt loss}(\vec{{\cal E}}({\cal T}))$ using ${\tt alis}_t$ in place of {\tt lis}.)
\end{itemize}
We begin with a few simple propositions.  The first, which follows immediately from the definition
of ${\rm {\bf Classify}}$ specifies what happens in the base case ${\bf {\rm  w}}({\cal B})=1$.
\begin{prop}
\label{prop:narrow}
If ${\cal B}$ is a box of width 1, then   ${\tt alis}_t({\cal B})={\tt lis}({\cal B})$ and
$\nu_t({\cal B})=0$. For the unique $x \in X({\cal B})$, $x \in Good_t$ if and only if $F(x) \in {\cal B}$.
\end{prop}
Henceforth, we assume that ${\cal B}$ has width at least 2. We remind that $Good_t({\cal B})$ denotes the set of indices
ini $X({\cal B})$ classified as  {\em good} by ${\rm {\bf Classify}}_t({\cal B})$.
The quantity ${\tt alis}_t({\cal B})$ returned by the algorithm is an estimate of $|Good_t({\cal B})|$.
\begin{prop}
\label{prop:good}
For any box ${\cal B}$ of width at least 2, and $t \geq 1$:
\begin{enumerate}
\item $Good_t({\cal B})$ is equal to the union over critical boxes ${\cal C}$ of $Good_{t-1}({\cal C})$.
\item $Good_t({\cal B})$ indexes an increasing sequence in ${\cal B}$ and thus $|Good_t({\cal B})| \leq {\tt lis}({\cal B})$.
\end{enumerate}
\end{prop}
\begin{proof}
The first part follows from the main case of ${\rm {\bf Classify}}_t$.
For the second part, if $x,y \in Good_t({\cal B})$
then either $F(x)$ and $F(y)$ belong to different boxes of $\vec{{\cal C}}$
or $F(x),F(y)$ lie in the same critical box ${\cal C}$.
In the former case, they are comparable since the boxes lie in a box chain.
In the latter case, they are both classified good by ${\rm {\bf Classify}}_{t-1}(\cdot,{\cal C})$
and must be comparable by induction on $t$.
\end{proof}

\subsection{Components of secondary error }
\label{subsec:secondary components}

In this section we identify five components of secondary error, denoted $\zeta_1,\ldots,\zeta_5$.
We gather the definitions together here for easy reference, but the motivation for each term comes from the analysis
presented in Section \ref{sec:primary}.

\iffalse
Each definition is followed by an informal explanation as to why the term is small, but the proofs are deferred to
Section \ref{subsec:secondary analysis}.
\fi

\iffalse
The output ${\tt alis}_t({\cal B})$ is an estimate of $|Good_t({\cal B})|$ obtained through random sampling. Hence, we expect the following error term to be small:
\fi

$$\zeta_1 = {\tt alis}_t({\cal B}) - |Good_t({\cal B})|.$$

Recall that the subroutine ${\rm{\bf TerminalBox}}_t$ together with the secondary random bits determine the terminal  box chain $\vec{{\cal T}}$.
The remaining four secondary error terms are associated to each individual terminal box ${\cal T}$  in $\vec{{\cal T}}$; the secondary
error will be obtained by summing these over all ${\cal T}$. We define:

\begin{eqnarray*}
\zeta_2({\cal T}) & = & \sum_{{\cal C} \in \vec{{\cal C}}({\cal T})} {\tt alis}_{t-1}({\cal C}) - \sum_{{\cal C} \in \vec{{\cal C}}({\cal T})}|Good_{t-1}({\cal C})|.\\
\zeta_3({\cal T}) & = & |{\cal L}^{in}({\cal T})| - \sum_{{\cal E} \in \vec{{\cal E}}({\cal T})} |{\cal E} \cap {\cal L}|.\\
\zeta_4({\cal T}) &= &|{\cal L}^{out}({\cal T})| - \mu_t \cdot {\tt out}(\vec{{\cal E}}({\cal T})).\\
\zeta_5({\cal T})
& = &  \mu_t \cdot {\tt aloss}_{t-1}(\vec{{\cal E}}({\cal T})) - (1-\mu_t)\cdot {\tt out}(\vec{{\cal E}}({\cal T})).
\end{eqnarray*}

\iffalse
This error term can be viewed as follows. $|{\cal L}^{in}({\cal T})|$ counts the number of points of the LIS ${\cal L}$ that are inside of ${\cal T}$.  The term being subtracted off counts a subset of those points, and the difference
counts the number of points of ${\cal L}$ that don't lie in $\vec{{\cal D}}({\cal T})$ plus the number of points of ${\cal L}$ that lie in tainted boxes of $\vec{{\cal D}}({\cal T})$.
The grid approximation lemma (\Lem{grid-approx}) says that the first quantity is small, while under assumption 2, there are no tainted boxes so the second quantity is 0.

	Note that $|{\cal L}^{out}|$ is the number of LIS points that belong to the strip ${\cal T} | {\cal B}$ but not to  ${\cal T}$.
	Refer to \Fig{lis-strip}. These are exactly the LIS points in ${\cal T} | {\cal B}$ that are violations with the (bottom-right and top-left)
	corners of the ${\cal T}$, which are splitters. Because the splitters are $(\mu_t,\gamma {\bf {\rm  w}}({\cal T}))$-safe, it can be shown that $|{\cal L}^{out}|$ can not be much larger than
	$\mu_t\beta({\cal T})$ ($\beta({\cal T}) = |({\cal T}|{\cal B}) \cap {\cal F}|$). For technical reasons arising in the analysis, we subtract out $\Lambda({\cal T})$.

	This is motivated by the dichotomy lemma (\Lem{dichotomy}). Since ${\cal T}$ is a terminal box, no grid chain in $\Gamma({\cal T})$
	can have more than (roughly) $(1-\mu_t)\beta({\cal T})$ points plus $\mu_t$ times the number of safe points.
          We subtract $\widehat{\kappa}({\cal T})$ for technical reasons arising in the analysis
\fi

\subsection{Transforming our goal}
\label{sec:transform}

Our goal is to upper bound $|\nu_t({\cal B})|=|{\tt lis}({\cal B})-{\tt alis}_t({\cal B})|$.
We start from the definition of $\nu_t({\cal B})$, substitute $|Good_t({\cal B})|+ \zeta_1$ for ${\tt alis}_t({\cal B})$
and apply the inequality (from \Prop{good}) ${\tt lis}({\cal B}) \geq Good_t({\cal B})$:
\begin{eqnarray*}
|\nu_t({\cal B})|&=&|{\tt lis}({\cal B})-{\tt alis}_t({\cal B})|\\
& = & |{\tt lis}({\cal B}) - |Good_t({\cal B})| -\zeta_1|\\
&\leq & {\tt lis}({\cal B}) - |Good_t({\cal B})| + |\zeta_1|
\end{eqnarray*}
Define:
\[
\Delta_t={\tt lis}({\cal B})-|Good_t({\cal B})|-\tau_t{\tt loss}({\cal B}),
\]
Our goal (\ref{goal 1}) will follow from:

\[
\Delta_t \leq \delta_t{\bf {\rm  w}}({\cal B})-|\zeta_1|.
\]

Noting that ${\tt lis}({\cal B})=|{\cal L}|$ and ${\tt loss}({\cal B})=|{\cal B} \cap {\cal F}|-|{\cal L}|$. we have:

\[
\Delta_t= (1+\tau_t)|{\cal L}|-|Good_t({\cal B})|-\tau_t|{\cal B} \cap {\cal F}|
\]

\iffalse
\begin{eqnarray}
& {\tt lis}({\cal B}) - |Good_t({\cal B})| + |\zeta_1| \leq \tau_t {\tt loss}({\cal B}) + \delta_t{\bf {\rm  w}}({\cal B}) \nonumber \\
\Longleftrightarrow & |{\cal B} \cap {\cal F}| - |Good_t({\cal B})| - |{\cal B} \cap {\cal F}| + |{\cal L}| - \tau_t (|{\cal B}\ \cap {\cal F}| - |{\cal L}|) \leq \delta_t{\bf {\rm  w}}({\cal B}) - |\zeta_1| \nonumber \\
\Longleftrightarrow & |{\cal B} \cap {\cal F}| - |Good_t({\cal B})| - (1+\tau_t) (|{\cal B} \cap {\cal F}| - |{\cal L}|) \leq \delta_t {\bf {\rm  w}}({\cal B})- |\zeta_1| \label{eq:goal12}
\end{eqnarray}
\fi
Each term on the right counts a subset of ${\cal B} \cap {\cal F}$. Partitioning the box ${\cal B}$ into the strips $({\cal T}|{\cal B})$
for each terminal box ${\cal T}$, we define  $\Delta_t({\cal T})$ as follows to be the contribution of the points in
${\cal T}|{\cal B}$ to the right hand side (using the notation in Section \ref{sec:stripnot}
and noting that $Good_t({\cal B}) \cap ({\cal T}|{\cal B}) \subseteq {\cal T}$):

\begin{align} \label{eq:Delta}
\Delta_t({\cal T}) & = (1+\tau_t) |{\cal L}({\cal T})| -  |Good_t({\cal B}) \cap {\cal T} | - \tau_t \beta({\cal T})
\end{align}

Our goal now is to show:
\begin{eqnarray}
\label{eq:goal12.1}
\sum_{{\cal T} \in \vec{{\cal T}}} \Delta_t(T) & \leq & \delta_t {\bf {\rm  w}}({\cal B})-|\zeta_1|.
\end{eqnarray}
This is broken down into two steps. We use the notation $x^+ = \max(x,0)$.

\begin{claim} \label{clm:primary} (Primary error)
Let $t \geq 1$ and let ${\cal B}$ be a box such that $({\cal B},t)$ is untainted.  Let $\vec{{\cal T}}$ be the
terminal chain associated with a call of ${\rm {\bf ApproxLIS}}_t({\cal B})$.  We have:
\begin{eqnarray}
\label{sum Delta}
\sum_{{\cal T} \in \vec{{\cal T}}} \Delta_t({\cal T}) & \leq & (\delta_t - \delta_1) {\bf {\rm  w}}({\cal B})+\sum_{{\cal T} \in \vec{{\cal T}}}  (\zeta_2({\cal T}) + 5 \zeta_3({\cal T})^+ + 5\zeta_4({\cal T})^+ + 2 \zeta_5({\cal T})^+).
\end{eqnarray}
\end{claim}

\begin{claim} \label{clm:secondary} (Secondary error)
With the same hypotheses as in Claim \ref{clm:primary} together with Assumption 1, we have:
\begin{eqnarray}
\label{goal 1.3}
|\zeta_1|+\sum_{{\cal T} \in \vec{{\cal T}}} (\zeta_2({\cal T}) + 5 \zeta_3({\cal T})^+ + 5\zeta_4({\cal T})^+ + 2 \zeta_5({\cal T})^+) & \leq & \delta_1{\bf {\rm  w}}({\cal B}).
\end{eqnarray}
\end{claim}

Summing these bounds yields \Eqn{goal12.1}, which proves \Thm{basic correctness}.

\subsection{Bounding the primary error} \label{sec:primary}
Here we prove Claim \ref{clm:primary}.
The proof is by induction on $t$.  The base case is $t=1$.  We prove  the base case and the induction step together,
indicating where they differ.

The following claim  bounds $\Delta_t({\cal T})$ in a more convenient form.

\begin{claim} \label{clm:delta}
For each terminal box ${\cal T}$,
\begin{eqnarray*}
\Delta_t({\cal T}) & \leq & (1+\tau_t)|{\cal L}^{out}({\cal T})| - \tau_t \cdot {\tt out}(\vec{{\cal E}}({\cal T}))
- (1+\tau_t) \cdot {\tt loss}(\vec{{\cal E}}({\cal T})) + {\tt aloss}_{t-1}(\vec{{\cal E}}({\cal T})) \\
&&+\zeta_2({\cal T})+(1+\tau_t)\zeta_3({\cal T}).
\end{eqnarray*}
\end{claim}

\iffalse
The expression on the right hand side does not seem to have a good intuitive interpretation.
It arises from a sequence of natural manipulations done in the proof.
 Excluding the secondary error terms,
we see that the right hand side is the difference of two terms, the first being a multiple
of $\beta({\cal T})$ (which is $({\cal T}|{\cal B})$),  and the second being
$\Lambda({\cal T}) - \kappa({\cal T})$ which
is the number of points \emph{missed} by the LIS that do not lie in the boxes of  $\vec{{\cal E}}$. (In terms of the
high level description, this subtracted term reflects the gain in the analysis due to boosting).
\fi

\begin{proof}
By Proposition \ref{prop:good}, $|Good_t({\cal B})\cap {\cal T}|=\sum_{{\cal C} \in \vec{{\cal C}}({\cal T})} |Good_{t-1}({\cal C})|$. Thus,
(\ref{eq:Delta}) can be rewritten as:
\begin{eqnarray}
\nonumber
\Delta_t({\cal T}) & = & (1+\tau_t) |{\cal L}({\cal T})| - \sum_{{\cal C} \in \vec{{\cal C}}({\cal T})} |Good_{t-1}({\cal C})| - \tau_t \beta({\cal T})
\end{eqnarray}

We replace $|Good_{t-1}({\cal C})|$ by ${\tt alis}_{t-1}({\cal C})$, using $\zeta_2({\cal T})$.

\begin{eqnarray*}
\label{eq:Delta2}
\Delta_t({\cal T})
& = & (1+\tau_t)|{\cal L}({\cal T})| - \sum_{{\cal C} \in \vec{{\cal C}}({\cal T})} {\tt alis}_{t-1}({\cal C}) - \tau_t \beta({\cal T}) + \zeta_2({\cal T})
\end{eqnarray*}

By construction, $\vec{{\cal C}}({\cal T})$  is a grid-chain with respect to the grid
$\Gamma({\cal T})$
that maximizes the sum $\sum_{{\cal C} \in \vec{{\cal C}}({\cal T})} {\tt alis}_{t-1}({\cal C})$.  This sum is at least
$\sum_{{\cal E} \in \vec{{\cal E}}({\cal T})} {\tt alis}_{t-1}({\cal E})$, since $\vec{{\cal E}}$ is a subsequence of a grid-chain.
\begin{eqnarray*}
\nonumber
\Delta_t({\cal T}) & \leq &(1+\tau_t)|{\cal L}({\cal T})| - \sum_{{\cal E} \in \vec{{\cal E}}({\cal T})} {\tt alis}_{t-1}({\cal E}) - \tau_t \beta({\cal T}) + \zeta_2({\cal T})
\end{eqnarray*}
Now, $|{\cal L}({\cal T})|=|{\cal L}^{in}({\cal T})|+|{\cal L}^{out}({\cal T})|$.  Using the definition of $\zeta_3({\cal T})$,
$|{\cal L}^{in}|=\zeta_3({\cal T}) + \sum_{{\cal E} \in \vec{{\cal E}}({\cal T})} |{\cal E} \cap {\cal L}|$;  the grid approximation
lemma (\Lem{grid-approx}) will be used to show that $\zeta_3({\cal T})$ is small.
Furthermore, for each ${\cal E} \in \vec{{\cal E}}({\cal T})$, $|{\cal E} \cap {\cal L}| \leq {\tt lis}({\cal E})$. Combining,
\begin{eqnarray*}
\Delta_t({\cal T}) & \leq &(1+\tau_t)|{\cal L}^{out}({\cal T})| + (1+\tau_t)\sum_{{\cal E} \in \vec{{\cal E}}({\cal T})} {\tt lis}({\cal E})
- \sum_{{\cal E} \in \vec{{\cal E}}({\cal T})} {\tt alis}_{t-1}({\cal E}) - \tau_t \beta({\cal T}) \\
& & + \zeta_2({\cal T})+(1+\tau_t)\zeta_3({\cal T})
\end{eqnarray*}
Substituting ${\tt lis}({\cal E}) = |{\cal E} \cap {\cal F}|-{\tt loss}({\cal E})$, and ${\tt alis}_t({\cal E})=|{\cal E} \cap {\cal F}|-{\tt aloss}({\cal E})$ and
performing some simple algebraic manipulations completes the proof:
\begin{eqnarray*}
\Delta_t({\cal T}) & \leq &(1+\tau_t)|{\cal L}^{out}({\cal T})| + (1+\tau_t)\Big[\sum_{{\cal E} \in \vec{{\cal E}}({\cal T})} |{\cal E} \cap {\cal F}|
- {\tt loss}(\vec{{\cal E}}({\cal T}))\Big]
- \Big[\sum_{{\cal E} \in \vec{{\cal E}}({\cal T})} |{\cal E} \cap {\cal F}|-{\tt aloss}_{t-1}(\vec{{\cal E}}({\cal T}))\Big] \\
& & - \tau_t \beta({\cal T}) + \zeta_2({\cal T})+(1+\tau_t)\zeta_3({\cal T}) \\
& = & (1+\tau_t)|{\cal L}^{out}({\cal T})| - \tau_t \Big[\beta({\cal T}) - \sum_{{\cal E} \in \vec{{\cal E}}({\cal T})} |{\cal E} \cap {\cal F}|\Big]
- (1+\tau_t) \cdot {\tt loss}(\vec{{\cal E}}({\cal T})) + {\tt aloss}_{t-1}(\vec{{\cal E}}({\cal T})) \\
&&+\zeta_2({\cal T})+(1+\tau_t)\zeta_3({\cal T}) \\
& = & (1+\tau_t)|{\cal L}^{out}({\cal T})| - \tau_t \cdot {\tt out}(\vec{{\cal E}}({\cal T}))
- (1+\tau_t) \cdot {\tt loss}(\vec{{\cal E}}({\cal T})) + {\tt aloss}_{t-1}(\vec{{\cal E}}({\cal T})) \\
&&+\zeta_2({\cal T})+(1+\tau_t)\zeta_3({\cal T}).
\end{eqnarray*}
\end{proof}

\begin{claim}
${\tt loss}(\vec{{\cal E}}({\cal T})) \geq K_t[{\tt aloss}_{t-1}(\vec{{\cal E}}({\cal T}))-\delta_{t-1} {\bf {\rm  w}}({\cal T})]$, where
$K_1=0$ and $K_t = 1/(1+\tau_{t-1})$ for $t \geq 2$.
\end{claim}

\begin{proof} For $t=1$, simply note that the loss is always non-negative.

Suppose $t \geq 2$.
By construction of $\vec{{\cal E}}$, for each ${\cal E} \in \vec{{\cal E}}$, $({\cal E},t-1)$ is not tainted.
Using the induction hypothesis, we can relate ${\tt loss}({\cal E})$ to ${\tt aloss}_{t-1}({\cal E})$.
The proof is completed by summing the following bound over all ${\cal E} \in \vec{{\cal E}}({\cal T})$.

\begin{eqnarray*}
{\tt aloss}_{t-1}({\cal E}) \leq (1+\tau_{t-1}) {\tt loss}({\cal E}) + \delta_{t-1} {\bf {\rm  w}}({\cal E}) \\
\Longleftrightarrow {\tt loss}({\cal E}) \geq \frac{{\tt aloss}_{t-1}({\cal E})}{1+\tau_{t-1}} - \frac{\delta_{t-1} {\bf {\rm  w}}({\cal E})}{1+ \tau_{t-1}}
\end{eqnarray*}
\end{proof}
Combining this claim with \Clm{delta} gives:

\begin{eqnarray*}
\Delta_t({\cal T}) & \leq &(1+\tau_t)|{\cal L}^{out}({\cal T})| -\tau_t \cdot {\tt out}(\vec{{\cal E}}({\cal T})) + [1-K_t(1+\tau_t)]\cdot{\tt aloss}_{t-1}(\vec{{\cal E}}({\cal T}))\\
&& +\zeta_2({\cal T})+(1+\tau_t)\zeta_3({\cal T})+K_t\delta_{t-1} {\bf {\rm  w}}({\cal T}).
\end{eqnarray*}
We use $\zeta_4({\cal T})$ and $\zeta_5({\cal T})$ to eliminate $|{\cal L}^{out}|$ and ${\tt aloss}_{t-1}(\vec{{\cal E}}({\cal T}))$.
\begin{eqnarray}
\Delta_t({\cal T}) & \leq &(1+\tau_t)[\mu_t\cdot{\tt out}(\vec{{\cal E}}({\cal T})) + \zeta_4({\cal T})] -\tau_t \cdot {\tt out}(\vec{{\cal E}}({\cal T})) + \nonumber \\
&&[1-K_t(1+\tau_t)]\mu^{-1}_t[(1-\mu_t)\cdot{\tt out}(\vec{{\cal E}}({\cal T})) + \zeta_5({\cal T})]
 +\zeta_2({\cal T})+(1+\tau_t)\zeta_3({\cal T})+K_t\delta_{t-1} {\bf {\rm  w}}({\cal T}) \nonumber \\
& = & [(1+\tau_t)\mu_t - \tau_t + (1-K_t(1+\tau_t))(\mu^{-1}_t - 1)] {\tt out}(\vec{{\cal E}}({\cal T})) \nonumber \\
& & +\zeta_2({\cal T})+(1+\tau_t)\zeta_3({\cal T}) + (1+\tau_t)\zeta_4({\cal T}) + [1-K_t(1+\tau_t)]\mu^{-1}_t \zeta_5({\cal T}) + K_t\delta_{t-1} {\bf {\rm  w}}({\cal T}) \label{eq:errors}
\end{eqnarray}
Our focus is on the coefficient of ${\tt out}(\vec{{\cal E}}({\cal T}))$ and the parameters will be chosen to ensure
this is negative.
\begin{eqnarray*}
& & (1+\tau_t)\mu_t - \tau_t + [1-K_t(1+\tau_t)](\mu^{-1}_t - 1) \\
& = & (1+\tau_t)\mu_t - (1+\tau_t) + K_t(1+\tau_t) + [1-K_t(1+\tau_t)]\mu^{-1}_t \\
& = & \mu^{-1}_t[ (1+\tau_t)\mu^2_t - (1+\tau_t)(1-K_t) \mu_t - K_t(1+\tau_t) + 1] \\
& = & \mu^{-1}_t\{ (1+\tau_t)[\mu^2_t - (1-K_t)\mu_t - K_t] + 1\}
\end{eqnarray*}
Setting $\mu_t = (1-K_t)/2$ (which is positive since $K_t < 1$) minimizes the inner quadratic. The condition that this expression
is non-positive is equivalent to the following.
\begin{align*}
(1+\tau_t)[(1-K_t)^2/4 - (1-K_t)^2/2 - K_t] \leq -1
\Longleftrightarrow (1+\tau_t) \geq \frac{4}{(1+K_t)^2}
\end{align*}
For $t=1$, we have $K_t=0$ and the requirement is $\tau_t \geq 3$.  For $t \geq 2$,
$K_t=1/(1+\tau_{t-1})$ and the requirement becomes:
\[
\tau_t \geq \frac{4\tau_{t-1} + 3\tau^2_{t-1}}{(2+\tau_{t-1})^2}
\]
Guessing a solution of the form $\tau_t = C/t$, one verifies that $\tau_t=4/t$ works.  The
righthand side becomes

\begin{eqnarray*}
\frac{\frac{16}{t-1}+\frac{48}{(t-1)^2}}{(2+\frac{4}{t-1})^2} = \frac{16(t-1)+48}{(2(t-1)+4)^2} = \frac{4t+8}{(t+1)^2} \leq \frac{4t+8+\frac{4}{t}}{(t+1)^2} = \frac{4}{t}.
\end{eqnarray*}
\iffalse
\begin{eqnarray*}
\frac{(2/\tau_{t-1} + 1)^2}{4/\tau_{t-1} + 3} = \frac{[(t-1)/2 + 1]^2}{t+2} = \frac{(t+1)^2}{4(t+2)} \geq \frac{t}{4}
\end{eqnarray*}
\fi

Thus the coefficient of ${\tt out}(\vec{{\cal E}}(T))$ in \Eqn{errors} is nonpositive.  To further simplify the bound
note that $K_t = (t-1)/(t+3) \leq 1$	and  $(1-K_t(1+\tau_t))/\mu_t  =2 (1-K_t(1+\tau_t))/(1-K_t) \leq 2$.
Thus from \Eqn{errors} we deduce:
\begin{eqnarray*}
\Delta_t({\cal T})
 &\leq & \zeta_2({\cal T})+(1+\tau_t)\zeta_3({\cal T})+(1+\tau_t)\zeta_4({\cal T})+ \zeta_5({\cal T})(1-K_t(1+\tau_t))/\mu_t+ K_t\delta_{t-1} {\bf {\rm  w}}({\cal T}) \\
 &\leq & \zeta_2({\cal T})+ 5\zeta_3({\cal T})+ 5 \zeta_4({\cal T})+ 2\zeta_5({\cal T})+ (\delta_{t}-\delta_1) {\bf {\rm  w}}({\cal T}).
\end{eqnarray*}
Summing over ${\cal T}$ completes the proof of the claim.
\smallskip
\iffalse
For $t=1$, we set $\mu_1=1/2$ and then it suffices to set $\tau_1 \geq 3$.

For $t \geq 1$,  we view the expression multiplying $\beta({\cal T})-\Lambda({\cal T})$ as a function of $4\mu_t$
and choose $\mu_t$ to minimize
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

\begin{eqnarray*}
\zeta_2({\cal T}) & = & \sum_{{\cal C} \in \vec{{\cal C}}({\cal T})} {\tt alis}_{t-1}({\cal C}) - \sum_{{\cal C} \in \vec{{\cal C}}({\cal T})}|Good_{t-1}({\cal C})|.\\
\zeta_3({\cal T}) & = & |{\cal L}^{in}({\cal T})| - \sum_{{\cal D} \in \vec{{\cal E}}({\cal T})} |{\cal D} \cap {\cal L}|.\\
\zeta_4({\cal T}) &= &|{\cal L}^{out}({\cal T})| - \mu_t(\beta({\cal T}) - \Lambda({\cal T})).\\
\zeta_5({\cal T})&=& \mu_t(\Lambda({\cal T}) - \widehat{\kappa}({\cal T})) - (1-\mu_t)(\beta({\cal T})-\Lambda).
\end{eqnarray*}

We now apply a sequence of elementary manipulations to the inequality:
\begin{eqnarray*}
\nonumber
\Delta_t({\cal T}) & \stackrel{(A1)}{\leq} & \beta({\cal T}) -  \widehat{\kappa}({\cal T}) - (1+\tau_t) (\beta({\cal T}) -  |{\cal L}^{out}({\cal T})| - |{\cal L}^{in}({\cal T})|)  +\zeta_2({\cal T})\\
& \stackrel{(A2)} {\leq} & \beta({\cal T}) -  \widehat{\kappa}({\cal T}) - (1+\tau_t) [(1-\mu_t)\beta({\cal T}) + \mu_t\Lambda({\cal T}) -\kappa({\cal T})] \\
& & +\zeta_2({\cal T})+ (\zeta_3({\cal T}) + \zeta_4({\cal T}))(1+\tau_t) \\
& \stackrel{(A3)}{\leq} & [1 - (1+\tau_t)(1-\mu_t)]\beta({\cal T}) - (1+\tau_t)(\Lambda({\cal T})-\kappa({\cal T})) + (1+\tau_t)(1-\mu_t)(\Lambda({\cal T}) -\widehat{\kappa}({\cal T}))\\
& &+(\tau_t-\mu_t-\tau_t\mu_t)\widehat{\kappa}({\cal T}) +\zeta_2({\cal T})+ (\zeta_3({\cal T}) + \zeta_4({\cal T}))(1+\tau_t) \\
& \stackrel{(A4)}{\leq} & [1 - (1+\tau_t)(1-\mu_t)]\beta({\cal T}) - (1+\tau_t)(\Lambda({\cal T})-\kappa({\cal T})) + (1+\tau_t)(1-\mu_t)(1-\mu_t)\beta({\cal T}) \\
& & +(\tau_t-\mu_t-\tau_t\mu_t)\widehat{\kappa}({\cal T})+\zeta_2({\cal T})+ (\zeta_3({\cal T}) + \zeta_4({\cal T}))(1+\tau_t) + (1+\tau_t)(1-\mu_t)\zeta_5({\cal T}) \\
& \stackrel{(A5)}{\leq} & [1-(1+\tau_t)(1-\mu_t)\mu_t]\beta({\cal T}) - (1+\tau_t)(\Lambda({\cal T})-\kappa({\cal T}))+(\tau_t-\mu_t-\tau_t\mu_t)\widehat{\kappa}({\cal T})\\
& & + \zeta_2({\cal T})+(\zeta_3({\cal T})+\zeta_4({\cal T})+(1-\mu_t)\zeta_5)(1+\tau_t).
\end{eqnarray*}
For (A1), we split ${\cal L}({\cal T})$ into ${\cal L}^{in}({\cal T})$ and ${\cal L}^{out}({\cal T})$.
For (A2), we use the definitions of the error terms $\zeta_3({\cal T})$ and $\zeta_4({\cal T})$
to  replace $|{\cal L}^{in}({\cal T})|$ by $\sum_{{\cal D} \in \vec{{\cal E}}({\cal T})} |{\cal D} \cap {\cal L}| + \zeta_3({\cal T}) \leq
 \kappa({\cal T}) + \zeta_3({\cal T})$, and replace
$|{\cal L}^{out}({\cal T})|$ by $\mu_t\beta({\cal T}) - \mu_t\Lambda({\cal T}) + \zeta_4({\cal T})$.
We also use the replacement $\Lambda({\cal T}) - \widehat{\kappa}({\cal T})$ with $(1-\mu_t)\beta({\cal T}) + \zeta_5({\cal T})$.

We use the fact that $(1+\tau_t)(1-\mu_t) = (1+4/t)(1-2/(t+3)) = (t+4)(t+1)/[t(t+3)] \geq 1$.

Now for the proof of \Clm{primary}. We structure this proof to show how the quantities $\mu_t = 2/(t+3)$ and $\tau_t = 4/t$ are chosen.

\begin{proof}
Consider the case $t=1$. Since
$\Lambda({\cal T})-\kappa({\cal T}) \geq 0$, we can omit this term to get:
\begin{eqnarray}
\Delta_1({\cal T}) & \leq & \beta({\cal T})(1  - (1+\tau_1)(1-\mu_1)\mu_1) \nonumber \\
&& +\zeta_2({\cal T})+(\zeta_3({\cal T})+\zeta_4({\cal T})+(1-\mu_t)\zeta_5({\cal T}))(1+\tau_t) \label{eqn:delta}.
\end{eqnarray}
We want the primary term (the expression involving $\beta({\cal T})$) to be nonpositive.
Thus, we choose $\mu_1=1/2$ which minimizes the coefficient of $\beta({\cal T})$.
It suffices to set $\tau_1 = 3$, but we choose $\tau_1=4$ for convenience in later steps.
This leaves only the secondary error terms, completing the proof for $t=1$.

We proceed to the case $t\geq2$.  We replace
$(1+\tau_t)(\Lambda({\cal T})-\kappa({\cal T}))$ by a lower bound.

We plug this in the bound of \Clm{delta} and use simple constant bounds for the coefficients of the secondary error terms.
We also note that $\delta_{t-1} = \delta_t - \delta_1$.
\begin{align}
\nonumber
\Delta({\cal T})
\leq & \ [1-(1+\tau_t)(1-\mu_t)\mu_t]\beta({\cal T}) - \frac{(1+\tau_t)(1-\mu_t)}{1+\tau_{t-1}}\beta({\cal T})\\
& +\zeta_2({\cal T})+(\zeta_3({\cal T})+\zeta_4({\cal T})+(1-\mu_t-\frac{1}{1+\tau_{t-1}})\zeta_5)(1+\tau_t)+\frac{1+\tau_t}{1+\tau_{t-1}}\delta_{t-1}{\bf {\rm  w}}({\cal T})\\
\nonumber
\leq & \ \Big[1-(1+\tau_t)(1-\mu_t)(\mu_t+\frac{1}{1+\tau_{t-1}})\Big]\beta({\cal T}) + (\delta_t - \delta_1){\bf {\rm  w}}({\cal T})\\
\label{Delta 4}
& +\zeta_2({\cal T})+5(\zeta_3({\cal T})^+ +\zeta_4({\cal T})^+ + \zeta_5({\cal T})^+)
\end{align}

The proof will be completed by making the primary error term nonpositive. So we set
$\mu_t=\tau_{t-1}/2(1+\tau_{t-1})$ to maximize the expression multiplying $1+\tau_t$.
We obtain the following recurrence inequality for $\tau_t$.
\begin{eqnarray*}
\Big(\frac{2\tau_{t-1}+2}{\tau_{t-1}+2}\Big)^2 -1  & \leq  & \tau_t.
\end{eqnarray*}
Guessing a solution of the form $\tau_t=c/t$ for some constant $c$, one sees that $\tau_t=4/t$ works (matching the
base case $\tau_1=4$).
\begin{eqnarray*}
\Big(\frac{2\tau_{t-1}+2}{\tau_{t-1}+2}\Big)^2 -1 = \Big(\frac{4/(t-1)+1}{2/(t-1)+1}\Big)^2 -1 & = & \Big(\frac{t+3}{t+1}\Big)^2 - 1 \\
& = & \frac{4(t+2)}{(t+1)^2} \leq \frac{4}{t} = \tau_t
\end{eqnarray*}
The corresponding value for $\mu_t$ is $2/(t+3)$.
\end{proof}

\fi

{\bf Remark.} The reader should note that in the proof of \Clm{primary},
the only thing used about the algorithm ${\rm{\bf TerminalBox}}$ is \Lem{terminal}. The
exact details of \emph{how} the terminal chain was chosen are not used. Similarly, the particular choice of $\delta_1$ was
not used; we only use the fact that $\delta_t = t\delta_1$.
The assumptions on the random seed are just Assumption 1 and that fact that $({\cal B},t)$ is not tainted.
The specifics of the definition of tainted do no enter this proof.
All the calculations were basically algebraic manipulations (most details about the algorithm
have been pushed into the secondary error terms).
We mention this because our improved algorithm
will be obtained by modifying ${\rm{\bf TerminalBox}}$ and changing $\delta_1$ (but not $\tau_t$ or $\mu_t$).
In analyzing the quality of approximation in the second
algorithm, we can reuse the analysis of this section.
\subsection{Bounding the secondary error terms}
\label{subsec:secondary analysis}

In this section we prove \Clm{secondary}.
We examine each of the error terms separately and show that each one contributes at most $\frac{1}{5\log(n)}=\frac{\delta_1}{5}$ to the secondary error, and so the total secondary error is at most $\delta_1$.

\begin{claim}
\label{clm:et1+et2}
If  $({\cal B},t)$ is not tainted, $|\zeta_1| \leq \eta{\bf {\rm  w}}({\cal B})$ and $\sum_{\cal T} \zeta_2({\cal T}) \leq 2\eta {\bf {\rm  w}}({\cal B})$.
\end{claim}

\begin{proof}
The first inequality follows immediately from the definition of (non)tainted boxes: $|\zeta_1| = |{\tt alis}_t({\cal B})-|Good_t({\cal B})|| \leq \eta {\bf {\rm  w}}({\cal B})$.

For the second inequality,
recall that $\vec{{\cal C}}$ is the critical chain for ${\cal B}$ and $\vec{{\cal C}}({\cal T})$ is the portion of the critical chain in terminal box ${\cal T}$.
Let $\vec{{\cal C}}^*\subset \vec{{\cal C}}$ be the set of critical boxes ${\cal C} \in \vec{{\cal C}}$
such that $({\cal C},t-1)$ is tainted.
Since $({\cal B},t)$ is not tainted, $\sum_{{\cal C} \in \vec{{\cal C}}^*} {\bf {\rm  w}}({\cal C}) \leq \eta {\bf {\rm  w}}({\cal B})$.
We therefore have:

\begin{eqnarray*}
\sum_{\cal T} \zeta_2({\cal T}) & = & \sum_{{\cal C} \in \vec{{\cal C}}} {\tt alis}({\cal C})-|Good_{t-1}({\cal C})|\\
& \leq & \sum_{{\cal C} \in \vec{{\cal C}}} |{\tt alis}({\cal C})-|Good_{t-1}({\cal C})||\\
& \leq	& \sum_{{\cal C} \in \vec{{\cal C}}^*}{\bf {\rm  w}}({\cal C}) + \sum_{{\cal C} \in \vec{{\cal C}}-\vec{{\cal C}}^*} \eta{\bf {\rm  w}}({\cal C})\\
& \leq &  \eta{\bf {\rm  w}}({\cal B}) + \eta{\bf {\rm  w}}({\cal B}) \ =  2\eta {\bf {\rm  w}}({\cal B}).
\end{eqnarray*}
\end{proof}

Since $\eta=1/10\log(n)$, both
$|\zeta_1|$ and  $\sum_{{\cal T} \in \vec{{\cal T}}} \zeta_2({\cal T})$ are  bounded above by ${\bf {\rm  w}}({\cal B})/(5 \log n)$.

We move on to the error term $\zeta_3({\cal T})= |{\cal L}^{in}({\cal T})| - \sum_{{\cal E} \in \vec{{\cal E}}({\cal T})} |{\cal E} \cap {\cal L}|.$
\begin{claim}
\label{clm:et3}
\begin{eqnarray*}
\sum_{{\cal T} \in \vec{{\cal T}}} \zeta_3({\cal T})
& \leq & (\alpha + \eta) {\bf {\rm  w}}({\cal B}).
\end{eqnarray*}
\end{claim}
\begin{proof} Focus on a single terminal box ${\cal T}$.
By the grid approximation lemma (\Lem{grid-approx}), we can choose the chain $\vec{{\cal D}}({\cal T})$ so that it misses at most
$\alpha{\bf {\rm  w}}({\cal T})$ points of ${\cal L}^{in}({\cal T})$. (Note that $\vec{{\cal E}}$ is the subsequence consisting of non-tainted boxes.) Let the total width of the tainted boxes in $\vec{{\cal D}}({\cal T})$ be denoted as $b({\cal T})$.
Hence, $\zeta_3({\cal T}) \leq \alpha{\bf {\rm  w}}({\cal T}) + b({\cal T})$. Summing over all ${\cal T}$, $\sum_{{\cal T} \in \vec{{\cal T}}} \zeta_3({\cal T}) \leq \alpha{\bf {\rm  w}}({\cal B}) + \sum_{{\cal T} \in \vec{{\cal T}}} b({\cal T})$.
Since $({\cal B},t)$ is not tainted, the latter sum is at most $\eta{\bf {\rm  w}}({\cal B})$.
\end{proof}

Substituting  $\alpha = 1/(C_1\log n)^3$ and $\eta = 1/(10\log n)$,
gives $\sum_{{\cal T} \in \vec{{\cal T}}} \zeta_3({\cal T}) \leq {\bf {\rm  w}}({\cal B})/(5\log n)$.

Next we consider the error term $\zeta_4({\cal T}) = |{\cal L}_{out}({\cal T})| - \mu_t\cdot{\tt out}(\vec{{\cal E}}({\cal T}))$.

\begin{claim}
\label{clm:et4}
\begin{eqnarray*}
\sum_{{\cal T} \in \vec{{\cal T}}} \zeta_4 ({\cal T})& \leq & \Big(2\alpha+\frac{4\gamma \log n}{\rho}\Big) {\bf {\rm  w}}({\cal B}) \leq {\bf {\rm  w}}({\cal B})/(5\log n).
\end{eqnarray*}
\end{claim}

The main part of the claim is \Lem{et4}, which is formulated more generally to allow for its reuse later.
Recall that in \Sec{terminal}, we constructed a tree associated with calls to ${\rm{\bf TerminalBox}}_t(\cdot,{\cal B})$
whose leaves were the terminal boxes and whose intermediate nodes were boxes that occur along some execution of ${\rm{\bf TerminalBox}}_t(\cdot,{\cal B})$.
Each intermediate node was also associated to a unique splitter selected to split the associated box.
These splitters make up the interior increasing point sequence ${\cal P}^{\circ}(\vec{{\cal T}})$ associated with the terminal
chain $\vec{{\cal T}}$.  For each $P \in {\cal P}^{\circ}(\vec{{\cal T}})$ we defined
${\cal H}(P)$ to be the box in the splitter tree that was split by $P$, and noted that by Assumption 1,
$P$ is $(\mu_t,2\gamma {\bf {\rm  w}}({\cal H}(P)))$-safe for ${\cal H}(P)$.

In the improved algorithm to be presented in \Sec{improved}, the parameter $\gamma$ will not be fixed, and the splitter selected for different boxes may
be selected based on a different $\gamma$.  To anticipate this we introduce the notation $\gamma(P)$ to be the value of $\gamma$ that was used
when $P$ was selected as splitter for ${\cal H}(P)$ and so Assumption 1 gives that $P$ is a $(\mu_t,2\gamma(P) {\bf {\rm  w}}({\cal H}(P)))$-splitter for ${\cal H}(P)$.
Nothing in the previous analysis relied on $\gamma$ being fixed (indeed, this is the first time in the proof of \Thm{basic correctness}  that $\gamma$ has been
used.)

\begin{figure*}[tb]
  \centering
    \includegraphics[width=0.3\textwidth]{figures/errorterm4.pdf}
    \caption{The LIS ${\cal L}$ is depicted as a monotonically increasing freeform curve. The boxes in $\vec{{\cal E}}$ are colored dark gray,
    and the strips ${\cal S}^-({\cal T})$, ${\cal S}^+({\cal T})$ are in light gray.
}\label{fig:et4}
\end{figure*}

\begin{lemma}
\label{lem:et4}
\begin{eqnarray*}
\sum_{{\cal T} \in \vec{{\cal T}}} \zeta_4({\cal T}) & \leq & 2\alpha {\bf {\rm  w}}({\cal B}) + 4\sum_{P \in {\cal P}^{\circ}(\vec{{\cal T}})}\gamma(P){\bf {\rm  w}}({\cal H}(P)).
\end{eqnarray*}
\end{lemma}
\begin{proof}
Looking at the definition of $\zeta_4({\cal T})$,
our first goal is to obtain a lower bound on
${\tt out}(\vec{{\cal E}}({\cal T})) = \beta({\cal T})-\sum_{{\cal E} \in \vec{{\cal E}}({\cal T})}|{\cal E} \cap {\cal F}|$, the number of ${\cal F}$-points in the strip $\strip{{\cal T}}{{\cal B}}$ that lie outside of $\vec{{\cal E}}$.

Note that ${\cal L}^{out}({\cal T})$ can be split
into the set ${\cal L}^{-}({\cal T})$ of points that lie below ${\cal T}$ and ${\cal L}^{+}({\cal T})$ of points that lie above ${\cal T}$.
Refer to \Fig{et4}.
Let ${\cal S}^-({\cal T})$ be the smallest strip starting from the left edge of $\strip{{\cal T}}{{\cal B}}$ that contains all of ${\cal L}^{-}({\cal T})$ (so ${\cal S}^-({\cal T})$ is
either empty, or has its rightmost edge defined by the largest $x$ for which $F(x) \in {\cal L}$ and lies below ${\cal T}$).
Similarly, let ${\cal S}^+({\cal T})$ be the smallest strip that ends at the right edge of $\strip{{\cal T}}{{\cal B}}$ and contains all of ${\cal L}^+({\cal T})$.
Since ${\cal L}$ is increasing, ${\cal S}^-({\cal T})$ and ${\cal S}^+({\cal T})$ are disjoint.

The overlap of ${\cal S}^-({\cal T}) \cup {\cal S}^+({\cal T})$ with $\vec{{\cal E}}({\cal T})^{\cup}$ is small.
We claim that only the leftmost box ${\cal E}_L$ of
$\vec{{\cal E}}$ can overlap ${\cal S}^-({\cal T})$ (and a similar argument shows that only the rightmost box ${\cal E}_R$ can overlap ${\cal S}^+({\cal T})$).
The right edge of ${\cal S}^-({\cal T})$ occurs
at the rightmost point of ${\cal L}^-$. The right edge of ${\cal E}_L$ must be to the right of that because
${\cal E}_L$ contains at least one point in ${\cal L}^{in}$.
Hence,
\begin{eqnarray*}
{\tt out}(\vec{{\cal E}}({\cal T})) & \geq & |({\cal S}^-({\cal T})\cup {\cal S}^+({\cal T})) \cap {\cal F}| - |({\cal E}_L \cup {\cal E}_R) \cap {\cal F}|\\
& \geq & |({\cal S}^-({\cal T})\cup {\cal S}^+({\cal T})) \cap {\cal F}| - 2\alpha {\bf {\rm  w}}({\cal T}),
\end{eqnarray*}
where the second inequality
uses the fact that each of the grid strips of $\strip{{\cal T}}{{\cal B}}$ have width at most $\alpha {\bf {\rm  w}}({\cal T})$.
We now have:

\begin{eqnarray*}
\zeta_4({\cal T})
& = & |{\cal L}^{out}({\cal T})| - \mu_t\cdot{\tt out}(\vec{{\cal E}}({\cal T}))\\
 & \leq & |{\cal L}^-({\cal T})|+|{\cal L}^+({\cal T})| - \mu_t(|({\cal S}^-({\cal T})\cup {\cal S}^+({\cal T})) \cap {\cal F}| - 2\alpha {\bf {\rm  w}}({\cal T}))\\
& \leq &(|{\cal L}^-({\cal T})|-\mu_t|{\cal S}^-({\cal T}) \cap {\cal F}|)+(|{\cal L}^+({\cal T})| - \mu_t| {\cal S}^+({\cal T}) \cap {\cal F}|) + 2\mu_t\alpha {\bf {\rm  w}}({\cal T}).
\end{eqnarray*}

We now bound the first two terms in the final expression.
Let $P$ be the bottom left point of ${\cal T}$ and $Q$ be the top right point of ${\cal T}$.
All of the points in ${\cal L}^-({\cal T})$ are in violation with $P$. (Refer to \Fig{et4}.)	  Since
$P$  is a $(\mu_t,2\gamma(P) {\bf {\rm  w}}({\cal H}(P)))$-splitter for ${\cal H}(P)$, there are at most
$\mu|{\cal S}^-({\cal T}) \cap {\cal F}| + 2\gamma(P) {\bf {\rm  w}}({\cal H}(P))$ points of ${\cal F}$ that are in violation with $P$
and so $|{\cal L}^-({\cal T})| - \mu|{\cal S}^-({\cal T}) \cap {\cal F}| \leq 2\gamma(P) {\bf {\rm  w}}({\cal H}(P))$.
Similarly  $|{\cal L}^+({\cal T})| - \mu|{\cal S}^+({\cal T}) \cap {\cal F}| \leq 2\gamma(Q) {\bf {\rm  w}}({\cal H}(Q))$.
Thus:

\begin{eqnarray*}
\zeta_4({\cal T})
& \leq &2\gamma(P){\bf {\rm  w}}({\cal H}(P))+2\gamma(Q){\bf {\rm  w}}({\cal H}(Q)) + 2\mu_t\alpha {\bf {\rm  w}}({\cal T}).
\end{eqnarray*}

Finally, we sum the inequality in the lemma over all terminal boxes ${\cal T}$.
Observing that $\mu_t \leq 1$ and  that each point $P$ of the point sequence
${\cal P}^{\circ}(\vec{{\cal T}})$ gets included twice (once as a bottom left point and once as an upper right point), we
get:
\begin{eqnarray*}
\sum_{{\cal T} \in \vec{{\cal T}}^w} \zeta_4({\cal T}) & \leq & 2\alpha {\bf {\rm  w}}({\cal B}) + 4\sum_{P \in {\cal P}^{\circ}(\vec{{\cal T}})}\gamma(P) {\bf {\rm  w}}({\cal H}(P)).
\end{eqnarray*}
\end{proof}

\begin{proof}[of \Clm{et4}]
We use the previous lemma with $\gamma(P)=\gamma$ for all $P$.
For a given level of the splitter tree the sum of ${\bf {\rm  w}}({\cal H})$ is equal to ${\bf {\rm  w}}({\cal B})$ so the total sum is
bounded by ${\bf {\rm  w}}({\cal B})d$ where $d$ is the depth of the splitter tree.  Since each splitter is $\rho$-balanced, the width of a box
at depth $d$ in the splitter tree is at most $n(1-\rho)^d \leq ne^{-\rho d}$. This must be at least 1, so $d \leq (\log n)/\rho$.
Thus we have:
\begin{eqnarray}
\label{eterm 4 bound}
\sum_{{\cal T} \in \vec{{\cal T}}} \zeta_4({\cal T}) & \leq & \Big(2 \alpha + \frac{4\gamma (\log n)}{\rho}\Big){\bf {\rm  w}}({\cal B}).
\end{eqnarray}
Applying $\rho = C_1/\log n$ and $\alpha = \gamma = (1/C_1\log n)^3$, we get the final inequality.
\end{proof}
Finally, we consider $\zeta_5({\cal T})= \mu_t\cdot {\tt aloss}_{t-1}(\vec{{\cal E}}({\cal T})) - (1-\mu_t)\cdot {\tt out}(\vec{{\cal E}}({\cal T}))$. Let us review the basic terms. We have a terminal box ${\cal T}$ inside ${\cal B}$ andgrid $\Gamma({\cal T})$. $\vec{{\cal D}}({\cal T})$ is the grid-chain with the largest number of points in ${\cal L}$.
Tainted boxes and those containing no point of ${\cal L}$ are removed from $\vec{{\cal D}}({\cal T})$ to get
the chain $\vec{{\cal E}}({\cal T})$.

\begin{proposition} \label{prop:et5} $\zeta_5({\cal T}) \leq \mu_t\cdot{\tt aloss}_{t-1}(\vec{{\cal D}}({\cal T}))
- (1-\mu_t)\cdot {\tt out}(\vec{{\cal D}}({\cal T}))$.
\end{proposition}

\begin{proof} Since $\vec{{\cal E}}({\cal T})$ is a subsequence of $\vec{{\cal D}}({\cal T})$,
${\tt aloss}_{t-1}(\vec{{\cal E}}({\cal T})) \leq {\tt aloss}_{t-1}(\vec{{\cal D}}({\cal T}))$ and
${\tt out}(\vec{{\cal E}}({\cal T})) \geq {\tt out}(\vec{{\cal D}}({\cal T}))$.
\end{proof}

\begin{claim}
\label{clm:et5}
For every terminal box ${\cal T}$, if ${\cal T}$ is narrow then $\zeta_5({\cal T}) \leq 0$ and if $\zeta_5({\cal T})$ is wide then
$\zeta_5({\cal T})
 \leq  4\rho{\bf {\rm  w}}({\cal T}) \leq \frac{1}{5 \log(n)} {\bf {\rm  w}}({\cal T})$.

\end{claim}
\begin{proof} For convenience, we abbreviate $\vec{{\cal D}}({\cal T})$ by  $\vec{{\cal D}}$.
We apply \Lem{dichotomy} to the box $\strip{{\cal T}}{{\cal B}}$ with the strip decomposition given by the grid $\Gamma({\cal T})$.
We get $(1-\mu_t)\cdot {\tt out}(\vec{{\cal D}}) \geq \mu_t\cdot|U|$, where $U$ is the set of $\vec{{\cal D}}$-points that
are $\mu_t$-unsafe in $\Gamma({\cal T})$.
Hence, $\zeta_5({\cal T}) \leq \mu_t({\tt aloss}_{t-1}(\vec{{\cal D}}) - |U|)$.

Suppose ${\cal T}$ is narrow (that is, ${\bf {\rm  w}}({\cal T}) \leq 1/\rho$).
By the definition of ${\rm {\bf BuildGrid}}$, the grid $\Gamma({\cal T})$ has
$X(\Gamma({\cal T}))=X({\cal T})$, and so each box ${\cal D} \in \vec{{\cal D}}$ has width 1.
For any such box ${\tt alis}_{t-1}({\cal D})=|{\cal D} \cap {\cal F}|$, so ${\tt aloss}_{t-1}({\cal D}) = 0$.
Hence, $\zeta_5({\cal T}) \leq 0$.

Suppose ${\cal T}$ is wide (that is, ${\bf {\rm  w}}({\cal T}) > 1/\rho$).
We can crudely bound ${\tt aloss}_{t-1}(\vec{{\cal D}}) \leq |\vec{{\cal D}}^\cup \cap {\cal F}|$,
so $\zeta_5 \leq \mu_t |S|$, where $S$ is the set of ${\cal D}$-points
that are $\mu_t$-\emph{safe} in $\Gamma({\cal T})$.

Every box in $\vec{{\cal D}}$ has
width at most $\alpha {\bf {\rm  w}}({\cal T}) \leq \gamma {\bf {\rm  w}}({\cal T})$ (since $\vec{{\cal D}}$ is a $\Gamma({\cal T})$-chain).
So any $\mu_t$-safe point in $\Gamma({\cal T})$ is $(\mu_t,\gamma {\bf {\rm  w}}({\cal T}))$-safe.  ${\cal T}$ is a wide terminal box and
${\rm {\bf FindSplitter}}_t({\cal T},{\cal B},\mu_t,\gamma {\bf {\rm  w}}({\cal T}), \rho)$ failed to find a splitter. By Assumption 1 (reliability of ${\rm {\bf FindSplitter}})$
and \Cor{fails}, the total number of nondegenerate $(\mu_t,\gamma{\bf {\rm  w}}({\cal T}))$-safe indices for $\strip{{\cal T}}{{\cal B}}$
is at most $3\rho{\bf {\rm  w}}({\cal T})$.  Therefore, $|S| \leq 3\rho{\bf {\rm  w}}({\cal T}) + 1 \leq 4\rho{\bf {\rm  w}}({\cal T})$ (where the last
inequality follows from the fact that ${\cal T}$ is wide), completing the proof.
\end{proof}

We have thus shown that each of the five error terms is bounded by ${\bf {\rm  w}}({\cal B})/5\log(n)$ and so the
total secondary error is ${\bf {\rm  w}}({\cal B})/\log(n)=\delta_1 {\bf {\rm  w}}({\cal B})$.
This completes the proof of \Clm{secondary} the approximation error bound for the first algorithm.

\section{The improved algorithm}
\label{sec:improved}

The previous algorithm had running time $(\log n)^{O(1/\overline{\tau})}$ where $\tau$ is the primary approximation
parameter.
In this section we show how to modify the algorithm so that the running time is
$(1/\overline{\delta}\overline{\tau})^{O(1/\overline{\tau})} (\log n)^{c}$ for some absolute constant $c$, where $\overline{\delta}$ is the secondary error parameter, thereby proving \Thm{alg2}.
The improved running time is obtained by making some subtle (and somewhat mysterious) changes to the
basic algorithm.  Formally the changes are  minor, and we will start by completely describing the revisions made to the
basic algorithm without
motivating the reasons for the changes.  Then we provide an informal discussion of how we arrived at these
changes.  (The reader may wish to read this discussion before reading the formal description.)
Finally we prove the properties of the improved algorithm.
\iffalse
As mentioned earlier, it is enough to give an algorithm with error probability at most 1/4 since
we can reduce the error to $\xi$ by running $\Theta(1/\xi)$ independent executions and
taking the median.
\fi

\subsection{Formal description of the algorithm}
\label{sec:improve-alg}

The basic algorithm consists of 6 main procedures,${\rm {\bf BasicMain}}$, ${\rm {\bf ApproxLIS}}$, ${\rm {\bf Classify}}$, ${\rm {\bf CriticalBox}}$, ${\rm{\bf TerminalBox}}$ and ${\rm {\bf GridChain}}$,
and uses two additional procedures ${\rm {\bf FindSplitter}}$ and ${\rm {\bf BuildGrid}}$.
The new algorithm has the same structure, with the only changes being that  the internal structure of
${\rm{\bf TerminalBox}}$ is modified, and some  auxiliary parameters are changed, and some new parameters are added.
The change in parameter definitions is done by replacing ${\rm {\bf BasicMain}}$ by ${\rm {\bf ImprovedMain}}$.

In the procedure below $C_2$ is a sufficiently large constant.
The key new parameter is $\Psi$, called the {\em error controller}.  Most of the other parameters are defined in terms of $\Psi$.  Increasing this parameter reduces the error, but also increases the
running time.  The running time of the algorithm will turn out to be $(1/\Psi)^{O(\tau)}(\log n)^c$.
This parameter did not appear explicitly in
the basic algorithm, but implicitly it was set to
$\Omega(\log n)$.  In this algorithm we take it to be $\Omega(1/(\overline{\tau}\overline{\delta}))$, which is what allows us
to make the exponent of $\log n)$ a constant independent of $\overline{\tau}$ and $\overline{\delta}$.

\vspace{-10pt}
\begin{center}
	\fbox{\begin{minipage}{\columnwidth}
${\rm {\bf ImprovedMain}}(n,f,\overline{\tau},\overline{\delta})$\\
Output: Approximation to ${\tt lis}_f$.
\begin{enumerate}
\item Fix global parameters (unchanged throughout algorithm).
\begin{center}
  \begin{tabular}{ | l || c | c |}
    \hline
    {\bf Name} & {\bf Symbol} & {\bf Value} \\ \hline
		Maximum level & $t_{\max}$ & $\lceil 4/\overline{\tau} \rceil$ \\ \hline
    Error controller & $\Psi$ & $\max(C_2, t_{\max}/\overline{\delta})$ \\ \hline
    Sample size parameter & $\sigma$ & $100\Psi^3$ \\ \hline
    Grid precision parameter & $\alpha$ & $\frac{1}{(C_2\Psi)^4}$ \\ \hline
    Width threshold & $\omega$ & $1/\alpha$ \\ \hline
    Tainting parameter & $\eta$ & $1/10\Psi$ \\ \hline
    Primary splitter parameter & $\mu_r$ & $\frac{2}{r+3}$ \\ \hline
    Secondary splitter parameter & $\gamma_j$ & $16^j\alpha/(\log n)^4$ \\ \hline
    Splitter balance parameter & $\rho_j$ & $(\gamma_j)^{1/4}=2^j\alpha^{1/4}/\log n$ \\ \hline

  \end{tabular}
\end{center}

\item Let box  ${\cal U}$ be the  box $[1,n] \times [1,{\tt valbound}]$.
\item  Return ${\rm {\bf ApproxLIS}}_{t_{\max}}({\cal U})$.
\end{enumerate}
\end{minipage}}
\end{center}

Comparing ${\rm {\bf BasicMain}}$ and ${\rm {\bf ImprovedMain}}$ one sees that $t_{\max}$ and the function $\mu_r$
are unchanged.    The parameters $\sigma$, $\alpha$, $\omega$ and $\eta$ are
now polynomials (or inverse polynomials) in $\Psi$ rather than $\log(n)$.
The parameters $\gamma$ and $\rho$ are now replaced by functions
$\gamma_j$ and $\rho_j$.  This reflects the following key change in the algorithm:
In the basic algorithm, the procedure ${\rm{\bf TerminalBox}}$ terminates the first time that ${\rm {\bf FindSplitter}}$ fails to
find a splitter, or when the width of the box dropped below the threshold $\omega$.
In the improved algorithm, this is not the case.   We view the improved
${\rm{\bf TerminalBox}}$ as proceeding in phases where a phase
ends whenever ${\rm {\bf FindSplitter}}$ fails.  The index $j$
keeps track of the {\em phase number} and is incremented each time ${\rm {\bf FindSplitter}}$ fails to find a splitter
and the values of $\gamma$ and $\rho$ are increased to $\gamma_j$ and $\rho_j$
and ${\rm {\bf FindSplitter}}$ is repeated. Increasing $\gamma$ means that a splitter
is allowed to have more violations while increasing $\rho$ means that the we require any selected splitter to be
closer to the center of the interval. Thus as the phases proceed,  one of the splitter
conditions is relaxed and the other is made more stringent.
In the basic algorithm, there was a fixed parameter $\omega$  used in ${\rm{\bf TerminalBox}}$ to provide
a threshhold to determine whether the current box was ``narrow'' or not and to provide one of the criteria
for the procedure to halt.  In the improved ${\rm{\bf TerminalBox}}$ there is a variable parameter $\theta$ and the only stopping
criterion for ${\rm{\bf TerminalBox}}$ is that the current box has width below $\theta$. The
parameter $\omega$ is used for the initial value for $\theta$.
The value of $\theta$ may increase
at the beginning of each new phase.  If ${\rm {\bf FindSplitter}}$ fails on box ${\cal T}$ in phase $j$, then $\theta$ is reset to
the maximum of its present value and $ \gamma_j {\bf {\rm  w}}({\cal T})/\alpha$.

The following auxiliary parameters are not used explicitly by the algorithm, but appear in the analysis:

\begin{center}
  \begin{tabular}{ | l || c | c |}
    \hline
    {\bf Name} & {\bf Symbol} & {\bf Value} \\ \hline
    Base additive error & $\delta_1$ & $1/\Psi$ \\ \hline
    $t$-level additive error & $\delta_t$ & $t\delta_1$ \\ \hline
    Taint probability & $\phi$ & $\frac{1}{C_2}\alpha^5$    \\ \hline
  \end{tabular}
\end{center}
\iffalse
We present the various parameters of the improved algorithm in the table below.
As before, the desired
approximation parameters $\overline{\tau}$ and $\overline{\delta}$ are viewed as inputs to the algorithm.
These parameters determine
two other parameters $t_{\max}$ and $\Psi$. The parameter $t_{\max}$ is a natural number that specifies the value of the level parameter $t$ in the highest level call to the algorithm.
 The parameter $\Psi$ is called the {\em error controller} and   determines the initial setting of several parameters used in the
algorithm.

The parameters $\tau_t = 4/t$ and $\mu_t = 2/(t+3)$ are as in the first algorithm.

The following table provides a summary of the parameters related to $t_{\max}$ and $\Psi$.

\iffalse
We assume that these $taupar$ are each at least $1/\log(n)$ which implies that $t_{\max}$ and $\Psi$
are both $\log(n)^{O(1)}$.  \marginpar{technical issue: is assumption valid}
\fi

\begin{center}
  \begin{tabular}{ | l || c | c |}
    \hline
    {\bf Name} & {\bf Symbol} & {\bf Value} \\ \hline
Constant &  $C_2$ & Sufficiently large \\ \hline
                    Target multiplicative error& $\overline{\tau}$ & Input \\ \hline
		Target additive error & $\overline{\delta}$ &  Input \\ \hline
		Maximum level & $t_{\max}$ & $\lceil 4/\overline{\tau} \rceil$ \\ \hline
    Error controller & $\Psi$ & $\max(C_2, t_{\max}/\overline{\delta})$ \\ \hline
    Sample size parameter & $\sigma$ & $100\Psi^3$ \\ \hline
    Base additive error & $\delta_1$ & $1/\Psi$ \\ \hline
    $t$-level additive error & $\delta_t$ & $t\delta_1$ \\ \hline
    Grid precision parameter & $\alpha$ & $\frac{1}{(C_2\Psi)^4}$ \\ \hline
    Width threshold & $\omega$ & $1/\alpha$ \\ \hline
    Tainting parameter & $\eta$ & $1/10\Psi$ \\ \hline
    Taint probability & $\phi$ & $\frac{1}{C_2}\alpha^5$    \\ \hline

  \end{tabular}
\end{center}

An important change from the previous algorithm is that ${\rm{\bf TerminalBox}}$ goes through various \emph{phases}.
The nonnegative integer $j$ is called the {\em phase parameter}. This is a local variable to ${\rm{\bf TerminalBox}}$
which counts the number of times that a call to ${\rm {\bf FindSplitter}}$ has failed.  When ${\rm{\bf TerminalBox}}$ is called it
is initialized to 0.  We say that phase $j$ begins
after the $j$th failure of ${\rm {\bf FindSplitter}}$. The secondary splitter parameter $\gamma$ and balance parameter $\rho$ now
change with the phase.
\begin{center}
  \begin{tabular}{ | l || c | c |}
    \hline
    {\bf Name} & {\bf Symbol} & {\bf Value} \\ \hline
		Secondary splitter parameter & $\gamma_j$ & $16^j\alpha/(\log(n))^4$ \\ \hline
    Splitter balance parameter & $\rho_j$ & $2^j \alpha^{1/4}/\log(n) = \gamma_j^{1/4}$ \\ \hline
  \end{tabular}
\end{center}
\fi

Below is the improved version of ${\rm{\bf TerminalBox}}$.

\vspace{-10pt}
\begin{center}
	\fbox{\begin{minipage}{\columnwidth}
${\rm{\bf TerminalBox}}_t(x,{\cal B})$
\algcomment{$x \in X({\cal B})$}\\
Output: subbox ${\cal T}$.\\
\begin{enumerate}
\item Initialize: ${\cal T} \longleftarrow {\cal B}$; $j \longleftarrow 0$;
$\theta \longleftarrow \omega$; $\gamma \longleftarrow \gamma_0$; $\rho \longleftarrow \rho_0$.
\item Repeat until ${\bf {\rm  w}}({\cal T}) \leq \theta$:
\begin{enumerate}
\item Run ${\rm {\bf FindSplitter}}({\cal T},{\cal B},\mu_t,\gamma {\bf {\rm  w}}({\cal T}),\rho)$ which
returns the boolean variable $splitter\_found$ and the index
$splitter$.
\item If $splitter\_found={\tt TRUE}$ then
\begin{enumerate}
\item If $x \leq splitter$ then replace ${\cal T}$ by the
box $Box(P_{BL}({\cal T}),F(splitter))$.
\item If $x > splitter$ then replace ${\cal T}$ by the
box $Box(F(splitter), P_{TR}({\cal T}))$.
\end{enumerate}
\item else (so $splitter\_found = {\tt FALSE}$ and new phase starts)
\begin{enumerate}
\item $\theta \longleftarrow \max(\theta, \gamma {\bf {\rm  w}}({\cal T})/\alpha)$.
\item $j \longleftarrow j+1$; $\gamma \longleftarrow \gamma_j$; $\rho \longleftarrow \rho_j$.
\end{enumerate}
\end{enumerate}
\item Return ${\cal T}$.
\end{enumerate}
\end{minipage}}
\end{center}

We will prove the following property of ${\rm {\bf ApproxLIS}}$ with the improved version of ${\rm{\bf TerminalBox}}$:

\begin{theorem}
\label{thm:improved approxlis}
Suppose ${\rm {\bf ApproxLIS}}$ is run with the global parameters set as in ${\rm {\bf ImprovedMain}}$ using
the improved version of ${\rm{\bf TerminalBox}}$.
On input a box ${\cal B} \subseteq {\cal U}$ and an integer $t$, ${\rm {\bf ApproxLIS}}_t({\cal B})$:
\begin{itemize}
\item  runs in time $(1/\Psi)^{O(t)}(\log n)^c$, and
\item outputs a value that, with probability at least $3/4$, is a
{\em $(\tau_t,\delta_t )$}-approximation to ${\tt lis}({\cal B})$, where:
\begin{eqnarray*}
\tau_t&=& \frac{4}{t} \\
\delta_t& = & \frac{t}{\Psi}.
\end{eqnarray*}
\end{itemize}
\end{theorem}

\Thm{alg2} follows immediately from \Thm{improved approxlis}:

\begin{proof}[of \Thm{alg2}]
${\rm {\bf ImprovedMain}}(n,f,\overline{\tau},\overline{\delta})$
returns the output of ${\rm {\bf ApproxLIS}}_{t_{\max}}({\cal U})$.  By \Thm{improved approxlis}, this gives a
$(4/t_{\max},t_{\max}/\Psi)$-approximation to ${\tt lis}_f$ which runs in time $(1/\Psi)^{O(t_{\max})}\log(n)^c$.  Using the fact that $t_{\max} = \lceil 4/\overline{\tau} \rceil$ and $\Psi=t_{\max}/\overline{\delta}$,
gives the desired running time and approximation error for ${\rm {\bf ImprovedMain}}$.
\end{proof}

In the next subsection we provide some intuition for the improved algorithm.  The remainder of the section
is devoted to the proof of \Thm{improved approxlis}.  The proof is structured to parallel
that of \Thm{basic approxlis}.   We start with the running time analysis.  We revisit the $t$-critical tree,
highlighting the differences that arise in the improved algorithm.  Also, we revisit the randomness assumptions, modifying them as needed for the new analysis.  The primary and secondary error terms are defined
as in the basic algorithm, and the primary error analysis is unchanged.  The secondary error analysis reuses
much of the secondary error analysis from the basic algorithm,  but there are some significant
differences.

\subsection{Intuition for the improved algorithm}

Before analyzing the improved algorithm, we discuss two lines of thought that led to the improvement.
Our first line of thought gave the desired speed-up, but the algorithm was technically cumbersome.
In trying to simplify the algorithm we found an alternative way to think about the improvement,
leading to the simplified version presented here.

Consider the main contributions  to the running time of the first algorithm.
The algorithm is recursive with recursion depth $t_{\max}=\Theta(1/\overline{\tau})$.
Let $Time_t$ denote the running time of ${\rm {\bf ApproxLIS}}_t$ on instances of size at most $n$.
Roughly,
$Time_t=R \times Time_{t-1}+S$ where $R$ is the number of recursive calls to ${\rm {\bf ApproxLIS}}_{t-1}$,
and $S$ which is the cost of all other computation performed by ${\rm {\bf ApproxLIS}}_t$, and this gives an overall running time of
$O(R^t S)$.  In the basic algorithm, $R$ and $S$ are both $(\log n)^{\Theta(1)}$, giving a time bound
of $(\log(n))^{O(1/\overline{\tau})}$.  To improve the algorithm
we seek to reduce $R$.

What determines $R$?  In the main ${\rm {\bf ApproxLIS}}$ procedure we start by selecting a sample index set of size $\sigma=\log n^{\theta(1)}$.
For each sample index $x$ we eventually have to run ${\rm {\bf GridChain}}_t({\cal T})$ where ${\cal T}$ is the terminal box
selected for $x$.  Within ${\rm {\bf GridChain}}_t({\cal T})$ recursive calls are made to ${\rm {\bf ApproxLIS}}_{t-1}$.  The number of
such calls is $1/\alpha^{\Theta(1)}$.  Thus the total number of recursive calls
to ${\rm {\bf ApproxLIS}}_{t-1}$ is $\sigma (1/\alpha)^{\Theta(1)}$.  Since $\sigma$ and $1/\alpha$ are both
$(\log n)^{\Theta(1)}$, we would have to reduce each of them in order to make $R$ independent of $n$.

Note that the costs of ${\rm{\bf TerminalBox}}_t$ (which includes calls to ${\rm {\bf FindSplitter}}$), and the cost
of ${\rm {\bf BuildGrid}}$, which are both $((\log n))^{\Theta(1)}$, are part of the ``nonrecursive'' cost that contribute to
$S$ but not $R$. We can ignore them in this discussion.

Reducing $\sigma$ is fairly straightforward.
The choice of  $\sigma$ was originally made to guarantee that all pairs $({\cal B},t)$ are untainted.
In other words, ${\rm {\bf ApproxLIS}}_t$ accurately estimates the number of $Good_t$ points
because $\sigma$ is large enough. In the proof of \Prop{assumption 2}, we take a union bound over all possible pairs $({\cal B},t)$ (basically
all possible ${\rm {\bf ApproxLIS}}$ calls).  Since the number
of potential calls is $n^{\Theta(1)}$, we needed $\sigma$ to be $(\log n)^{\Omega(1)}$.
The first idea for reducing $\sigma$ is to relax the union bound so that it only pertains to the $(\log n)^{O(1)}$
calls that are actually made by the algorithm. This would allow us
to reduce $\sigma$ to $(\log\log n)^{O(1)}$. This
still has a dependence on $n$ (albeit a much better one).

In both the original analysis, and the improved analysis sketched above, an execution is considered unsuccessful
unless {\em every} recursive call to ${\rm {\bf ApproxLIS}}_u$ that is actually performed gives a ``sufficiently good''
estimate for $|Good_u|$.  This is quite a stringent requirement, and in the improved algorithm
we relax this criterion for success and allow a small
fraction of calls to ${\rm {\bf ApproxLIS}}_u({\cal C})$ to give a poor estimate to $|Good_u({\cal C})|$.
More precisely when we make a recursive call to ${\rm {\bf ApproxLIS}}({\cal T})$ we will allow the probability
that ${\rm {\bf ApproxLIS}}_t$ errs significantly on its
estimate of the number of $Good_t$ points to be $\phi$ (as defined above)
which is much larger than $n^{-\Omega(1)}$.
The challenge in doing is this is that errors might accumulate over different recursive levels
so that the estimate produced at the top level is inaccurate with high probability.  It turns out
this does not happen, and
the  recursive notion of tainted was defined as an analytical tool to prove this.
This allows $\sigma$ to be some polynomial in $1/\tau$.

The more challenging problem is to deal with $\alpha$, which is the grid precision parameter.
The grid constructed inside a terminal box has size ($\textrm{poly}(1/\alpha)$).  In order to perform the longest path
computation on the digraph $D(\Gamma|{\cal T})$ we
make a recursive call to ${\rm {\bf ApproxLIS}}$  in each grid box.
This leads to a contribution of $(1/\alpha)^{O(t)}$
in the run time (since $t$ is the depth of the recursion), and since $\alpha$ is $\Theta(1/\log(n))$
this is significant.   If $\alpha$ could be taken to be a constant, this would give us the kind of run time
we are aiming for.

Unfortunately, the analysis of the first algorithm does not allow for such an improvement.
The analysis of $\zeta_5({\cal T})$ forces the grid to be fine, specified as $\alpha \leq \gamma$ (refer to the proof of \Clm{et5}).
The parameter $\gamma$ decides the additive loss of a splitter, and the grid precision must be finer than this.
This is crucial for the application of \Lem{dichotomy}.

\iffalse
  by the number of $(\mu,\alpha {\bf {\rm  w}}({\cal T}))$-safe
points, so we need that number to be small.   For each terminal box ${\cal T}$, using the fact that we failed to find
a splitter in ${\cal T}$, we deduce that with high probability there are at most $3\rho {\bf {\rm  w}}({\cal T})$ points that are
 $(\mu, \gamma{\bf {\rm  w}}({\cal T}))$-safe.
When we  apply Lemma \ref{lem:dichotomy} we need $\alpha \leq \gamma$.
\fi

Our  analysis of the basic algorithm also requires that $\gamma$ be small.
When we analyze the
error term $\sum_{{\cal T}} \zeta_4({\cal T})$, we obtain an upper bound of  $\gamma (\log n) {\bf {\rm  w}}({\cal B})/\rho$ (refer to \Clm{et4}).
This error term accounts for the points that are eliminated (perhaps incorrectly)
because they were in violation with some selected splitter.
To ensure that this term is small we need  $\gamma=\log(n)^{-\Theta(1)}$.  Since $\alpha \leq \gamma$,
we get the same upper bound on $\alpha$.

\iffalse
to increasing sequences within the chain of terminal boxes includes an additive term of $\gamma(\log n){\bf {\rm  w}}({\cal B})/\rho$.
(Refer to \Clm{et4}, the analysis of $\sum_{{\cal T}} \zeta_4({\cal T})$.) This is because the splitters at each level of $t$-splitter
tree collectively ``lose" $\gamma {\bf {\rm  w}}({\cal B})$ points. This comes about since the splitter at box ${\cal A}$ is $(\mu, \gamma{\bf {\rm  w}}({\cal A}))$-safe.
(Refer to the parameters in the call to ${\rm {\bf FindSplitter}}$ in ${\rm{\bf TerminalBox}}$.) The depth of the $t$-splitter tree os $O((\log n)/\rho$,
leading to a total loss of $\gamma(\log n){\bf {\rm  w}}({\cal B})/\rho$. Since the balance parameter $\rho$ is at most $1$, $\gamma$ must be $O(1/\log n)$
to get a reasonable error bound.
\fi

The key insight to overcoming this barrier is that the longest path computation that we perform on the grid is very similar to an exact LIS computation.
It
can be formulated
as a weighted generalization of LIS on an index set of size $1/\alpha$.  So rather than do an exact longest path
computation we could instead approximate the longest path computation by applying the ideas of our LIS
algorithm recursively.   This can be indeed be done.  However,
in this form the algorithm becomes rather complicated and confusing since we have recursion arising in two ways: the basic
algorithm was already recursive, and now another recursion is piled on top.

Fortunately, by  unwinding this new layer of recursion, one can construct
an algorithm that avoids it altogether.  Indeed this new layer of recursion is implicitly
implemented simply by introducing the phases in ${\rm{\bf TerminalBox}}$ and adjusting some of the parameters dynamically.  To see how this arises, let us consider a recursive algorithm of
the type proposed above.  When we arrive at a terminal box (because we fail to find a splitter), rather
than do an exact longest path computation inside
of ${\rm {\bf GridChain}}$ we recursively call an approximation algorithm.  In this recursive call, the index set size will be $1/\alpha$
which is $(\log n)^{O(1)}$, and when we look for splitters, the $\gamma$ parameter will be $1/(\log(1/\alpha))^{O(1)}$
which will be $(\log\log n )^{O(1)}$, which is significantly smaller than that of the basic algorithm.
This suggests
that (rather than impose this additional recursive structure) when the algorithm fails to find a good splitter
for a particular
value of $\gamma$ we increase $\gamma$ and try again.
In order to control all the error terms,
we have to increase $\rho$ and the width threshold $\theta$ (the minimum width that allows us
to stop and declare a terminal box).
We think of ${\rm{\bf TerminalBox}}$ as acting in phases indexed by $j=0,1,\ldots$.
Phase $j$ ends either because the width of the current box drops below $\theta$ (in which
case ${\rm{\bf TerminalBox}}$ terminates) or because ${\rm {\bf FindSplitter}}$ fails, in which case phase $j$ ends and phase $j+1$ begins
with $\gamma,\rho$ and $\theta$ all adjusted upwards.

The parameters $\gamma$ and $\rho$ are initially $1/(\log n)^{\Theta(1)}$ as in the original algorithm.
With the recursive view described above,  there is a rapid decrease in the parameters because
the size of the longest path subproblem being solved is polylogarithmic in the size of the initial problem.
This suggests that after $j$ phases the parameters should be the reciprocal of the $j$th iterated logarithm.
This works, but our analysis allows considerable flexibility in choosing the parameters. To simplify
the technical details,
we make a particularly simple choice:
we  double $\rho$ after each phase and multiply $\gamma$ by 16, always maintaining $\gamma=\rho^4$.

The stopping condition for ${\rm{\bf TerminalBox}}$ is now changed.  Before we stopped the first time
${\rm {\bf FindSplitter}}$ failed.  Now we continue until the width of the terminal box drops below the threshhold.

The above approach allows us to set $\alpha = (1/t)^{O(1)}$.
Note that the term $O(\alpha {\bf {\rm  w}}({\cal T}))$ still appears in $\zeta_3({\cal T})$ and $\zeta_4({\cal T})$,
leading to a secondary error of $t^{-\Omega(1)}$.

\subsection{Running time analysis of the improved algorithm}
We now turn to the  proof of \Thm{improved approxlis}. We begin with the run time
analysis, and mimic the anaylsis for the basic algorithm with some minor changes.

Let $A_t=A_t(n)$ be the running time of ${\rm {\bf ApproxLIS}}_t$  and
$C_t=C_t(n)$ be the running time of ${\rm {\bf Classify}}_t$ on boxes of width at most $n$.

As before  we use $P_i=P_i(n)$ to denote functions of the form $a_i ((\log n))^{b_i}$, where $a_i,b_i$ are constants that
are independent of $n$ and $t$.  We also use $Q_i=Q_i(\Psi)$ to denote functions of $\Psi$ of the form $c_i(\Psi)^{d_i}$ where $c_i,d_i$ are constants.

\begin{claim} \label{clm:imp-time}
For all $t \geq 1$,
\begin{eqnarray*}
A_t & \leq & Q_1 C_t + Q_2. \\
C_t & \leq & C_{t-1}+ Q_4 A_{t-1}+P_1Q_3.
\end{eqnarray*}
\end{claim}

\begin{proof}
The first recurrence with $Q_1=\sigma$ is immediate from the definition of
${\rm {\bf ApproxLIS}}_t$.   The function $Q_2$ is an upper bound on the cost of operations excluding calls to ${\rm {\bf Classify}}$.

For the second recurrence, the final recursive call to ${\rm {\bf Classify}}_{t-1}$  gives the $C_{t-1}$ term.
The rest of the cost comes from  ${\rm {\bf CriticalBox}}_t$ which invokes ${\rm{\bf TerminalBox}}_t$, which involves several iterations
where the cost of each iterations is dominated by the cost of ${\rm {\bf FindSplitter}}$.  Each iteration reduces the size of the
box ${\cal T}$ by at least a $(1-\rho_0)$ factor so the number of iterations is at most $\log n/\rho_0$.  The cost of ${\rm {\bf FindSplitter}}$ is $(\log n/\Psi)^{O(1)}$
so the cost of ${\rm{\bf TerminalBox}}_t$ is included in the term $P_1Q_3$.
${\rm {\bf CriticalBox}}_t$ then calls ${\rm {\bf GridChain}}_t$.  This involves building a grid of
size $(1/\Psi)^{O(1)}$ and making one call to ${\rm {\bf ApproxLIS}}_t$ for each grid box, which accounts for the term $Q_4 A_{t-1}$.
${\rm {\bf GridChain}}_t$ finds a longest path in  the grid digraph, which can be absorbed into the $P_1Q_3$ term.
\end{proof}

\begin{corollary} \label{cor:imp-time}
For given input parameters $\overline{\tau}, \overline{\delta}$, both $A_{t_{\max}}$ and $C_{t_{\max}}$ are in $(1/(\overline{\tau}\overline{\delta}))^{O(1/\overline{\tau})}(\log n)^{O(1)}$.
\end{corollary}

\begin{proof} Using the recurrence for $A_{t-1}$ to eliminate $A_{t-1}$ from
the recurrence for $C_t$, which gives a linear recurrence for $C_t$ in terms of $C_{t-1}$
whose solution has the form $C_t \leq P_5Q_5(Q_1Q_4+1)^t$.  This leads also to  $A_t \leq P_6Q_6(Q_1Q_4+1)^t$,  which are both $(\log n)^{O(1)}(\Psi)^{O(t)}$.
Since $t_{\max} = O(1/\overline{\tau})$ and $\Psi = O(1/(\overline{\tau}\overline{\delta}))$, the bound follows.
\end{proof}

\subsection{Revisiting the t-splitter tree and the terminal chain}
\label{sec:revised}

In preparation for the improved error analysis, we revisit the terminal tree, and replace Assumption 2 by a relaxed version.
Recall the $t$-splitter tree described in \Sec{terminal}.  We will construct a similar tree that also
reflects the phase structure of the improved algorithm.

A box-phase pair is a pair $({\cal T},j)$.  The execution of ${\rm{\bf TerminalBox}}_t(x,{\cal B})$ generates a sequence $({\cal T}_0,j_0)=({\cal B},0),({\cal T}_1,j_1),\ldots$
of box-phase pairs corresponding to each call of ${\rm {\bf FindSplitter}}$.
This is called the {\em $t$-trace} of $x$.  We define the {\em $t$-execution tree} for ${\cal B}$
whose paths from the root correspond to the $t$-traces of all indices.

Classify each box-phase pair $({\cal T},j)$ as {\em split} or {\em splitterless} depending on whether \linebreak
${\rm {\bf FindSplitter}}_t({\cal T},{\cal B},\mu_t,\gamma_j {\bf {\rm  w}}({\cal B}),\rho_j)$
succeeds or fails  to find a splitter.  For a split pair $({\cal T},j)$, let $s_j({\cal T})$ be the splitter found,
and define the left-child and right-child of $({\cal T},j)$ to  be  $(Box(x_{BL}({\cal T}),F(s)),j)$ and $(Box(F(s),x_{TR}({\cal T})),j)$.
If $({\cal T},j)$ is splitterless, define its child to be $({\cal T},j+1)$.   This defines a DAG on the box-phase pairs.

The subgraph of nodes reachable from $({\cal B},0)$ is a rooted tree in which every node has 1 or 2 children (depending on whether
it is splitterless or split).  It is convenient to add an additional (splitterless) root $({\cal B},-1)$ with unique child $({\cal B},0)$.
We assign a number $\omega({\cal T},j)$ to each splitterless pair $({\cal T},j)$. We set $\omega({\cal T},j)=\frac{\gamma_j}{\alpha}{\bf {\rm  w}}({\cal T})$ for $j \geq 0$,
and $\omega({\cal B},-1)=\omega$.
Define $\theta({\cal T},j)$ for every pair $({\cal T},j)$ to be the maximum of $\omega({\cal R},i)$
over all splitterless ancestors $({\cal R},i)$ of $({\cal T},j)$.  Observe that along any path from the root
$\theta({\cal T},j)$ is nondecreasing
while $|{\cal T}|$ is nonincreasing.  Truncate every path at the first node where
$|{\cal T}| \leq \theta({\cal T},j)$.   This is the $t$-execution tree for ${\cal B}$.

For each $x \in X({\cal B})$, define
$\Pi_E(x,{\cal B})$ to be the set of nodes in the $t$-execution tree whose box includes $x$ in its index set.
The following lemma is immediate from the (improved) definition of  ${\rm{\bf TerminalBox}}$.

\begin{lemma}
\label{lem:execution}
For every $x \in F^{-1}({\cal B})$, $\Pi_E(x,{\cal B})$
is a root-to-leaf path in the tree and is equal to the $t$-trace
of $x$.  In particular, the box corresponding to the leaf that is reached is the terminal box that is returned
by ${\rm{\bf TerminalBox}}_t(x,{\cal B})$, and is equal to
$\vec{{\cal T}}[x]$ (the unique box ${\cal T} \in \vec{{\cal T}}$ such that $x \in X({\cal T})$).
\end{lemma}

For a box ${\cal H}$ that appears in the $t$-execution tree, the set of nodes labeled by ${\cal H}$ is a path and the sequence of
phase numbers increase by 1.  All of the nodes in the path except the last have exactly one child (which is its successor
in the path.)  The last occurence of ${\cal H}$ is either a leaf or a split node.  We define ${\tt ph}({\cal H})$ to be the highest phase
that ${\cal H}$ reaches.   Box ${\cal H}$ is a {\em multiphase box} if the associated path has two or more nodes
and is a {\em uniphase box} otherwise.  Note that if ${\cal H}$ is a multiphase box then $({\cal H},{\tt ph}({\cal H})-1)$ is
unsplittable and lies on the execution path that reaches $({\cal H},{\tt ph}({\cal H}))$. We state a simple proposition.

\begin{proposition} \label{prop:phase-box} For some positive $j$, let $({\cal H},j)$ and $({\cal H}',j)$ be unsplittable nodes in the $t$-execution tree.
Then $X({\cal H})$ and $X({\cal H}')$ are disjoint.
\end{proposition}

\begin{proof} Since the edges in the $t$-execution tree denote containment, if $X({\cal H}) \cap X({\cal H}') \neq \emptyset$, then
(wlog) ${\cal H}$ is contained in ${\cal H}'$. There is a root-to-leaf path passing through $({\cal H}',j)$ and then $({\cal H},j)$.
Because $({\cal H}',j)$ is unsplittable, the subsequent node in this path must be $({\cal H}',j+1)$. But phases
cannot decrease as we go down this path, so $({\cal H},j)$ cannot appear.
\end{proof}

We can construct a new tree by contracting all of the occurences of each box into a single node.  This gives a binary
tree of boxes and this is the $t$-splitter tree.  Each node in this tree is a box ${\cal H}$.
The reader can readily verify that the $t$-splitter tree satisfies the  bulleted properties of $R({\cal B})$ in
\Sec{terminal} and \Lem{terminal}.  As we already noted in formulating \Lem{et4},
the parameter $\gamma$  now depends on $P$.

Define $\Pi(x,{\cal B})$ to be the path in the $t$-terminal tree corresponding to $x$.  The non-terminal nodes of $\Pi(x,{\cal B})$
are precisely the split nodes in $\Pi_E(x,{\cal B})$ (the $t$-trace of $x$ defined earlier).
The phase numbers of nodes along the path are non-decreasing.
It is not hard to see that $\gamma_j$ (where $j$ indexes the phase) can never become too large. This is because that threshold $\theta$
increases as $j$ increases, and eventually this will exceed the width of the box ${\cal T}$.

For $j \geq 0$, let $d_j(x)$ be the number of non-terminal nodes in $\Pi(x,{\cal B})$ at phase $j$.
Each of these nodes represents a successful splitter.
This number cannot be too large, since the width of the box decreases with each split.
We make these arguments formal.

\begin{prop}
\label{prop:phase} Let $j$ be a nonnegative integer and $x \in X({\cal B})$ be such that $d_j(x) \neq 0$.
\begin{enumerate}
\item $\gamma_{j} \leq 16\alpha$ and $\rho_j \leq 2\alpha^{1/4}$.
\item $d_j(x) \leq (1/\rho_j)^2$.
\end{enumerate}
\end{prop}

\begin{proof} Fix $j$ such that $d_j(x) \neq 0$.
For simplicity of notation write $d$ for $d_j(x)$.
Let ${\cal H}_1,\ldots,{\cal H}_{d}$ ($d \geq 1$) be the sequence of non-terminal boxes in $\Pi(x,{\cal B})$ at
phase $j$.  By the relationship between the $t$-execution tree and the $t$-splitter tree,
$({\cal H}_1,j),\ldots,({\cal H}_d,j)$ is  a path in the $t$-execution tree and $({\cal H}_1,j-1)$ is the
parent of $({\cal H}_1,j)$.   Let $\theta_j$ be the width threshhold at the beginning of phase $j$.
We must have $\theta_j < {\bf {\rm  w}}({\cal H}_d)$ since otherwise one of the boxes ${\cal H}_1,\ldots,{\cal H}_d$ would
be a terminal box.

For the first part of the proposition, it is enough to prove the first inequality since
$\rho_j=\gamma_j^{1/4}$.
For $j=0$, $\gamma_0 \leq \alpha$ by definition.
For $j \geq 1$, by the definition of $\theta_j$ in ${\rm{\bf TerminalBox}}$,
$\theta_j \geq {\bf {\rm  w}}({\cal H}_1)\gamma_{j-1}/\alpha$ which
is at most ${\bf {\rm  w}}({\cal H}_1)$. Hence $\gamma_{j-1} \leq \alpha$ and $\gamma_j =16 \gamma_{j-1} \leq 16 \alpha$.

Now consider the second part of the proposition.
During phase $j$ each selected splitter is $\rho_j$-balanced and so ${\bf {\rm  w}}({\cal H}_d) \leq {\bf {\rm  w}}({\cal H}_1)(1-\rho_j)^{d-1} \leq {\bf {\rm  w}}({\cal H}_1)e^{-\rho_j(d-1)}$.

For $j=0$, we have $1 \leq {\bf {\rm  w}}({\cal H}_d) \leq n e^{-\rho_0(d-1)}$, so $d \leq 1 + (\ln n)/\rho_0$.
This is at most $1/\rho_0^2$ by the definition of $\rho_0$.

For $j \geq 1$, ${\bf {\rm  w}}({\cal H}_d)$
must be at least $\theta_j \geq {\bf {\rm  w}}({\cal H}_1) \gamma_{j-1}/\alpha$.  Combining this with the
previous upper bound on ${\bf {\rm  w}}({\cal H}_d)$, we have
$e^{-\rho_j(d-1)} \geq \gamma_{j-1}/\alpha = \rho_{j-1}^4/\alpha = (\rho_j/2)^4/\alpha$.  Solving this
final inequality for $d$ gives:

\begin{eqnarray*}
d \leq \frac{\rho_j+\ln (\alpha(2/\rho_j)^4)}{\rho_j} \leq \frac{\rho_j + 4\ln(2/\rho_j)}{\rho_j}
\leq \left(\frac{1}{\rho_j}\right)^2.
\end{eqnarray*}

To justify the final inequality, observe that $\rho_j \leq 2\alpha^{1/4} =2/\Psi \leq 2/C_2 \leq 1/16$.
Furthermore, for any $x \in (0,1/16)$,
$x+4\ln(2/x) \leq 1/x$.
\end{proof}

Call a terminal box ${\cal T}$ {\em narrow} or {\em wide} depending on whether ${\bf {\rm  w}}({\cal T}) \leq \omega$
or ${\bf {\rm  w}}({\cal T})>\omega$.

\begin{prop}
\label{prop:wide}
For every wide terminal box ${\cal T}$ there is a multiphase box ${\cal H}$ on the $t$-splitter path to ${\cal T}$ such that
${\bf {\rm  w}}({\cal T}) \leq \gamma_{{\tt ph}({\cal H})-1} {\bf {\rm  w}}({\cal H})/\alpha$.
\end{prop}

\begin{proof}
Since ${\cal T}$ is a terminal box, the execution of ${\rm{\bf TerminalBox}}$ for any $x \in X({\cal T})$ follows the exact same
path in the $t$-execution tree and ends with ${\cal T}$, and the final value
$\theta^*$ of the width threshhold is at least ${\bf {\rm  w}}({\cal T})$.
Since ${\cal T}$ is wide, $\theta^* \geq {\bf {\rm  w}}({\cal T})> \omega$, which implies that
$\theta$ increased at least once during the execution of ${\rm{\bf TerminalBox}}$.   The parameter $\theta$ can only change
when a new phase begins. This happens when a box is found to be unsplittable, and $\theta$ only increases.
Consider the  change of $\theta$ to $\theta^*$.   This corresponds to
an  unsplittable pair $({\cal H},i)$ on the $t$-execution path to $({\cal T},{\tt ph}({\cal T}))$
such that $\theta^*=\omega({\cal H},i)={\bf {\rm  w}}({\cal H}) \gamma_i/\alpha$.  We therefore have
${\bf {\rm  w}}({\cal H}) \gamma_i/\alpha \geq {\bf {\rm  w}}({\cal T})$.  Since $\gamma_i$ increases with $i$
and ${\tt ph}({\cal H})-1$ is the largest phase for which ${\cal H}$ is unsplittable, ${\bf {\rm  w}}({\cal H}) \gamma_{{\tt ph}({\cal H})-1}/\alpha \geq {\bf {\rm  w}}({\cal H}) \gamma_i/\alpha \geq {\bf {\rm  w}}({\cal T})$.
\end{proof}

\subsection{Revisiting tainted boxes} \label{sec:tainted}

Previously, the tainting parameter $\eta$ was $1/(10\log n)$ and the sample size $\sigma$ was $10(\log n)^2$.
The chance of (large) error in the estimate of ${\rm {\bf ApproxLIS}}_t({\cal B})$ for $|Good_t({\cal B})|$ was small
enough to use a union bound argument. We easily concluded that with high probability, no box was tainted.

Now, the parameters are $\sigma = 100\Psi^3$, $\eta = 1/10\Psi$, $\phi = \alpha^5/C_2$,
and $\alpha = \frac{1}{(C_2\Psi)^4}$.
Since $\Psi$ is only bounded below by a fixed constant $C_2$, there is a non-negligible
chance that a single call to ${\rm {\bf ApproxLIS}}_t({\cal B})$ errs in its estimate.
A simple union bound does not work and our accounting needs to be more careful.
We will prove by induction that the probability that box-level pair $({\cal B}',t')$ is tainted is small.

We remind the reader that ${\cal B}$ has a chain of terminal boxes that spans ${\cal B}$. Furthermore,
we have a grid $\Gamma({\cal T})$ in each terminal box ${\cal T}$.  A {\em spanning terminal-compatible grid chain} for ${\cal B}$
is a chain of boxes that is obtained by selecting a spanning grid chain for each terminal box ${\cal T}$
and concatenating them together.

\begin{lemma}
\label{lem:tainted}
Assume that the secondary random bits are fixed in a way such that Assumption 1 holds.
For all $({\cal B},t)$, the probability with respect to the primary random bits that $({\cal B},t)$ is tainted is at most  $\phi$,
where $\phi=\alpha^t/C_2$ is the taint probability defined in \Sec{improve-alg}
\end{lemma}

\begin{proof}
We prove the result by induction on  $t$.
 For the base case, we note that
if $t=0$, then $({\cal B},t)$ is a leaf of the instance tree and not tainted by definition.
Suppose $t\geq 1$.
By applying the definition of tainted, the inductive claim follows immediately from
the following two statements:

\begin{enumerate}
\item
 ${\rm Pr}[|{\rm {\bf ApproxLIS}}_t({\cal B}) - |Good_t({\cal B})|| > \eta {\bf {\rm  w}}({\cal B})]$  is at most $\phi/2$.
\item
The probability that ${\cal B}$ has a spanning terminal-compatible grid chain $\vec{{\cal C}}$  such that the
total width of the boxes $\{{\cal C} \in \vec{{\cal C}}| \textrm{$({\cal C},t-1)$ is tainted}\}$ is at least $\eta {\bf {\rm  w}}({\cal B})$, is at most
$\phi/2$.
\end{enumerate}

By \Prop{hoeff2}. we obtain that
${\rm Pr}[|{\rm {\bf ApproxLIS}}_t({\cal B})-|Good_t({\cal B})|| > \eta {\bf {\rm  w}}({\cal B})]$ is at most $2e^{-2\eta^2 \sigma} \leq 2e^{-\Psi} \leq 1/\Psi^{23} \leq \psi/2$, to prove the first statement.

The proof of the second statement involves more work (and  induction).
Consider a terminal box ${\cal T}$.  By \Prop{buildgrid}, the
grid $\Gamma=\Gamma({\cal T})$ has at most $|X(\Gamma)| \leq 3/\alpha$ and $|Y(\Gamma)| \leq 16/\alpha^2$. The points
$|X(\Gamma)|$ divide the box  ${\cal T}$ into at most $3/\alpha$ grid strips. For wide ${\cal T}$, each of these has width at most $\alpha {\bf {\rm  w}}({\cal T})$.
A grid strip ${\cal S}$ of ${\cal T}$ is said to be \emph{blue}
if there is a grid box ${\cal C}$ in the strip, such that $({\cal C},t-1)$ is tainted.
Note that if ${\cal T}$ is narrow, no grid strip of $\Gamma({\cal T})$ is blue (since boxes of width $1$ are by definition
not tainted).

The event whose probability we wish to upper bound in contained in the following event: the total width of blue grid strips
in ${\cal B}$ is at least $\eta{\bf {\rm  w}}({\cal B})$. This, in turn, is contained in the following event $E$:
the sum over all wide terminal boxes ${\cal T}$ of ${\cal B}$ of the width of blue grid strips of ${\cal T}$ is at least $\eta{\bf {\rm  w}}({\cal B})$.
Index the collection of all grid strips of terminal boxes of ${\cal B}$
arbitrarily as ${\cal S}_1, {\cal S}_2, \cdots$. Define random variable $Y_i$ as follows.
If ${\cal S}_i$ is blue, $Y_i = {\bf {\rm  w}}({\cal S}_i)/(\alpha {\bf {\rm  w}}({\cal B}))$. Otherwise, $Y_i = 0$.

\begin{claim} \label{clm:yi} The random variables $Y_i$ are independently distributed in $[0,1]$.
The event $E$ is contained in the event $[\sum_i Y_i \geq \Psi^3]$.
Furthermore, $\hbox{\bf E}[\sum_i Y_i] \leq 1$.
\end{claim}

\begin{proof} Suppose ${\cal S}_i$ is contained in (wide) terminal box ${\cal T}$.
The variable $Y_i$ is either $0$ or $ {\bf {\rm  w}}({\cal S}_i)/(\alpha {\bf {\rm  w}}({\cal B}))$ $\leq \alpha {\bf {\rm  w}}({\cal T})/(\alpha {\bf {\rm  w}}({\cal B}))
\leq 1$. All the grid strips of interest are disjoint,  so the random variables $Y_i$
are independent (because the primary random bits they depend on are disjoint).

Note that $\sum_i Y_i = \sum_{i: {\cal S}_i \textrm{blue}} {\bf {\rm  w}}({\cal S}_i)/(\alpha {\bf {\rm  w}}({\cal B}))$.
When $E$ occurs, $\sum_i Y_i \geq \eta {\bf {\rm  w}}({\cal B})/(\alpha {\bf {\rm  w}}({\cal B})) \geq \Psi^3$.

The lower bound on $\hbox{\bf E}[\sum_i Y_i]$ is where the  induction appears.
The number of grid boxes lying in ${\cal S}_i$ is at most $|Y(\Gamma({\cal T}))|^2 \leq 256/\alpha^4$.  By the induction hypothesis,
for each such grid box ${\cal C}$, the probability that $({\cal C},t-1)$ is tainted is at most $\phi$.
By a union bound, the probability that ${\cal S}_i$ is blue is at most $256 \phi/\alpha^4$.
By linearity of expectation, $\hbox{\bf E}[\sum_i Y_i] \leq (256 \phi/\alpha^4)\sum_i {\bf {\rm  w}}({\cal S}_i)/(\alpha {\bf {\rm  w}}({\cal B}))$
$\leq 256\phi/\alpha^5 \leq 1$.
\end{proof}
We can now apply \Prop{cher} and deduce
$\Pr[\sum_i Y_i \geq {\Psi}^3] < 2^{-\Psi^3}$ $< 1/\Psi^{23} \leq \phi/2$.
This completes the proof of \Lem{tainted}.
\end{proof}

\iffalse
 Consider a spanning terminal-compatible grid chain $\vec{{\cal C}}$; we upper
bound the total width of boxes ${\cal C} \in \vec{{\cal C}}$ for which $({\cal C},t-1)$ is tainted. By definition,  Each such  box ${\cal C}$
belongs to a terminal box ${\cal T}({\cal C})$, which may be blue or not. By hypothesis, the total width of the boxes ${\cal C}$ for which
${\cal T}({\cal C})$ is blue is at most $\sqrt{\alpha} {\bf {\rm  w}}({\cal B})/2$.
By the induction hypothesis and
a union bound over all grid boxes in a column, the probability that a column is blue is at most $C_3/(\Psi^{{21}}\alpha^4)$.

 By the above bound, this happens with probability at most $2^{-1/2\sqrt{\alpha}}$.
Let random variable $Z_{\cal T}$ be $0$ if ${\cal T}$ is not blue and ${\bf {\rm  w}}({\cal T})$ otherwise.
We have $\hbox{\bf E}[\sum_{{\cal T} \in \vec{{\cal T}}} Z_{\cal T}] \leq 2^{-1/2\sqrt{\alpha}} {\bf {\rm  w}}({\cal B})$.
Observe that the sum is exactly the width of blue terminal boxes. By the Markov inequality,
$\Pr[\sum_{{\cal T} \in \vec{{\cal T}}} Z_{\cal T} > \sqrt{\alpha}{\bf {\rm  w}}({\cal B})/2] < 2^{1-1/2\sqrt{\alpha}}/\sqrt{\alpha}$.
Since $\alpha = \frac{1}{(C_2\Psi)^4}$ and $\Psi$ is sufficiently large, this is at most $1/2\Psi^{{21}}$.

Hence, with probability at least $1 - 1/2\Psi^{{21}}$, the total width of terminal boxes
containing more than $1/2\sqrt{\alpha}$ blue columns is at most $\sqrt{\alpha}{\bf {\rm  w}}({\cal B})/2$.
The width of a column is at most an $\alpha$-fraction of the width of the containing terminal box.
The total width of blue columns (over $\vec{{\cal T}}$) \emph{not} contained in blue boxes is at most $\sqrt{\alpha}{\bf {\rm  w}}({\cal B})/2$.
Consider any spanning grid chain $\vec{{\cal C}}$ for ${\cal B}$. Any tainted box ${\cal C}$ in this chain is either contained
in a blue column or a blue terminal box. The total width of this is $\sqrt{\alpha}{\bf {\rm  w}}({\cal B}) \leq \eta {\bf {\rm  w}}({\cal B})$,
thus the
total width of $\{{\cal C} | {\cal C} \in \vec{{\cal C}}, \textrm{$({\cal C},t-1)$ is tainted}\}$ is at most $\eta {\bf {\rm  w}}({\cal B})$.
\fi

\subsection{Error analysis of the improved algorithm}
\label{subsec:revised error}

The formal statement concerning the error of the improved algorithm is:

\begin{theorem}
\label{thm:improved correctness}
Let ${\cal B}$ be a box in ${\cal U}(f)$.
Assume that the random bits used satisfy Assumption 1.
For any $1 \leq t \leq t_{\max}$, if $({\cal B},t)$ is not tainted:

\begin{eqnarray*}
\nu_t({\cal B}) & \leq & \frac{4}{t}{\tt loss}({\cal B})+\frac{{\bf {\rm  w}}({\cal B})}{\Psi}.
\end{eqnarray*}
\end{theorem}

\iffalse

\fi

\begin{proof}[of \Thm{improved approxlis}]  The claimed run time for
\Thm{improved approxlis} follows from \Cor{imp-time}.  By \Prop{assumption 1},
Assumptions 1 fails is $n^{O(\log(n)}$.  By \Lem{tainted}, the probability
that $({\cal B},t)$ is tainted is at most $\phi$. So the probability that neither of these happens
is (easily) at least $3/4$.  So we apply
\Thm{improved correctness} to get the claimed bounds.
\end{proof}

So we are left to prove  \Thm{improved correctness}.
the improved algorithm has the same global structure as the original algorithm, and in particular
satisfies \Lem{terminal}, \Prop{narrow}, and \Prop{good}.  Assumption 1 still holds with probability $1-n^{-\Omega(\log n)}$.
We can break down the proof of \Thm{improved correctness} into proving \Clm{primary} (for the primary error terms)
and \Clm{secondary} (for the secondary error terms).
Furthermore, as noted in the remark at the end of \Sec{primary},
we can reuse \Clm{primary} and its proof as is.

Hence, it only remains to prove  \Clm{secondary} for our setting, which we restate below
for convenience.
\begin{eqnarray}
\nonumber
|\zeta_1|+\sum_{{\cal T} \in \vec{{\cal T}}} (\zeta_2({\cal T}) + 5 \zeta_3({\cal T})^+ + 5\zeta_4({\cal T})^+ +5 \zeta_5({\cal T})^+)& \leq & \delta_1{\bf {\rm  w}}({\cal B})
= \frac{{\bf {\rm  w}}({\cal B})}{\Psi}.
\end{eqnarray}
We can use \Clm{et1+et2} and \Clm{et3} and their proofs from the basic analysis.
Using the new values $\eta=1/10\Psi$ and $\alpha=1/\Psi^5$ gives a bound of ${\bf {\rm  w}}/5\Psi$
on each of the contributions of $\zeta_1$, $\zeta_2$ and $\zeta_3$.

 \iffalse
We bound each error term separately in the following claims.
The desired upper bounds on $\zeta_1$ and $\zeta_2$ follow from:
\begin{claim}
\label{claim:et1+et2}
If  $({\cal B},t)$ is not tainted, $|\zeta_1| \leq \eta{\bf {\rm  w}}({\cal B})$ and $\sum_{\cal T} \zeta_2({\cal T}) \leq \eta {\bf {\rm  w}}({\cal B})$.
\end{claim}

\begin{proof}
By the definition of (non)tainted boxes, $|\zeta_1| = |{\tt alis}_t({\cal B})-|Good_t({\cal B})|| \leq \eta {\bf {\rm  w}}({\cal B}) = {\bf {\rm  w}}({\cal B})/10\Psi$.

Recall that $\vec{{\cal C}}$ is the critical chain for ${\cal B}$ and $\vec{{\cal C}}({\cal T})$ is the portion of the critical chain in terminal box ${\cal T}$.
Let $\vec{{\cal C}}^*\subset \vec{{\cal C}}$ be the subset of critical boxes that are tainted.
We use a trivial bound for $|{\tt alis}({\cal C})-|Good_{t-1}({\cal C})||$ for tainted boxes in the following.

\begin{eqnarray*}
\sum_{\cal T} \zeta_2({\cal T}) & = & \sum_{{\cal C} \in \vec{{\cal C}}} {\tt alis}({\cal C})-|Good_{t-1}({\cal C})|\\
& \leq & \sum_{{\cal C} \in \vec{{\cal C}}} |{\tt alis}({\cal C})-|Good_{t-1}({\cal C})||\\
& \leq	& \sum_{{\cal C} \in \vec{{\cal C}}^*}{\bf {\rm  w}}({\cal C}) + \sum_{{\cal C} \in \vec{{\cal C}}-\vec{{\cal C}}^*} {\bf {\rm  w}}({\cal C})/10\Psi\\
& \leq &  \frac{{\bf {\rm  w}}({\cal B})}{10\Psi} + \frac{{\bf {\rm  w}}({\cal B})}{10\Psi} =  \frac{{\bf {\rm  w}}({\cal B})}{5\Psi}.
\end{eqnarray*}
\end{proof}

The proof for $\zeta_3$ is identical to the proof \Clm{et3}.

\begin{claim}
\label{clm:et3imp}
\begin{eqnarray*}
\sum_{{\cal T} \in \vec{{\cal T}}} \zeta_3({\cal T})
& \leq & {\bf {\rm  w}}({\cal B})/5\Psi.
\end{eqnarray*}
\end{claim}
\begin{proof}
By the grid approximation lemma (\Lem{grid-approx}) for terminal box ${\cal T}$, we can choose $\vec{{\cal D}}({\cal T})$ so that it misses at most
$\alpha{\bf {\rm  w}}({\cal T})$ points of ${\cal L}^{in}({\cal T})$. Let the total width of the tainted boxes in $\vec{{\cal D}}({\cal T})$ be denoted as $b({\cal T})$.
Hence, $\zeta_3({\cal T}) \leq \alpha{\bf {\rm  w}}({\cal T}) + b({\cal T})$. Summing over all ${\cal T}$,
$\sum_{{\cal T} \in \vec{{\cal T}}} \zeta_3({\cal T}) \leq \alpha{\bf {\rm  w}}({\cal B}) + \sum_{{\cal T} \in \vec{{\cal T}}} b({\cal T}) \leq (\alpha + \eta){\bf {\rm  w}}({\cal T})$.
Since $\alpha = \frac{1}{(C_2\Psi)^4}$ and $\eta = 1/10\Psi$, $\sum_{{\cal T} \in \vec{{\cal T}}} \zeta_3({\cal T}) \leq {\bf {\rm  w}}({\cal B})/5\Psi$.
\end{proof}
\fi

To prove the bound on  $\zeta_4({\cal T}) = |{\cal L}^{out}({\cal T})| - \mu_t \cdot {\tt out}(\vec{{\cal E}}({\cal T}))$,
we use the
following variant of \Clm{et4}.

\begin{claim}
\label{clm:et4imp}
\begin{eqnarray*}
\sum_{{\cal T} \in \vec{{\cal T}}} \zeta_4 ({\cal T})& \leq & {\bf {\rm  w}}({\cal B})/5\Psi.
\end{eqnarray*}
\end{claim}

\begin{proof}
Recall that \Lem{et4} was proved in enough generality to apply to the present situation and gave us:
\begin{eqnarray}
\label{eq:et4}
\sum_{{\cal T} \in \vec{{\cal T}}} \zeta_4({\cal T}) & \leq & 2\alpha {\bf {\rm  w}}({\cal B}) + 4\sum_{P \in {\cal P}^{\circ}(\vec{{\cal T}})}\gamma(P){\bf {\rm  w}}({\cal H}(P)).
\end{eqnarray}

To analyze the final sum we consider for each index $x \in X({\cal B})$, the root-to-leaf path $\Pi(x)$ in the $t$-splitter tree.  Let ${\cal P}(x)$ denote the
set of splitters encountered along that path.  Recall that for $j \geq 0$, $d_j(x)$ is the number of splitters in ${\cal P}(x)$
that were found in phase $j$. Define
$\tilde{\gamma}(x)=\sum_{P \in {\cal P}(x)} \gamma(P)=\sum_{j \leq {\tt ph}(x)} \gamma_jd_j(x)$.
The summation on the righthand side
of \Eqn{et4} is equal to $\sum_{x \in X({\cal B})} \tilde{\gamma}(x)$.

Using the inequalities $d_j(x) \leq (1/\rho_j)^2$ and $\rho_j \leq 2\alpha^{1/4}$, and using the
fact that $\rho_j$ is proportional to $2^j$,
\Prop{phase} we have:

\begin{equation*}
\tilde{\gamma}(x) \leq \sum_{j = 0}^{{\tt ph}(x)} \gamma_j/(\rho_j)^2=\sum_{j=0}^{{\tt ph}(x)} (\rho_j )^2 \leq 2 (\rho_{{\tt ph}(x)})^2 \leq 8\sqrt{\alpha}.
\end{equation*}

Summing over $x \in X({\cal B})$  and substituting into the above bound yields the upper bound
$(2\alpha+32\sqrt{\alpha}){\bf {\rm  w}}({\cal B}) \leq 34\sqrt{\alpha}{\bf {\rm  w}}({\cal B}) \leq {\bf {\rm  w}}({\cal B})/5\Psi$.
\end{proof}

Finally, we bound $\sum_{{\cal T} \in \vec{{\cal T}}}\zeta_5({\cal T}) = \sum_{{\cal T} \in \vec{{\cal T}}}
[\mu_t\cdot{\tt aloss}_{t-1}(\vec{{\cal E}}({\cal T})) - (1-\mu_t)\cdot {\tt out}(\vec{{\cal E}}({\cal T}))]$.

\begin{claim} \label{clm:et5i}
\begin{eqnarray*}
\sum_{{\cal T} \in \vec{{\cal T}}} \zeta_5({\cal T}) & \leq & {\bf {\rm  w}}({\cal B})/5\Psi.
\end{eqnarray*}
\end{claim}

This claim is analogous to \Clm{et5} but the proof has a crucial difference.
In \Clm{et5}, we obtained a bound for $\zeta_5({\cal T})$ for each ${\cal T}$ separately and summed the bound.  In the analysis of the improved algorithm we no longer are able to separately bound each of the terms $\zeta_5({\cal T})$, rather we must
look at the entire sum and bound it.   This difference represents an important subtlety in the improved algorithm.

We explain what goes wrong if we try to follow the proof of \Clm{et5}.
Focus on the case when ${\cal T}$ is wide.
The dichotomy lemma, \Lem{dichotomy}, gives the bound $(1-\mu_t)\cdot {\tt out}(\vec{{\cal E}}({\cal T})) \geq \mu_t|U|$, where $U$ is (roughly speaking) the set of unsafe points in  $\vec{{\cal E}}({\cal T})$.
For this to be a useful bound, we must ensure that $|U|$ is small.
In the basic algorithm, ${\rm {\bf FindSplitter}}_t$ had been called on ${\cal T}$ and failed, and this
ensures that there are few safe points in ${\cal T}$.
In the improved algorithm, a failure of ${\rm {\bf FindSplitter}}_t$ does not terminate the procedure, but rather
leads to a new phase
The terminal box ${\cal T}$ is  not chosen
because ${\rm {\bf FindSplitter}}_t$ failed, but rather
because the threshold $\theta$ rises above ${\bf {\rm  w}}({\cal T})$.

When ${\cal T}$ was declared terminal, the value of $\theta$ was equal to $\gamma_j {\bf {\rm  w}}({\cal H})/\alpha$ where ${\cal H}$ is an
ancestor of ${\cal T}$ in the splitter tree, such that ${\rm {\bf FindSplitter}}_t$ failed on ${\cal H}$ in phase $j$.
This failure implies that the number of safe splitters with respect to
$\strip{{\cal H}}{{\cal B}}$ is small compared to ${\bf {\rm  w}}({\cal H})$. We cannot conclude that the number of safe
splitters with respect to $\strip{{\cal T}}{{\cal B}}$ is a small fraction of ${\bf {\rm  w}}({\cal T})$, which is required
to bound $|U|$.

To overcome this problem, we need to take a more gloabal view.  Rather than
apply the dichotomy lemma to  each grid chain $\vec{{\cal D}}({\cal T})$, we   apply the dichotomy lemma
to a single chain $\vec{{\cal D}}$ that is obtained by piecing together all the grid chains $\vec{{\cal D}}({\cal T})$ (as defined in \Sec{stripnot}).

\begin{proof} By \Prop{et5},
$$ \sum_{{\cal T} \in \vec{{\cal T}}} \zeta_5({\cal T}) \leq
\mu_t\cdot \sum_{{\cal T} \in \vec{{\cal T}}} {\tt aloss}_{t-1}(\vec{{\cal D}}({\cal T}))
- (1-\mu_t)\cdot \sum_{{\cal T} \in \vec{{\cal T}}}{\tt out}(\vec{{\cal D}}({\cal T})).$$

For each terminal box ${\cal T}$, the grid $\Gamma({\cal T})$ defines a strip decomposition $\vec{{\cal S}}({\cal T})$ of $\strip{{\cal T}}{{\cal B}}$ and $\vec{{\cal D}}({\cal T})$
is a chain compatible with $\vec{{\cal S}}({\cal T})$.  Let $\vec{{\cal S}}$ denote the concatenation of $\vec{{\cal S}}({\cal T})$ (in left-to-right order), which
gives a strip decomposition of ${\cal B}$, and let $\vec{{\cal D}}$ denote the concatenation of $\vec{{\cal D}}({\cal T})$, which is a chain compatiable
with $\vec{{\cal S}}$.
We apply the dichotomy lemma to ${\cal B}$ with strip decomposition $\vec{{\cal S}}$ and get:
$$ (1-\mu_t)\cdot \sum_{{\cal T} \in \vec{{\cal T}}}{\tt out}(\vec{{\cal D}}({\cal T})) \geq
\mu_t \cdot \sum_{{\cal T} \in \vec{{\cal T}}} |u({\cal T})|,$$
where $u({\cal T})$ is the set of $(\mu_t,\vec{{\cal D}})$-unsafe indices $x$ satisfying $F(x) \in \vec{{\cal D}}^{\cup} \cap {\cal T}$. Thus,
$$ \sum_{{\cal T} \in \vec{{\cal T}}} \zeta_5({\cal T}) \leq
\mu_t\cdot \sum_{{\cal T} \in \vec{{\cal T}}} [{\tt aloss}_{t-1}(\vec{{\cal D}}({\cal T}))
- |u({\cal T})|].$$

Partition $\vec{{\cal T}}$ into $\vec{{\cal T}}^{narrow}$ and $\vec{{\cal T}}^{wide}$ depending on
whether ${\bf {\rm  w}}({\cal T}) \leq 1/\alpha$ or ${\bf {\rm  w}}({\cal T}) > 1/\alpha$.
For a summand ${\cal T} \in \vec{{\cal T}}^{narrow}$  we have (as in the proof of \Clm{et5})
${\tt aloss}_{t-1}(\vec{{\cal D}}({\cal T})) = 0$
and the summand is nonpositive.

For ${\cal T} \in \vec{{\cal T}}^{wide}$, each summand is (trivially) at most
$|\vec{{\cal D}}^{\cup} \cap {\cal T}| - |u({\cal T})| = |s({\cal T})|$,
where $s({\cal T})$ is the set of $(\mu_t,\vec{{\cal D}})$-\emph{safe} indices $x$ satisfying $F(x) \in \vec{{\cal D}}^{\cup} \cap {\cal T}$.
Hence, it suffices
to bound $\sum_{{\cal T} \in \vec{{\cal T}}^{wide}}|s({\cal T})|$.
In the proof of \Clm{et5}, we used the fact that ${\rm {\bf FindSplitter}}$ failed on ${\cal T}$.
For the improved algorithm, we will argue that ${\rm {\bf FindSplitter}}$ failed on an ancestor ${\cal H}$ of ${\cal T}$ in
the $t$-splitter tree and that every point of $s({\cal T})$ is safe for $\strip{{\cal H}}{{\cal B}}$.

Recall that a box ${\cal H}$  is a multiphase box if the path of boxes
in the $t$-execution tree corresponding to ${\cal H}$ has more than one box.
\begin{prop}
\label{prop:bound-s}
For any wide terminal box ${\cal T}$, there is a multiphase box ${\cal H}$ in the $t$-splitter tree such that for $j={\tt ph}({\cal H})$,
$({\cal H},j-1)$ is an unsplittable pair along the $t$-execution tree path of ${\cal T}$
and every index $s \in s({\cal T})$ is $(\mu_t,\gamma_{j-1}{\bf {\rm  w}}({\cal T}))$-safe for $\strip{{\cal H}}{{\cal B}}$.
Furthermore if $s$ is nondegenerate (with respect to ${\cal T}$) then it is also non-degenerate with respect to $\strip{{\cal H}}{{\cal B}}$.
\end{prop}
\begin{proof}
By \Prop{wide} there is an ancestor ${\cal H}$ in the $t$-splitter tree such that $\alpha {\bf {\rm  w}}({\cal T}) \leq \gamma_{j-1}{\bf {\rm  w}}({\cal H})$.
Let $x \in s({\cal T})$,  and let ${\cal D}$ be $\vec{{\cal D}}[x]$ (the box of $\vec{{\cal D}}$ with $x \in X({\cal D})$).
We claim that $x$ is
$(\mu_t,\gamma_{j-1}{\bf {\rm  w}}({\cal T}))$-safe  for $\strip{{\cal H}}{{\cal B}}$.  We are given that $x$ is
$(\mu_t,\vec{{\cal D}})$-safe, which means that it is $(\mu_t,{\bf {\rm  w}}({\cal D}))$-safe for ${\cal B}$ and is
therefore $(\mu_t,{\bf {\rm  w}}({\cal D}))$-safe for the substrip $\strip{{\cal H}}{{\cal B}}$ of ${\cal B}$.
Since ${\bf {\rm  w}}({\cal D}) \leq \alpha {\bf {\rm  w}}({\cal T}) \leq \gamma_{j-1}{\bf {\rm  w}}({\cal H})$, we have the desired conclusion.

If $s$ is nondegenerate with respect to ${\cal T}$ then it is not equal to $x_R({\cal T})$.  Since ${\cal T}$ is a subbox of ${\cal H}$,
$s \neq x_R({\cal H})$.
\end{proof}
Since each terminal box ${\cal T}$ has at most one degenerate splitter, we can bound the number of degenerate
splitters in a wide terminal box by $s({\cal T}) \leq \alpha {\bf {\rm  w}}({\cal T})$ (since any wide
box has width at least $\omega = 1/\alpha$). The sum over all wide ${\cal T}$ yields a bound of $\alpha {\bf {\rm  w}}({\cal B})$.

To account for the non-degenerate splitters, \Prop{bound-s} allows us to sum over all safe points in multiphase boxes.
For multiphase box ${\cal H}$, let $s'({\cal H})$ be the set of nondegenerate indices that are $(\mu_t,\gamma_{{\tt ph}({\cal H})-1})$-safe for $\strip{{\cal H}}{{\cal B}}$.
Let $\vec{{\cal H}}^j$ denote the sequence of multiphase boxes with ${\tt ph}({\cal H})=j$ and ${\bf {\rm  w}}({\cal H}) > \omega$.
Combining with the simple bound for degenerate splitters,
$$ \sum_{{\cal T} \in \vec{{\cal T}}^{wide}} s({\cal T}) \leq \alpha {\bf {\rm  w}}({\cal B}) +\sum_{j} \sum_{{\cal H} \in \vec{{\cal H}}^j} |s'({\cal H})| $$

Since $({\cal H},{\tt ph}({\cal H})-1)$ is unsplittable, by Assumption 1 and \Cor{fails}, $|s'({\cal H})| \leq 3\rho_{{\tt ph}({\cal H})-1}{\bf {\rm  w}}({\cal H})$.

By \Prop{phase-box}, all boxes in $\vec{{\cal H}}^j$ have disjoint index intervals, so $\sum_{{\cal H} \in \vec{{\cal H}}^j} \leq {\bf {\rm  w}}({\cal B})$.
We put it all together and note that $\rho_j$ is a geometric progression. We use $j_{\max}$ to denote the largest
possible value of ${\tt ph}({\cal H})$ and bound $\rho_{j_{\max}} \leq 2\alpha^{1/4}$ (\Prop{phase}).
\begin{eqnarray*}
\sum_{{\cal T} \in \vec{{\cal T}}^{wide}} s({\cal T}) & \leq & \alpha {\bf {\rm  w}}({\cal B})+ \sum_{j} \sum_{{\cal H} \in \vec{{\cal H}}^j} 3\rho_{j-1}{\bf {\rm  w}}({\cal H})\\
& \leq & \alpha {\bf {\rm  w}}({\cal B})+ \sum_{j} 3\rho_{j-1} {\bf {\rm  w}}({\cal B})\\
& \leq &  \alpha {\bf {\rm  w}}({\cal B}) + 6 \rho_{j_{\max}-1}  {\bf {\rm  w}}({\cal B}) \\
& \leq & (\alpha + 3 \rho_{j_{\max}}) {\bf {\rm  w}}({\cal B})\\
& \leq &  7\alpha^{1/4}{\bf {\rm  w}}({\cal B}) \leq {\bf {\rm  w}}({\cal B})/5\Psi,
\end{eqnarray*}
useing the assumption that $C_2$ is sufficiently large.
\end{proof}

This completes the proof of the approximation error bound for the improved algorithm.

\section{Acknowledgements} The second author would like to thank Robi Krauthgamer and David Woodruff
for useful discussions.

\bibliographystyle{alpha}

redpajama_set_name: RedPajamaArXiv