Estimating the Longest Increasing Subsequence in Nearly Optimal Time
Estimating the Longest Increasing Subsequence in Nearly Optimal Time
复制标题
DOI：
10.1109/focs54457.2022.00073
复制
发表时间：
2021-12
期刊：
影响因子：
--
通讯作者：
Alexandr Andoni;Negev Shekel Nosatzki;S. Sinha;C. Stein
中科院分区：
文献类型：
--
作者：
Alexandr Andoni;Negev Shekel Nosatzki;S. Sinha;C. Stein
最长的增加子序列（LIS）是序列的基本统计数据，并且已经研究了数十年，而长度为n的LI可以完全计算出时间$ O（N \ log n）$的复杂性。 （尤其是在Lis $ \ ll n $）中，（尤其是在\ Mathbb {n} $和$ \ lambda = o（1）$中的任何$ n \）存在一种（随机的）非自适应算法，给定带有Lis $ \ geq \ lambda n $的长度n序列，近似于$ 1/\ lambda^{o（1）} $ in $ n^{o（1）}/\ lambda $ time 。 $ \ omega（1/\ lambda）$的样本复杂性下限为了获得我们解决方案的一部分的任何不平整的近似值，我们会开发两个新颖的想法，这可能是独立的。或在此模型中损坏。通用性的测试数量。精密树是在一组样品上预处理的，此后由算法的多个组件反复使用，以提高其摊销复杂性。
Longest Increasing Subsequence (LIS) is a fundamental statistic of a sequence, and has been studied for decades. While the LIS of a sequence of length n can be computed exactly in time $O(n\log n)$, the complexity of estimating the (length of the) LIS in sublinear time, especially when LIS $\ll n$, is still open. We show that for any $n\in\mathbb{N}$ and $\lambda=o(1)$, there exists a (randomized) non-adaptive algorithm that, given a sequence of length n with LIS $\geq\lambda n$, approximates the LIS up to a factor of $1/\lambda^{o(1)}$ in $ n^{o(1)}/\lambda$ time. Our algorithm improves upon prior work substantially in terms of both approximation and run-time: (i) we provide the first sub-polynomial approximation for LIS in sub-linear time; and (ii) our run-time complexity essentially matches the trivial sample complexity lower bound of $\Omega(1/\lambda)$, which is required to obtain any non-trivial approximation of the LIS. As part of our solution, we develop two novel ideas which may be of independent interest. First, we define a new Genuine-LIS problem, in which each sequence element may be either genuine or corrupted. In this model, the user receives unrestricted access to the actual sequence, but does not know a priori which elements are genuine. The goal is to estimate the LIS using genuine elements only, with the minimal number of tests for genuineness. The second idea, Precision Tree, enables accurate estimations for composition of general functions from “coarse” (sub-)estimates. Precision Tree essentially generalizes classical precision sampling, which works only for summations. As a central tool, the Precision Tree is pre-processed on a set of samples, which thereafter is repeatedly used by multiple components of the algorithm, improving their amortized complexity.