  Estimating the length of the longest increasing subsequence (LIS) in an array
is a problem of fundamental importance. Despite the significance of the LIS
estimation problem and the amount of attention it has received, there are
important aspects of the problem that are not yet fully understood. There are
no better lower bounds for LIS estimation than the obvious bounds implied by
testing monotonicity (for adaptive or nonadaptive algorithms). In this paper,
we give the first nontrivial lower bound on the complexity of LIS estimation,
and also provide novel algorithms that complement our lower bound.
  Specifically, for every constant $\epsilon \in (0,1)$, every nonadaptive
algorithm that outputs an estimate of the length of the LIS in an array of
length $n$ to within an additive error of $\epsilon \cdot n$ has to make
$\log^{\Omega(\log (1/\epsilon))} n)$ queries. Next, we design nonadaptive LIS
estimation algorithms whose complexity decreases as the the number of distinct
values, $r$, in the array decreases. We first present a simple algorithm that
makes $\tilde{O}(r/\epsilon^3)$ queries and approximates the LIS length with an
additive error bounded by $\epsilon n$. We then use it to construct a
nonadaptive algorithm with query complexity $\tilde{O}(\sqrt{r} \cdot
\text{poly}(1/\lambda))$ that, for an array with LIS length at least $\lambda
n$, outputs a multiplicative $\Omega(\lambda)$-approximation to the LIS length.
  Finally, we describe a nonadaptive erasure-resilient tester for sortedness,
with query complexity $O(\log n)$. Our result implies that nonadaptive tolerant
testing is strictly harder than nonadaptive erasure-resilient testing for the
natural property of monotonicity.
