Estimating the length of the longest increasing subsequence (LIS) in an array is a problem of fundamental importance. In this paper, we investigate the two aspects of adaptivity and parameterization in sublinear-time algorithms for LIS estimation . We first show that adaptivity helps in LIS estimation, 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. This is the first lower bound on LIS estimation that is significantly larger than the query complexity of testing sortedness. In contrast, there is an adaptive algorithm (Saks, and Seshadhri; 2017) for the same problem with query complexity polylogarithmic in n. Next, we design nonadaptive LIS estimation algorithms whose complexity is parameterized in terms of the number of distinct values r in the array  . We first present a simple algorithm that makes O(r/\epsilon^3) queries and approximates the LIS  with an additive error bounded by \epsilon n. We then use it to construct a nonadaptive algorithm with query complexity O(r  /\lambda ^2) that, for an array in which the LIS is of length at least \lambda n, outputs a O (\lambda) multiplicative approximation to the length of the LIS . Our algorithm improves upon state of the art nonadaptive algorithms for LIS estimation (for r=n) in terms of approximation guarantee. 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 sortedness, thereby making progress towards solving an open question (Raskhodnikova, Ron-Zewi, and Varma; 2019) .
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 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 O(r \cdot \text{poly /\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 .
R
In this paper, we investigate the two aspects of adaptivity and parameterization in sublinear-time algorithms
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
R
. We first show that adaptivity helps in
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
R
specifically
and also provide novel algorithms that complement our lower bound. Specifically
D
This is the first lower bound on LIS estimation that is significantly larger than the query complexity of testing sortedness. In contrast, there is an adaptive algorithm (Saks, and Seshadhri; 2017) for the same problem with query complexity polylogarithmic in n.
R
is parameterized in terms of the
decreases as the the
R
r
, r,
A
decreases
A
length
A
\cdot \text{poly
R
^2)
))
R
in which the LIS is of
with LIS
R
O
multiplicative \Omega
R
multiplicative approximation to the length of the LIS . Our algorithm improves upon state of the art nonadaptive algorithms for LIS estimation (for r=n) in terms of approximation guarantee.
-approximation to the LIS length.
R
sortedness, thereby making progress towards solving an open question (Raskhodnikova, Ron-Zewi, and Varma; 2019)
monotonicity