New Algorithms and Lower Bounds for LIS Estimation

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 $\tilde{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 $\tilde{O}(\sqrt{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).