|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
New Algorithms and Lower Bounds for LIS Estimation | | Ilan Newman
; Nithin Varma
; | | Date: |
12 Oct 2020 | | Abstract: | 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 $ ilde{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
$ ilde{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). | | Source: | arXiv, 2010.05805 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER