License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2021.100
URN: urn:nbn:de:0030-drops-141699
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14169/
Go to the corresponding LIPIcs Volume Portal

Newman, Ilan ; Varma, Nithin

New Sublinear Algorithms and Lower Bounds for LIS Estimation

pdf-format:
LIPIcs-ICALP-2021-100.pdf (0.8 MB)

Abstract

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, we show that for every ε ∈ (0,1), every nonadaptive algorithm that outputs an estimate of the LIS length in an array of length n to within an additive error of ε n has to make log^{Ω(log (1/ε))} n queries. Next, we design nonadaptive LIS estimation algorithms whose complexity decreases as the number of distinct values, r, in the array decreases. We first present a simple algorithm that makes Õ(r/ε³) queries and approximates the LIS length with an additive error bounded by ε n. This algorithm has better complexity than the best previously known adaptive algorithm (Saks and Seshadhri; 2017) for the same problem when r ≪ polylog (n). We use our algorithm to construct a nonadaptive algorithm with query complexity Õ(√r⋅ poly(1/λ)) that, when the LIS is of length at least λ n, outputs a multiplicative Ω(λ)-approximation to the LIS length. Our algorithm improves upon the state of the art nonadaptive LIS estimation algorithm (Rubinstein, Seddighin, Song, and Sun; 2019) in terms of the approximation guarantee.
Finally, we present a O(log n)-query nonadaptive erasure-resilient tester for monotonicity. Our result implies that lower bounds on erasure-resilient testing of monotonicity does not give good lower bounds for LIS estimation. It also implies that nonadaptive tolerant testing is strictly harder than nonadaptive erasure-resilient testing for the natural property of monotonicity.

BibTeX - Entry

@InProceedings{newman_et_al:LIPIcs.ICALP.2021.100,
  author =	{Newman, Ilan and Varma, Nithin},
  title =	{{New Sublinear Algorithms and Lower Bounds for LIS Estimation}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{100:1--100:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14169},
  URN =		{urn:nbn:de:0030-drops-141699},
  doi =		{10.4230/LIPIcs.ICALP.2021.100},
  annote =	{Keywords: longest increasing subsequence, monotonicity, distance estimation, sublinear algorithms}
}

Keywords: longest increasing subsequence, monotonicity, distance estimation, sublinear algorithms
Collection: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Issue Date: 2021
Date of publication: 02.07.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI