English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

Estimating the length of the longest increasing subsequence (LIS) in an arrayis a problem of fundamental importance. Despite the significance of the LISestimation problem and the amount of attention it has received, there areimportant aspects of the problem that are not yet fully understood. There areno better lower bounds for LIS estimation than the obvious bounds implied bytesting 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 nonadaptivealgorithm that outputs an estimate of the length of the LIS in an array oflength $n$ to within an additive error of $\epsilon \cdot n$ has to make$\log^{\Omega(\log (1/\epsilon))} n)$ queries. Next, we design nonadaptive LISestimation algorithms whose complexity decreases as the the number of distinctvalues, $r$, in the array decreases. We first present a simple algorithm thatmakes $\tilde{O}(r/\epsilon^3)$ queries and approximates the LIS length with anadditive error bounded by $\epsilon n$. We then use it to construct anonadaptive algorithm with query complexity $\tilde{O}(\sqrt{r} \cdot\text{poly}(1/\lambda))$ that, for an array with LIS length at least $\lambdan$, 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 toleranttesting is strictly harder than nonadaptive erasure-resilient testing for thenatural property of monotonicity.

New Sublinear Algorithms and Lower Bounds for LIS Estimation